112. AtCoder参加記録（AtCoder Regular Contest 140）

19回参加でレート 1131 です。

今回はパフォーマンス 1681 です。初めての青パフォ！

ABCを通して、DEFは未解答です。3ペナですが、十分すぎる成果。

各問題の感想など。

A

16分6秒（Bから戻ってきた後の所要時間）。

まず、 $f(T)$ はどのように求められるか考えました。入力例を見ると、自然数 $n$ を小さい方から見て、先頭から $n$ 文字のループで文字列が構成される場合 $f(T) = n$ となるみたいです。 $N \le 2000$ なので、 $1 \le n \le N$ で $n$ 文字ループが作れるか、作るとしたら何文字変換すればよいか、を見れば $O(N^2)$ で行けそう…と考えました。実際には $n$ は $N$ の約数だけ見れば良いのでもっと余裕があります。

文字の変換は、ループさせる文字列の $i$ 文字目（ $1 \le i \le n$ ）で最も多く使われている文字を採用して、それ以外を変換すればよいです。変換する文字の合計数が $K$ 以下ならOK、そのときの $n$ が答えです。

この辺りまで5分ほどで薄っすら思い浮かびましたが、ちょっと確信を持てなかったのと実装が明らかに重かったので、頭の整理がつくまで一旦パスしてBを見ました（えらい）。

B

41分04秒（Aの考察時間を含む）。

変換後に ARC が新たにできるかが焦点です。偶数回目の操作 ARC → AC ではどうやってもできません。奇数回目の操作 ARC → R では、AARCC のようなパターンでできます。よって、正規表現で書くと (A+)ARC(C+) のようなパターンがあれば奇数回目の操作で変換「したい」です（注意すべきは、必ずできるとは限らない点です）。

ある ARC から新たな ARC を作れる回数は、前後のAとCの連続数のうち小さい方です。各 ARC についてこの数をカウントしておき、この数が 0 である ARC は別にカウントします。前者は奇数回目で優先的に選択し、後者は偶数回目で優先的に選択します。偶数回目で後者がない場合、仕方がないので前者を選択します。

結局、このような ARC の個数の計算に $O(N)$ 掛かり、あとは変換をシミュレートするだけなので、大きく見積もっても $O(N)$ です。

これも実装が重いですが、Aよりは楽そうだったのでこちらから片付けました。実装ミスで1ペナ。

C

51分52秒。

ABが解けた時点でだいぶ安堵して、かなりリラックスしながら「解ければラッキー」くらいの気持ちで解いていました。

なるべく真ん中の値から初めて、小さい方・大きい方…のようにジグザグ取っていけば良さそう？と直感。たとえば、 $(N, X) = (5, 1)$ なら、2文字目は真ん中の値にして $(1, 3, 4, 2, 5)$ のような形です。これでジグザグに取れなくなったら、余ったものを適当に後ろへくっつけます。

あんまり確信は無かったですが、正直これ以外思いつかなかったのでその通りに実装。小さい方・大きい方どちらから優先的に取るか、 $N$ が偶数のときの「真ん中」の取り方、で $2 \times 2$ 通り試して、 $O(4N)$ くらいの実装にしました。この場合分けのアイデアは、昨日の ABC E問題の教訓でもあります。