AtCoder Grand Contest 039

結果

順位   642nd / 3114
パフォーマンス   1676
レーティング  1917 → 1895(-22)

A - Connection and Disconnection

　2WA。まず一回目は「S一つを考えたときに必要な操作回数を数えて $K$ 倍し、Sの末尾とSの先頭が同じなら $K - 1$ 回プラス」という方針。しかしこれは

aabaaa
2

に対して5と答えてしまうので全然ダメ。

　二つ目の提出は $K$ が3未満のときは構築して愚直に、3以上のときは3つ連結したものを考えて、先頭・中間・末尾として扱って中間で必要な操作回数だけ $K - 2$ 倍するというもの。しかし

aaa
5

に対して8と答えてしまうのでダメ。文字が1種類だと中間が常に同じ消し方になるとは限らない。最初に条件分けを追加してAC。

　AGCのA問題をWAなしで通せる気がしない。

　提出

B - Graph Partition

　3WA。A問題でWAを出すとそれ以降の問題に対してもやや投げやりに提出してしまうところはあるかもしれない。

　まずいろいろ考えていると、だいたいグラフの端っこっぽいところからBFSをすれば良さそうという気持ちが芽生える。（2部グラフになっていなかったら途中で弾く）

　グラフの端を見つけたい。適当に頂点0からダイクストラ法で距離最大となる頂点を探し、そこからBFSをするという方針で1WA。木の直径の話を思い出して、最初にダイクストラをやって最大距離となる頂点からもう一回ダイクストラやって最大距離となる頂点からBFSをやるようにしてもう1WA。ひょっとして次数が1の頂点ならどこからBFSしても同じなのではと思って提出してさらにWA。

　ここで冷静になって、計算量的に間に合うんだからBFSし始める点を全探索すればいいじゃんということに気づいてAC。解説PDFとは違うけど、たぶん正当、かな？

　提出

C - Division by Two with Something

　いろいろ実験をしているうちに、ループするのが $N$ の奇数の約数をビット幅にもってb ~b b ~b b ... b ~b bのような形になる場合だと考えて、 $X = 2^N - 1$ の場合は解けそうだと思ったのでその特殊ケースについてずっと考えていた。残り十数分というところでそれについては解けた（提出）が、しかし $X \lt 2^N - 1$ の制約では全然わからずお手上げ。