脳log[20231111]

2023年11月11日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)があった。自分のすべての提出。くやちい。たいへんくやちい。なんてことのない F 問題を通すのに２分６秒ぽっち足りなかったのがくやしい。重み付き UnionFind のややこしさは知っているつもりで、結合する２つの頂点を縛る重みとそれらの根の重みを混同する落とし穴にはすでにはまったあとなので気をつけることができる。もちろんじっくり慎重に考える必要はあって、それでも一度は間違えて修正したのだけど。時間内に取り切れなかったバグはね、手癖で書いてる根の交換。効率良く集合をマージするためにサイズを見て根を交換することがある。根っこだけしか交換してなかった！ あほ！ ではふりかえり。■A 問題「Not Too Hard」。フィルタして足す。コーナーケースは足す数がゼロ個のとき。サンプルの３にちゃんとあるが事前に読めていた。■B 問題「11/11」。ありうるぞろ目は割りと少ないのだけど、総当たりをしてもやっぱり少ないので間違いにくいやり方をすればいいと思う。10 で割った余りで桁 d を取り出したら許される月・日は d か dd しかない。■C 問題「Consecutive」。累積和で数えるんだけど、範囲の内と外で接している２文字の一致を数えてはいけない。すごーく考えて累積和の左右の添字を決めた。８分。■D 問題「Take ABC」。下手なことをすると TLE かと思わせるけど、削除が連鎖することはないので貪欲に操作をすればいい。新しい文字列や新しい配列を操作のたびに作るような初歩的なミスをしない限りは大丈夫。■E 問題「Modulo MST」。制約がものすごく小さいので総当たりができる。だけどやっぱり AtCoder の問題なので、頭の悪い総当たりは許してくれない。はい、頭が悪いです。最終的に辺を総当たりで N-1 個選ぶ DFS を書いた。TLE を１回出しながら１時間かけて書いた。combination メソッドを使ったステートレスな判定が書きやすく理解もしやすいけど、TLE だったので DFS で漸進的に処理を進めなければいけなかった。制約をガイドにして解法を決めているきらいがあるので、制約がゆるゆるだと途方に暮れがち。そして E 問題で無意味にゆるいことなんてない。■F 問題「Good Set Query」。問題文が難しい。でもまあ苦労して読むと、長さ N の数列に対して、Q 個の制約を順番に、条件を満たす限り貪欲に追加していくという流れらしい。制約が連鎖している要素の全体に対して、基準点を内部に選んで基準との差分で制約を持つと効率良く判断ができる。見え見えの重み付き UnionFind。だけど残り 25 分では書けなかった。バグ取りに２分６秒足りなかった。■F 問題までのどこに難しい問題がありましたか。あほがいただけ。手も足も出ない難しい問題でたたきのめしてくれた方が慰めがあるってもんよ。