脳log[20240803]

2024年08月03日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）があった。解けるはずの D を落として ABCE の４完。F も G も歯が立たず。■A 問題「Leap Year」。どんどんネストを深くしていくこともできるし、ガード節を並べるみたいにもできる。leap? メソッドを使うこともできたみたいだけど、仕様の異同を確かめるのも無視するのも避けたい。■B 問題「Second Best」。max_by メソッドに引数を渡す。■C 問題「Transportation Expenses」。二分探索をして下さいと言われているように見えて、実は二分探索は必要ない。だけど二分探索をしないことでタイムが縮んだりしなかったのは、最初に A 数列をソートしていたからだった。無駄にややこしい解法を選んだかもしれない。■D 問題「AtCoder Janken 3」。最初の提出が WA だった。表か裏の２択だと思ったけどそこまで単純ではなかった。そこで無駄に考えすぎて SS.SPP.PRR.RSS... という順方向の並びと S+R+P+S+.. という逆方向の並びの連鎖を考えなければいけない気がして、こんなん ARC でしょと困惑していたのだけど、実は直前の手が何であったかという３状態の DP なのだった。AC は終了３分後。初手を間違えたあとのデバッグと方向転換が苦手すぎる。■E 問題「Xor Sigma Problem」。ビットごとに累積和を考えるだけなんだけど、０と１を反転させるだけの操作ができないんですよ。なかなかサンプルが合わなかった。■すべて 35 ℃を超えている室温が悪い。自分のすべての提出。■■■精進@翌日。F 問題「Takahashi on Grid」。位置の管理を BIT でやりたいとはコンテスト中に考えていた。でも L..U の範囲から外れた点をぞろぞろと移動させる方法が思いつかなかった。一日経ってもう一度考えたら重み付き UnionFind で集団大移動ができる。だいたいの点は L か U というエッジに寄せられて集団を作るので、代表点だけを動かして代表点にコストを計上する。各点のコストは代表点からの相対。エッジに寄らない点はコストがかからない点なので、ありがたく無視する。手段がわかればあとはやるだけ。std::map がない Ruby ではいくつもの道具を組み合わせてクエリの集団を Y 座標でソートした状態を保たなければいけないのが面倒で間違えやすい。■提出 #56361608 (AC / 2193 Byte / 2675 ms)。お風呂でエアコーディングを済ませていたのでばっちり２時間半(！)で AC ですよ。どうやってこれをコンテスト時間内に完成させられるんだ……。sx<tx を勝手に仮定していただとか、Y 座標の移動コストばかり気にしていて X 座標の移動コストを忘れていただとかの細かいバグはすぐに修正できたけど、一番難しかったバグが重み付き UnionFind の Find 関数にあったもので、１時間以上苦しんでいた。重みを更新するのにあたって条件が必要だとは思わなかった(58 行目)。このバグがあってもサンプル３の１つのクエリ以外は答えが合うのが怖い。サンプルが仕事をしていてたいへん助かりました。あとは BIT を使うにあたって座圧をさぼったら２つのケースで最長 221 ms 制限時間をオーバーして修正に 20 分。どうやってこれをコンテスト時間内に完成させられるんだ……(２回目)。■F 問題。Ruby での提出一覧を見たらもう AC を出している人がいた。提出 #56324651 (hmmnrst さん / 1304 ms)。自分の倍早い。中身を見たら GridRange と SegmentTree という、自分とは違う道具立て。セグメント木は BIT のスーパーセットだということで共通点はあるけど、GridRange ってなんぞ？■セグメント木を昨日考えなかったわけではない。一度 L か U に寄せられた点は以降決まったルートを辿るわけで、中間をすっとばしてゴール地点 X=tx における Y 座標が１つか２つ求められる道理。それができるのがたぶんセグメント木。ゴール地点において Y=ty との差分をコストに計上するのも簡単。でもスタート地点 X=sx における Y=sy が扱えなくて行き詰まった。sy は L でも U でもない。それをうまくやる方法があるということなのかな。セグメント木に何を乗せるかだよな。クエリに答えるのに都合のいい情報。わからん。