今週のABC結果　ABC313

Updated on Jun 5, 2024 1 min read Rust

結果的には前回と変わらずABの2問しか解けなかった。

タイピングミスで集中力が乱れたり、問題文の理解に苦労したりということはなかったものの、Cは時間内に解くことができなかった。パフォーマンス的にはいつもと変わらない感じではあった。Cが解けなくてDを考えようか、いややっぱCをやったほうがいいなと問題行ったり来たりしたのもよくなかったかもしれない。

Cの敗因

ひとえに考察があまかったと、それに尽きると思う。

なんとなく平均を攻めていく問題だと思ったので、平均を求めて元の配列の値を平均値にむかって増減させていけば答えが求まりそうと思って実装した。

しかしそれだけではサンプルでは通ったとしても、本番のテストケースは通らない。提出してこれはだめだろうなとわかりつつも、そこから先へ思考を進めることができなかった。解説見たらそういうことかとわかったけれども。

本番中にそこまで考察できなければ進歩がない。とりあえず手を動かして実装してしまったほうが早いと感じてしまうのは、数学的考察ができていない証拠である。とりあえず手を動かして調べる前に、考察進めてから実装するよう心がけたい。

現状だとある程度考察して方針らしいものを見つけたら実装に移ってしまいがち。それ以上の考察の取っ掛かりがないので（平たく言うとわからんから）、方針見つけたら実装したほうが早いと思ってしまう。しかしそれで失敗しているのだから、この方針自体を改めるべきだろう。

操作の内容は、i,jを選んでAi+1, Aj-1する。このことから与えられた数列Aの総和は変わらない。よって方針はすべての値を平均に近づけることということがわかる。

もう少し詳しくいうと、すべての値についてfloor(平均の値)とfloor(平均の値)+1のどちらかに寄せるである。これは操作によって数列Aの総和が変わらないので、単純に平均を求めるた端数をする必要があるから。問題は平均+1にする個数である。

こう書くとなぜ本番中に気づけなかったのかというくらい単純な話なのだが・・・。

平均+1する個数は数列Aの総和をnで割ったあまり、もしくは総和-floor(総和/n)*nすると求められる。解説のコードは%nであまりを計算していた。

あとはこの平均値にAiの各値を近づけるためにいくつ増減すればよいかを求めるだけだ。

数列Aを昇順にソートしたものと、数列B（すべての要素をfloor(平均の値) or 平均+1にしたもの）を比較して計算すると楽。数列Aを昇順でソートしておかないと平均+1との差を計算した場合に最適とはならないから。

試していないけど、平均より大きい値について%n個だけ平均+1との差の絶対値をとれば良さそう。ただしそうした場合に平均より大きい値の個数が%nより少なかった場合にWAとなりそうな気がするので、素直に昇順にソートして数列Bとの差をとったほうがよさそう。