脳log[20250517]

2025年05月17日 (土) [AtCoder] 今日はパナソニックグループ プログラミングコンテスト2025（ABC406）があった。■A 問題 Not Acceptable。やります。比較方法はいろいろ。配列で比較してもいいし、３回比較してもいいし、単位を揃えて比較してもいい。■B 問題 Product Calculator。どうやって桁数を知るか。Integer#digits を使ったけど、10**K と比較するのが無駄がなかったみたい。他の人の提出で知った。■C 問題 ~。にょろ。each_cons(3) で極大値極小値の座標をメモして、each_cons(4) でその座標４つから答えを数えた。たとえば、i<j<k<l が連続する４つの極大値極小値の座標だとすると、左端の候補が i から j-1 まで。右端の候補が k+1 から l まで。掛け合わせたものが j,k の位置に山と谷を持つ連続部分列の数。これでサンプル３の答えが過大になって困ってしまった。デバッグプリントで確かめてもバグがなかったので問題を読み直してみると、「A1​<A2​ である」という条件を忘れていた。P[i]<P[j] を確かめて解決。ところで、波ダッシュにはこういう話題がある。「UnicodeのWAVE DASH例示字形が、25年ぶりに修正された理由」。自分は何事も雰囲気でいい加減な人間なので、チルダも波ダッシュも全角チルダも同じようなものだと思ってるし、波が上がってから下がるかも下がってから上がるかも全く区別するつもりがない(できない)。この問題もそうであったらデバッグのための５分10分が節約できたのになあ。■D 問題 Garbage Removal。列の情報と行の情報を分けて管理する。罠がいくつか。グリッドが H 行 W 列。(i,j) は上から i 行目で左から j 列目のマス。(Xi,Yi) は i 番目のゴミの座標。説明がまわりくどくて無駄に文字が増えてるうえにその文字がかぶってる。(i,j) の説明は省いて (Xi,Yi) が上から Xi 行目で左から Yi 列目のマスだって説明すればいいじゃない。X と H、Y と W の対応もいやらしい。管理する情報はゴミの行から列、列から行と、すでに片付けられた行と列。同じ行(列)を何度も片付けようとすると TLE になるので(なったので)、片付け済みかどうかをまずチェックする。片付け済みフラグを管理する代わりに行から列、列から行のデータを削除可能な集合にして、リンクさせて管理するのが素直な解法だったっぽい？ 最初にそれを配列にしてしまったから対になるデータを同期するのが無理だと思ったんだよね。■E 問題 Popcount Sum 3。たとえば問題が 0b1111111111 以下の整数 x についてだったら数えやすい。実際に与えられる N はそうではない。過去問を解くときに十分に苦しんできたので、どうすれば漏れなく重複なく数えられるかは知っている。倒すビットを１つ選ぶ。それより上位のビットは N のものをそのまま維持し、それより下位のビットは 00...00 から 11...11 まで好きに選んでも N より小さくなる。固定された上位のビットと好きに選べる下位のビットの組み合わせで答えを数える。「N 以下」なのでビットを１つも倒さないケースも忘れず勘定に入れる。その方法だけど、N のケースを個別に数えるんでなく、N に予め１を足しておくだけで良かったっぽい？(「例の20は1足して21にすると考えやすいです」) ビット表現に即して考えているときにその表すところである数に意識を切り替えるのは難しい。ところで、数えるものは個数ではなかったんだよね。サンプルが合わないから読み返したら太字で総和って書いてあった。ちょっとひとひねりという感じなので、冷静にひと手間かければ個数を総和に変換できる。ひとひねりでてきめんにやられるのが自分ですけどね。ひと手間というのは、好きに選ぶ各ビットの寄与(１少ない桁数から１少ない１のビットを選ぶ場合の数)を考えること。■F 問題 Compare Tree Weights。HLD なのかな、平方分割チックに木をブロックに分割するのかなと考えるもまとまらなかった。スター型の木と直線の木を同時にうまく扱う方法がわからなかった。X でオイラーツアーと BIT だと複数見かけたけど、まだピンと来ていない。■G 問題 Travelling Salesman Problem。ABC273-F「Hammer 2」みたいな雰囲気を感じます。考える意味のない無駄な動きを除外してうまくやりたいけど、うまい動きがどういうものかはっきりしない。ちなみに ABC273 は３年前のパナソニックのコンテストでした。偶然ではないとしたら本当に似た問題なのだろうか。Hammer 2 は右左右左と往復を繰り返すことで効率良く解ける問題だった。制限時間が３秒だけど Ruby で 62 ms で解ける。……むしろ今日の C 問題？■■■精進。F 問題。提出 #65938315 (AC / 976 Byte / 1291 ms)。ひと晩寝るまで何がわからなかったか。ある区間の和を得るには端からの累積和の差を取るという、BIT(累積和)の使い方を忘れていた。オイラーツアーで木の頂点を DFS の行きがけ順に並べたら、ある頂点の子孫がある区間に連続して並ぶ。では子孫の重さの和を得るには、というときにどういう操作をするのかがわかっていなかった。なんでわからなくなるのかがわからなくもない。頂点を一列に並べてそれを BIT に乗せるとき、列に木の構造を見るばかりに BIT の各要素に過剰に意味を見つけようとしてしまうのだろう。だけど累積和の各値に木の構造を反映した意味はありません。差分を取って初めて意味が出てくる。だけど意味がわからないから差分を取るところまで行けなかった。数弱ですからね、すべて意味と具体で納得しながらでないと前に進めない。