脳log[20251220]

2025年12月20日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2025 クリスマス（ABC437）があった。先週と同じように時間だけはあるのに G 問題に手も足も出ない。■A 問題 Feet。よくわからない制約。その上限にどんな意味が？■B 問題 Tombola。トンボラって何？ 愚直にやるだけなんだけど、最初に集合の引き算 A-B をして、違うから B-A をして、実は積集合 A&B が正解だったという沼にはまっていた。頭を使ってください。■C 問題 Reindeer and Sleigh 2。トナカイと橇。前回(１)は Sleigh が読めなかったということを覚えている。英語の場合 ei をエイって素直に読んでいいんですかという疑いが最初に来るので。トナカイって匹じゃなくて頭で数えたいよなあという感想を持ったのも前回と同じ。しばし考えた。考えたのはどういう DP をするか。一見するとパラメータが２つあって貪欲法が馴染まない。だから DP。DP ができる制約には見えないけど、ずるができないなら全部を効率的に考慮するしかない。それでどういう状態を持つか。考えていると、そりを引くトナカイがそりに乗るトナカイに転じるとき、引くパワーがマイナスになるのと同時に、重さもパワーにマイナスに作用するという点で影響が共通の値で表せることがわかる。じゃあとりあえず全頭引く側にまわってもらって、負の影響が小さいものから貪欲に可能な限り乗る側にまわってもらう。そこからぐだぐだ時間がかかるんですねえ。受け取るパラメータ(w,p)の順番を間違えたり、マイナスに作用する値を w-p にしてみたり w+p にしてみたり、処理順が反対だったり、いつのまにかソートが消えていたり。ああでもないこうでもないといじくって全体で 14 分かかった。解けたと思ってからの方が長い。■D 問題 Sum of Differences。ソートして累積和と個数で計算する。手を動かすだけで４分。実装が二分探索と尺取りに分かれるみたい。自分はこの程度の単純さなら尺取りの方がわかりやすいので尺取りでやっている。二分探索だと返ってきた探索結果の位置づけを off-by-one エラーに注意して吟味する必要があるが、尺取りだと尺を取る操作そのものによって扱っているものの意味づけが明確になるので悩まない。尺取り操作が複雑になる問題ではこれが逆になって、二分探索でスッとコンテキスト外から値を差し出される方がロジックを明確にしやすかったりする。 ■E 問題 Sort Arrays。問題文が難しい。「言い換えると……」があまりにも親切。それなしでは理解できなかった。時間大丈夫かなと不安に思いながらとりあえず 12 分で出したものは WA だった (TLE はなし)。手元ですぐにダメケースが作成できた。それは異なる Ai が同じ列である場合。再帰関数で実装したので自然と DFS 順に答えが出てくるのだけど、同等の数列を束ねる BFS 的な処理順も必要だった。完全に BFS というわけでもなかった。難しいよー。結局追加で実装に 14 分かけた。合わせて 26 分＋ペナルティ５分。■F 問題 Manhattan Christmas Tree 2。45 度傾けるというあれですか？ 傾け方はよくわかりませんが、見たことのある x+y と x-y のそれぞれに対して最大値を取得するものと最小値を取得するものの２通り、全部で４つのセグメント木を用意して、やってみたらサンプルが合ったので提出して AC。手を動かすだけで 14 分。■G 問題 Colorful Christmas Tree。２乗が許される制約。木 DP でできるんかなというかそれ以外にやりようが思いつかないんだけど、３値の子供の処理順をやりくりするだけでもたいへんなのに、どこに親との辺を取り除く処理を挟むかという可能性まで関わってくると整理しきれない。おてあげ。■自分のすべての提出。手も足も出ない G 問題を前に時間を持て余していたのが先週と同じだったように、順位とパフォーマンスも前回と似たものだった。前回と違う点を探すと、６完最速との順位差が 200 番程度ではなかったということ。なんと６完最速は順位表の２ページ目、38 番にいる。今日は G 問題の崖が一際険しかったと言えそう。F 問題を 1500 人以上が解いているのは先週今週変わらず。■■■匹と頭について。検索すると一筋縄ではいかない。まず伝統的には匹のみが長く使われていた。特に馬と匹の結びつきが強い。しかし頭がある現在は、大型の獣にはもっぱら頭が使われる。しかし対象が小型でも頭が正式に採用されているケースがある。つまりどちらをつかっても間違いではない。現代的な感覚で判断すると頭になるというだけのことだった。