脳log[20230923]

2023年09月23日 (土) [AtCoder] 今日はサントリープログラミングコンテスト2023（AtCoder Beginner Contest 321） があった。コンテスト成績証。自分のすべての提出。ABCDE の５完遅解き。今回のネックは C 問題と E 問題だった。それぞれ 21 分と 56 分(＋ペナ５分)かけている。これは考えていた時間ではない。ひたすらに実装が下手だった。脳内イメージをコードにするプロセスがバグっている。ではふりかえり。■A 問題「321-like Checker」。はい。■B 問題「Cutoff」。制約が 100 以下とささやかなので素直に愚直解を書く。■C 問題「321-like Searcher」。K に１以上以外の制約がないことの意味をしばらく掴みかねた。だから文字列で答えを構築する必要があるのかなとか考えていた。そうとしても読み込む前に K が 64 ビット整数だとは知らせてほしい。なぜなのか。問題の不備なのか。最大の 321-like Number が 9876543210 だというだけのこと。全列挙すればいい。その列挙に 21 分かける自分のおつむに絶望するんですよ。言い訳をするなら、0 と空文字列が現れないようにきれいに列挙することができなかったという事情がある。無視すればいいだけなんだけどね。他所で読んだんだけど、321-like Number とは "9876543210" の部分文字列のことだった。そう捉えられたらもっとスムーズにコード化できただろうなあ。２の 10 乗通りの部分文字列に 0 と空文字列が現れるのも自然なことだとすぐわかる。■D 問題「Set Menu」。考える要素はどこにもない。ソートして P 以上になるペアを弾いて、残っているものの総和と P をいくつか足す。……という処理を一方の数列の各要素ごとに他方の数列に対して行う。両方の数列をソートしておくなら二分探索はいらない。AC まで４分。■E 問題「Complete Binary Tree」。セグメント木をイメージすればいい。ただし要素数が２べきに揃えられてはいない。K の上限が N-1 になってるけど、実際にありうる上限はセグメント木の高さ×2 なので 2log(N)≦2log(10**18)<120。10 万あるテストケースごとに K を変化させながら木を辿って構わない。あるノード k があるとき、これの d 階層下のノードは 2**d*k 以上 2**d*(k+1) 未満の番号を持っている。N と比較すればいくつのノードが該当するかは簡単に数えられる(はずだった)。与えられた X から根までさかのぼりながら、直前までいたノードと逆のノードの下にいくつ当てはまるノードがあるかを数えていく。根に辿りつくまでのあいだに K がゼロになったらそのノード自身をひとつ数えて終わりにする。やりたいことは最初から明確で大枠はすぐにできあがったけど、細部がひたすらバグっていた。最後まで残っていたバグは、「(根までさかのぼりながら、)直前までいたノードと逆のノードの下にいくつ当てはまるノードがあるかを数えていく」処理における「逆のノード」。直前までいたノードが N 以下なのはたしかだけど、逆のノードは必ずしもそうではない。d 階層下にばかり気を取られていて完全に盲点でチェックが漏れていた。ここでの教訓は「ステップも場合分けもまとめられるものはまとめた方が良い。式が３つあればバグは３か所に潜むし、場合分けにより実行パスがテストケースごとに分かれてしまうと、実行されないパスのデバッグ機会が限られてしまう」。d 階層下の処理とゼロ階層下の処理を分けたのが良くなかった。自分で書いたことなので当然わかってるんだけど、コンテスト中は時間に追われるからきれいに完璧に書くことの優先度が下がってしまう。それで AC が遠のいてたら本末転倒急がば回れなんだけど。■F 問題「#(subset sum = K) with Add and Erase」。残りのわずかな時間で考えていた。最初は O(N^2) だと勘違いして愚直に DP をするものを書いた。TLE だった。そうすると DP 配列を使いまわして巻き戻しをする必要があるなと、消去法のように考えた。でもそんなんやったことないし、できるかも知らない。残り１、２分くらいで書き直したものは引き算し過ぎでマイナスの数字(modulo に近い数ということ)が出ていた。