【ABC377】E問題に脳を破壊されました…

はじめに

こんにちは、KCPC代表のみうね（m1une）です。今回はABC377の感想を綴っていきます。

コンテスト前の私のレートは1499で、過去２回のレート推移が-3、-5と微減を繰り返していたのでそろそろその連鎖を断ち切りたいという思いで、1600perf以上を目標にしていました。

今回の配点は100-200-300-400-475-550-575で、G問題が少し弱いかもしれないという位でごくごく普通な配点でした。（翌日のARC186が800-900-900-900-1000とかいうイカれた配点をしているので、なおのこと平和な配点に見えた）

しかし、コンテストが始まってみればE問題が予想外に難しく…

コンテスト前

当日の昼間は部活に行って、その帰りにゲーセンに寄ったりもしていました。最近はよく弐寺（beatmania IIDX）という音ゲーをやっているのですが、だんだん☆12（表記上の最高レベル）をクリアできるようになってきててとても楽しいです。

今日の（AAは再易）
着実に地力ついてる感はある pic.twitter.com/YcnXPtfXyq
— みうね (@m1une_otoge) 2024年10月26日

ただ、ただでさえ部活で消耗しているのに、弐寺でさらに体力を消耗してしまうのは、ABCにむけた準備としては悪手だったとは思います。でも楽しいから仕方ないね〜

この1週間はなんだかんだで色々と忙しく、先週のABC以来競プロの問題を1問も解いていませんでした。精進もしないでいい成績が出るはずもないので、これに関しては反省です。精進しましょう。

以下私が取り組んだ問題（A〜E）について考えたことや感想を述べていきます。

A問題

問題文: A - Rearranging ABC

KCPCメンバー（rated）のAC数：13/13

diff: 12

コンテストが始まってから30秒ほど問題が読み込まれず、なんか重いなあと思っていました。

問題自体はどんなやり方でも解けますが、与えられた文字列をソートしたものが"ABC"に一致するかどうかを判定するのが一番楽だと思います。1:32に提出、無事AC。

B問題

問題文: B - Avoid Rook Attack

KCPCメンバー（rated）のAC数：13/13

diff: 50

64マスしか無いので、割とどんな非効率的なやり方（全探索など）をしても通るとは思います。

既に置かれているコマと同じ行・列には自分のコマを置けないので、(コマが1つも置かれていない行の数)×(コマが1つも置かれていない列の数)をすれば答えが求まります。自分は行と列をそれぞれsetにぶち込んで、最終的なsetの大きさを用いて答えを求めました。3:20に提出、無事AC。

C問題

問題文: C - Avoid Knight Attack

KCPCメンバー（rated）のAC数：13/13

diff: 274

こんどは $N \leq 10^9$ なので、B問題のように1マス1マスぜんぶ調べるということはできません。その代わりに、コマ1つにつき自分のコマが置けなくなるようなマスは最大9つ（コマ自身のマスも含める）なので、コマひとつひとつにつき効いてるマスを調べれば良いです。

具体的な実装方法としては、set<pair<int, int>>を使えば重複があっても二重にカウントしたりすることがなくて済むので簡単です。7:58に提出、無事AC。

D問題

問題文: D - Many Segments 2

KCPCメンバー（rated）のAC数：12/13

diff: 987

問題文の意図を読み取るのに少し苦労しました。

$l$ を固定した時に $r$ をどこまで伸ばせるかが $O(\log N)$ でわかれば $O(M \log N)$ で解けそうだな〜と思い、考えてみました。

$L, R$ の組を $L$ の昇順でソートして、 $l = 1 \ldots M$ について $\underset{ \{ i \ \mid \ l \leq L_i \}}{ \min } R_i$ を求めればよいので、ACLのsegment treeを用いてRMQ（Range Minimum Query）を実装すればうまくいきそうです。

$\{ i \ \mid \ l \leq L_i \}$ が空集合である時の処理に手こずったり、ソートを書き忘れて多少沼ったりしましたが、なんとかサンプルを通し、少し怖いながらも21:01に提出、無事AC。

E問題

問題文: E - Permute K times 2

KCPCメンバー（rated）のAC数：3/13

diff: 1685

問題のE問題。 $K \leq 10^{18}$ なので、まっさきにダブリングを疑い、実際に書いてみましたが合わず。

手元で試してみたところどうもサイクルになっているところ同士でしか交換し合わないので、サイクルだけ見て周期性を見出せばなんとかなりそうと思い周期がいくつなのかを調べました。

すると、どうもサイクル長が奇数のときは $2^l - 1$ が $l$ で割り切れる最小の数 $l$ が周期になっているらしいということがわかり（嘘かもしれない、一般にはなもりグラフになりそう）、サイクル長の偶奇で場合分けをやりはじめました。今から考えるとこれが地獄の始まりでした…

サイクル長が偶数の時はどうなんだととりあえず手元でサイクル長 $= 2, 4$ の場合を試してみるとどうもサイクルの全要素のindexと値が一致しそう（これは明確に嘘。2べきの場合しか試さなかったのが悪い）ということがわかり、それを実装しました。

しかしサンプルが合わず…どうもサイクル長が偶数の時にうまく行ってなさそうだったので、サイクル長 $= 6, 10$ のときを試してみるとこれはなもりグラフになっているようだということにようやく気づきました。そこでなもりグラフを検出していい感じに処理するコードを書いてみると、ここでやっとサンプルが通ります。

やっとサンプル通った〜と思って提出してみると、早々にTLEを吐かれてしまいます。なにが悪いんだと思っていろいろ考えた結果、奇数の場合でもなもりグラフになる可能性があってそのせいで無限ループが発生しているのでは無いかと終了直前に思い、急いでコードを偶数の場合のものに一本化して提出してみましたが急ぎすぎてCE。ここでコンテストが終了しました。

コンテスト終了後

Eの解説を見て、確かに…と崩れ落ちました。 $2^K$ に近い発想はしていたのに、 $2^K$ をそのままサイクル長で割ればいいという発想には至れませんでした。たぶん $2^K$ はあまりに大きすぎて発想しづらいという側面もあったと思います。

そして、D問題まで21分で通しているのにE問題で80分すべて溶かすのはもったいなかったです。G問題は比較的取り組みやすいように思えるので、E問題を諦めてGに行っていればまた結果は違った可能性もありました。

結果

ABCDの4完で終わってしまいました。perfは1438で、レートは-6の微減という結果に終わりました。結局レートがだんだん下がっていく傾向は止まるところを知らず、次の激ヤバ配点ARCでどうなることかとヒヤヒヤしています。

反省点

精進をしましょう。
一つの問題であまりに詰まった時は先の問題も見てみましょう。
一度の失敗を引き摺らないようにしましょう。

余談

今回のABCでは、問題とは関係ないところで少し思うところがあったのでお気持ちを書こうと思います。今回のABCは、おそらくメイン言語を生成AIとされている方が1位となっていました。この方は、1秒ACをしていたりするわけではないので、おそらくはAtCoderのAI使用ルールに基づいて参加しているのだと思います。しかし、問題文を書き写して、多少のプロンプトを入力するだけで全問正解できてしまうというのは競技としてどうなんでしょう…

個人的にはCodeforcesのルールのように、AIは翻訳とコード補完としての使用のみに限定したほうがいいのではないかと思っています。皆さんはどう思いますか？