CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)

　Fまで。

　Fはうまくやればdictは必要なかった。どの数字が何個あるかを配列に記録し、差分計算すれば良かった。PyPyで通せなかったのには理由がありました。

　ただ、思いつくべき内容ではあったが、個人的にはこういうlog外しはあまり重要に思えないのよね。AHCで焼きなましの回数を増やしたい！　とかなるとこういうことも重要になってくるけども。しかしそれも、高速な言語に書き換えた上での話な気もする。

コンテストへのリンク

コンテスト後のツイート

F 一行ごとならZero-Sum Rangesみたいに解けるので、H*H*Wの計算量になる。H,Wの大小で場合分けすれば解けると思ったがPyPyだとTLE一個が取れない。仕方なく、AtCoder生成AI対策ルールを久々に見に行き、RUSTに変換してもらったら2784 msでACした。

— titia (@titia_til) June 14, 2025

G - Longest Chord Chain

　解説放送を見てAC。解説を見てしまったけど、多分時間があれば自力で解けたと思う。

　[a,b]と[c,d]の区間が交わらないような最長のものを求める感じなのは分かるが、円環の問題なので、どこかで切り分けなくてはいけないのが難しい。

　これを、[a,b]だけでなく、[b,a+2*N]も考えることで、ただのLIS（今回は、最長減少部分列の方だが）を求める問題になるというのは驚き。こうすると実装しやすいね。