脳log[20240504]

2024年05月04日 (土) [AtCoder] 今日は AtCoder Beginner Contest 352 があった。E 問題までの解ける問題を解きましたという感じ。たぶん精進として粘れば F 問題も解けなくはないのかなと思うけど、まずは WA がどういう思い違いから生じているのかを探る必要がある。ではふりかえり。■A 問題「AtCoder Line」。範囲に含まれるかどうか。大小関係が制約により規定されているわけではないことに注意。■B 問題「Typing」。B 問題にしてはいかつい制約(20 万)だけど、まあ、やります。T をスキャンしながら S の現在位置との比較を行う。■C 問題「Standing On The Shoulders」。肩の高さは常に答えに寄与する。頭の高さ、というか、肩より上に出る頭の高さは１つだけが答えに寄与する。合計足す最大値が答え。■D 問題「Permutation Subsequence」。結構考えました。そもそも記号混じりの問題文という時点で理解に時間がかかる。理解した内容はこう。K 幅の順列を考える。１から K とか、2 から K+1 とかの。次にそれらが入力 P の中でどの位置にあるかを考える。必要なのは最も左にあるものと最も右にあるものの差。これの最小値が答え。D 問題だからスマートな解法があるのかなと思いつつ、考える時間を惜しんで BIT でなぐりました。幅 K のウィンドウをスライドさせながら、入ってきた要素の位置を +1 し、出て行った要素の位置を -1 すると、値が１の位置(最も左にある要素の位置)と値が K の位置(最も右にある要素の位置)を BIT に尋ねることができる。■E 問題「Clique Connect」。愚直に辺を繋いでいくことはできない。扱う要素数は最大で 40 万だけど、その組み合わせは２乗の数になる。最初に最小全域木を求める操作をした。コストの短い辺から順番に、繋げられるけどまだ繋がっていない要素をどんどん繋げていった。これは組み合わせではなく、テキトーに選んだ１つの要素に他のすべての要素を繋げていく操作。それをコストの昇順に繰り返して最後に全体がひとつになっていればコストの合計を答え、そうでなければ -1 を答えにする。■■■@2024-05-05 F 問題の WA が減らないので代わりに D 問題を BIT で殴らない方法。提出 #53178338 (AC / 405 Byte / 123 ms)。配列を２本使うだけなので短いし、BIT だと付く log も付かない。スライド最小値とかいう名前がついてるのかな。初めて参加した AGC が AGC038 なんだけど、時間内に解けなかった B 問題 Sorting a Segment への他の人の提出を研究する過程で見つけたのがこれだった。ソースコードで学んだので名前は後付け。20190922p01。じゃあ昨日の ABC352-D が解ける人は青 diff だった AGC038-B も解けるね。■■■@2024-05-06 F 問題。ほんの２週間前に「重み付き UnionFind の実装は死ぬほどややこしい」と書きながら ABC314-F の精進をしていたのだけど、そのときは時間をかけながらも１発で AC になっていたのだけど、今回の問題は５つも６つも実装ミスが重なって５回も WA を出していた。すべては実装ミスだった。提出 #53204970 (AC / 1169 Byte / 174 ms)。後半にビットを埋める総当たり(メモ化あり)があるので N の制約が 16 以下と小さい。だから前半の UnionFind を定型から外れて雑に書いてバグり散らかしていたという話。制約が小さいならサイズやランクを見る必要ないもんね。そしてもちろん後半部分にバグがなかったというわけでもない。実装が下手。頭の中が散らかっている。■F 問題の解法について書いていなかった。パズルのピースを組み合わせるイメージ。相対的順位差で関係づけられたいくつかのグループがパズルのピース。３人の人が１つ飛ばしの順位だったなら、このピースは 10101 で表せる。全部で５人なら、これは 1-3-5 位しか考えられないが、全部で 10 人なら 2-4-6 位もありうる。しかし全部で 10 人いて他に 101011111 というピースがあるなら、やはり 1-3-5 位しか考えられない(※ MSB を１位としました)。こうなってくるととりあえず全部を試してみるしか答えを出す方法はないよね、という気持ちになる。１階層ごとに特定の１ピースを埋める DFS をやるんだけど、DFS の呼び出し経路には関心がない。どういうことか。１階層目と２階層目が受け持つピースがどちらも 1 と 1 という形だったとする。３階層目のピースにとって関心があるのは、そして結果に影響するのは、どのビットが空いているかということだけなので、同じ２ビットのどちらとどちらを１ピース目と２ピース目が埋めているかという情報には関心がない。むしろ積極的にその区別を捨てて結果の使い回しをしたい。メモ化です。というわけで、前半ではピースの形を確定する UnionFind を、後半ではピースを N ビットに隙間なく埋めるメモ化再帰をする２段構えの問題だった。要素技術は F 問題までで身につけているはずで、組み合わさったことで F 問題だったのかなと。G 問題ではないなと。ならこれも実装問題だったのか。突破できませんでした。腕力が足りない。■他所で見かけたのでここでも書くんだけど、置きにくいピース(※)から置くような小細工を WA だった最初の提出から行っている。これをやらなくても TLE にはならないだろうけど、とにかく答えを見つければいいという DFS の場合、優先順位を付けて早期に判定ができると劇的に実行時間が縮まることがあって気持ちがいいので、とりあえずやってみて沼にはまるのがいいと思う。その先にヒューリスティック沼があるかは知らない。この問題では、再帰を深く潜ってからやっぱりだめでしたーと判定されていたかもしれないものが、比較的浅い階層で無理だと判断できるようになる効果があったと思う。※置きにくいピースを短絡的にビット長の長いものとしたけど、ポップカウントもいい指標になりそうだと気がついた。1000001 と 1111 のどちらが置きにくいかという話。自分が明確に誤っていたのは、ビット長が同じでポップカウントが異なる 110001 と 101111 の比較で、単純に数値比較で大きい方(最初の方)を置きにくいと判断したところ。小細工だしフレイバーなので許される手抜きだとは思うけど。