ARC 140 感想・反省 - sankantsuのブログ

結果

A1完 (64:23 + 2ペナ)

初めて実レート減少

最初に参加したARC(138)でも1完でひどいパフォを出し，今回はせめて2完したいと思っていたが撃沈やっぱり同じ配点の問題でもABCよりARCのほうがずっと難しいと感じる．苦手意識による思い込みなのか，問題傾向が苦手なのか，それともたまたま解けなかっただけなのか...．

コード

github.com

終了後に実装を修正している

各問題の振り返り

A

文字列をできるだけ短い周期で繰り返すパターンに編集する問題

$N \leq 2000$ の制約を見るに， $O(N^ 2)$ ぐらいが目安かなと見積もる．

最初に考えたのは，周期について2分探索できないかという方針．しかし，これはある周期を達成できるならそれより長い周期はかならず達成できるという前提に基づいていて，正しくない．

2分探索はできないが，調べる周期のパターンを少なくしたいというモチベーションは悪くなさそうである．周期としてありうる数がなんであるかということをもう少し考えてみると， $N$ の約数だけが周期となりうるということに気づく．約数の数はそれほど大きくならないと考え，ひとつの周期に対する達成可能であるかの判定に $O(N^ 2)$ で約数について全探索すれば解けるのではないかと考えてみる．

ある周期が達成可能かどうかを $O(N^ 2)$ で調べる方法だが，周期の各位置にあたる文字を一番出現回数の多い文字に合わせるという作業を $O(N)$ で行い，これを文字列の開始位置をずらしてすべて調べればよいだろうと考えた．(実際，文字列の開始位置をずらす作業は意味がない．計算量が $O(N^ 2)$ で良いだろうという思い込みがあったことから無駄に気づけなかった．)

テストケースが通ったので提出してみるとWA．見直してみると，周期内の各位置について調べるという部分が実は周期内の1点しか調べていないというミスをしていることに気づき，修正．

しかしこれを提出してみるとなぜかRE．よく見てみると，なぜか同時に開いていたB問題のほうに提出してしまっていた．改めて提出し直すと，1ケースだけTLEになった．

なんとか速くならないかと見直してみるが，なぜか実際文字列の開始位置をずらす作業が無駄であることには気づかず．代わりに，約数を全探索するのではなく，ある約数 $M$ についてそれを周期とすることができないなら， $M$ の約数についても周期にすることはできないという点に気づいて修正し，なんとかACになった．

B

文字列に対して特定の操作を行うことができる回数の最大値を求める問題．

操作可能な箇所すべてについて順番をかえて再帰的に探索するのでは間に合いそうもないので，最適な操作順というものを考えてみる．奇数回目の操作の後，操作箇所のまわりで新たにARCという文字列ができるのは，もともとがAARCCという並びになっていたときである．偶数回目の操作の後，操作箇所のまわりで新たにARCという文字列ができることはない．

よって，AARCCというのような並びがある部分はできるだけ奇数回目に操作することにするのが最適になる．

最適な操作について，より具体的に考える． $A^ k R C^ k$ という並びを文字列の中からすべて探し，重複を含む $k$ の集合(multiset)を考える． - 奇数回目の操作では $k$ が最も大きいものを選び， $k\gt1$ であれば $k$ を1減らして集合に戻す． $k=1$ であれば要素を取り除く． - 偶数回目の操作では $k$ が最も小さいものを選び，要素を取り除く．このようにして行える操作の回数を求めれば答えが求まる．