脳log[20250614]

2025年06月14日 (土) [AtCoder] 今日は CodeQUEEN 2025 予選 (ABC410) があった。問題の傾向として JOI に近いのだろうか。典型的な基礎知識が確実に身についているかを確かめる感じ。だからってそれが必ずしも簡単なわけじゃない。DP ひとつとってもいくらでも難しくなる。難易度はともかく、DP は必ず押さえておいてほしい知識のひとつとか、発想より実装みたいな傾向を感じた。結果は、まるで進歩が見られない。自分だけ前に進んでいないのだからそれは後退と一緒。■A 問題 G1。数えます。■B 問題 Reverse Proxy。シミュレートします。■C 問題 Rotatable Array。rotate をシミュレートする代わりに先頭へのポインタを動かす。添字の１始まりと０始まりの差を埋めるために N+1 要素の配列を用意してサンプルが合わずにグダってしまった。正しい対処法は、N 要素の配列を用意して、先頭へのポインタの初期値を N-1 にすることだった。■D 問題 XOR Shortest Walk。先々週の ABC408-E「Minimum OR Path」の OR が XOR だったら……という仮定がコンテスト後に見られました。期待に応えて？ 閉路でどうなるかなと思ったけど、チカチカするだけだった。「だけ」といってチカとチカとチカの組み合わせは２のべき乗で増えていくのだけど、それとは関係なく頂点数 1000 に対して状態数が 1024 なので、全部やって間に合います。1<<10 を計算して確かめたので間違いない(あまり見慣れない制約なので 10 ビットとゼロ３つの対応が思い出せなかった)。■E 問題 Battles in a Row。体力の高さと魔力の高さはトレードオフの関係にあるので、体力に対して最大の魔力を記録する DP をした。２乗が間に合う。ところで、「体力に対して最大の魔力を記録する DP」のどこが「体力の高さと魔力の高さはトレードオフの関係にあるので」なのかは判然としない。本当は「HP が低くなるなら MP は高くならないといけないよ」という DP をしようとしたのだけど、実装が混乱したので一旦すべての HP をフラットに扱う素直な実装を書いて、それをそのまま提出したのだった。■F 問題 Balanced Rectangles。対角を決めれば中身は数えられる。問題は対角の選び方が２乗のオーダーになること。どうやって効率良く数えるのかわかりません。短い方の辺の２乗なら許されるとしても、長辺方向の累積和で何もうまくできない。■G 問題 Longest Chord Chain。ABC402-D「Line Crossing」、ABC405-F「Chord Crossing」から続く３問目。おかげで問題の把握は容易。まずある弦を選ぶ。その右側と左側に対してそれぞれ平行な(平行になるように移動できる)弦が最大何本選べるかがわかればいい。これは再帰的に DP で求められる。わからないのは、左右にあるどの弦が再帰の次のステップとして最適か。これを逐次的に選ぶのでは全体で２乗のオーダーになって間に合わない。次のステップの候補が連続してすきまなく並んでいるのならセグメント木に載せて最適解を対数時間で選べるが、左右を分ける弦と交差する弦をクエリ範囲から取り除かなければ誤った答えを選んでしまう。ということを今この日記に書いていて思ったのだけど、交差する弦をセグメント木から一時的に除外することが可能なのではないか。除外したり復元したりの回数は全部で 2N 回なのでは？ この思いつきを実装しようとすると、弦に対して交差する弦のリストを作成すること、再帰の末尾に当たるどの要素からセグメント木を埋めなければいけないか、範囲の左右を分ける区切りとセグメント木の先頭末尾の区切りの不一致から扱う範囲が実質的に３つになることなど、気が遠くなるほど道のりが長い。２乗の解答を書くだけですでに疲弊しているというのに。しかもこの２乗の解答が (TLE に加えて) WA を出す可能性が６、７割くらいあると思ってるよ。それだけややこしいし、方針にも確信が持てない。■■■F 問題。この累積和の使い方、解いたことある。ABC338-G「evall」(「範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題」)。次元がひとつ増えるだけでキャパシティをオーバーして、できることとできることの足し算ができないことになってしまうのでした。提出 #66801656 (TLE×20/AC×23)。ダメです。