AtCoder Regular Contest 151

　ABの二完で終わり、レートを大きく落とした。B・Cで答えが合わず、愚直を書くのに時間を費やしたりしているのが厳しい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 151 BよりCがいけそうと思ってCをやっていたが、1caseがWAが取れず。遅解き二完でひどい。
A (0,1)のもの、(1,0)のものの個数をそれぞれ調べる。
B union-findでつなぎながら、答えを加算していく。
C 同じ数字が隣あっているものの個数を調べた後……？

— titia (@titia_til) October 16, 2022

C - 01 Game

　自力AC。

　実験などして、同じ数字に挟まれている部分はturnが奇数個、別の数字に挟まれている部分はturnが偶数個増えることは分かった。

　なので、あとは両端について分かれば良い。

　真似っ子戦略ができそうだが、今一つ分からず愚直コードを書いたら、

・両端以外のturnが偶数個のときは、両端の空きマスが同じ個数のときのみ後手の勝利

・両端以外のturnが偶数個のときは、両端の空きマスの個数が1個差で、大きい方が奇数個のときのみ後手勝利

　と分かった。

　前者は真似っ子戦略を考えれば当然。

　後者は両端を「二個以上減らすことはできるけど、一個減らすことはできない」ことを使う。同じ数字を隣におけないため、一個減らそうと思っても不可能なのだ。

　なので、二個減らす回数の偶奇により、勝者が変わることになる。

　本番は、後者のとき、「両端の空きマスの個数が1個差」であれば後手が勝利していると勘違い（実験コードの分析を間違った。上記の理屈にも気付かなかった）したためWAが一個出てACできず。

　これは時間がなくて焦っていたせいですね。もうちょっと余裕があればACにたどりつけてそう。

D - Binary Representations and Queries 

　解説AC。

　問題内容を把握するのに時間がかかってしまい、解説を読んでも「なんでこんなに解かれるの？」という気持ちだったが、多少整理すると「確かにそこまで難しくないか」とも思えてきた。

・Xが異なればクエリの順番を入れ替えてもOK

　と気付くのが重要。

　これは、言われれば確かにそうか、という気持ちになる。

　これさえ気付ければ、各Xのクエリは二者で足し合うだけなので、最初の数字を1としてシミュレーションすれば良い。

E - Keep Being Substring

　解説AC。

・XとYに共通部分がある→一番長い共通部分をsuffix arrayとLCP配列を使って探す

・XとYに共通部分がない→一文字にした後、Yのどれかの文字へ変形するのが最適。最短経路問題になる。

　言われてみればそう難しくない。

　ただ、一番目について、同じことを考えたのだが、最長の共通部分の求め方が分からなかったし、解説を読んでもLCP配列が何かすぐに思い出せなかった。文字列アルゴリズムは適宜使えるようにしておきたい。