AtCoder Regular Contest 153

　A,C問題を解いて2完。

tokuminiさんのAtCoder Regular Contest 153での成績：475位
パフォーマンス：1911相当
レーティング：1910→1910 (±0) :|
#AtCoder #ARC153 https://atcoder.jp/users/tokumini/history/share/arc153?lang=ja

　A問題を通したあとB問題で時間がかかってしまい、途中で順位表を見たときに解いた人数が多すぎてこれ解けても順位が伸びないと思ったのでCに取り掛かっていた。Cも解けなかったら悲惨なことになっていたのでなんとか通せて良かった。

A問題

　制約的に列挙できるんだろうなというのが感覚としてわかったので実装し始め、書いている途中で6個しか変わらないからだなぁという理解をする。

　組み合わせを列挙するために準備しているクラスを適当に改造して実装。

提出

B問題

　行と列は分解できるだろうとは思ったし、行が1回の操作でどうなるかは書き下していた。操作 $a$ で

$\begin{cases} (a - 1 - i) & (i < a) \\ (H - 1 - i + a) & (i \ge a) \end{cases}$

だと（ $i$ は0-indexed）

　でもこれが

$(H - 1 - i + a) \% H$

であることに気づかず。これに気づけば操作がまとめられるのでなんとかなる。数式の項をちょっと整理すれば気づきそうだったのにな。残念。

提出（コンテスト後）

C問題

　未証明気味。

　まず、答えの数列 $x$ に負の数があると考えづらいので0以上で考えてみる。一番単純なものだと $0,1,2,3,...$ というものになり、この値を基準としてどう変化させられるか考えたくなった。そうすると、どこか $x$ の途中から右側全てに同じ数を足すという操作がまず簡単に数値を変える手段としてありそうだと気づく。 $A$ の右側から累積和を取って、-1になるところがあれば-1を無限回やれるし、+1になるところがあれば+1を無限回できる。最初の $0,1,2,3,...$ の和が $N * (N - 1) / 2$ なので、変更する量もだいたいこれくらいになるということで上限には達しない。