脳log[20240427]

2024年04月27日 (土) [AtCoder] 今日は AtCoder Beginner Contest 351 があった。コンテスト成績証。自分のすべての提出。ABCDF の５完でレートは横ばい。E 問題が難しかった。ではふりかえり。■A 問題「The bottom of the ninth」。問題文に書いてある通り、９回裏が必ずある。場合分けはいらない。１点上回るのに必要な点数。■B 問題「Spot the Difference」。唯一の相違点の座標を答える。座標が１始まりなんだよね。添字と１のずれがある。それで思いついてしまったんだけど、サイズを答えにすればずれの補正がいらない。つまり、後ろの方から一致している行を取り除いていくと、相違点のある行までが残る。残った行数がそのまま１始まりの座標になる。列番号も同様に末尾から削っていくと、残った文字数がそのまま１始まりの列番号になる。+1 とか -1 とかの補正って嫌いなんだよね。１か所も漏らさず完璧に補正できる気がしないし、+1 とか -1 とか見るたびにその意味を解釈させられるのが嫌だ。だから普段から無害な０番目を補うなどして補正の必要をなくすようにしている。メモリの方が自分の脳みそよりローコストだから、余分な１要素をケチる理由がない。入力を１回だけ補正して変換するという手もあるけど、そうすると実行結果とサンプルの解説文とでずれが生じるので避けたい。■C 問題「Merge the balls」。えっと、やるだけなの？ 罠とかない？ と警戒したけど、これは C 問題だった。では油断してそのままやります。２つの数を足す操作が +1 することを意味するというのがちょっとしたフックかな。掛け算が log の足し算になるみたいな。■D 問題「Grid and Magnet」。本日の実装枠でした。といって簡単というわけでもなかったと思う。基本は BFS、DFS もしくは UnionFind で連結成分の大きさを求めるんだけど、移動するとそこから動けなくなる吸い付きマスをどう扱うか。最初の UnionFind のステップでは吸い付きマスを壁として扱い、その後のステップで隣接している吸い付きマスと連結成分を一体として大きさを数えるようにした。気をつけたいのは、幅１の吸い付きマスが２つの連結成分を分断しているとき(そう、分断するんですよ。UnionFind をするときに吸い付きマスを使って連結してはいけない)、その吸い付きマスは両方の連結成分に対して寄与がある。どちらか一方だけに所属させてはいけない。前半のステップでも後半のステップでも吸い付きマスの特別扱いが罠になり得る。簡単ではないよ。■E 問題「Jump Distance Sum」。解けなかった。dist(Pi,Pj) がゼロになるのはチェス盤をイメージして２つの点が異なる色のマスにある場合。そうでない場合に dist(Pi,Pj) は X 座標の差と Y 座標の差のうち大きい方になるみたい。ある点を中心として座標空間を十字に区切ると、X 座標の差が dist になる範囲と Y 座標の差が dist になる範囲がそれぞれ２つずつ。BIT を２つ使って、ある座標までにある点の数の和と、座標の和を管理すれば、ある座標を中心として左右にある点との距離の和が効率良く求まる。ちなみに今日の F 問題がそういう問題だった。でも E 問題ではそれができなかった。点は左右だけではなく上下にもあり、X 座標と Y 座標のどちらか決まった方を dist の計算に用いなければいけないが、その分別が効率良くできない。■F 問題「Double Sum」。すごく安心感のあるおなじみの問題。もう５回も６回も書いてる気がする。BIT で値の和と値の数を管理する。Ai<=Aj を常に成り立たせるために昇順もしくは降順に A 数列を処理する。