脳log[20241214]

2024年12月14日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#12（ABC384）があった。まずまずのでき。ABCDE のふりかえりと F の精進を。■A 問題 aaaadaa。言われた通りに。正規表現を使った置換だと一発だったのかな。操作が否定で定義されていて結局何をするのかよくわからなかったので言われた通りに。■B 問題 ARC Division。言われた通りにシミュレート。■C 問題 Perfect Standings。なにげにやっかいなのが同点での名前辞書順。得点と名前のペアでソートしてから名前を出力すれば良かったんだけど、名前に変換する前の数値の状態でソートして間違えた。一番複雑そうなサンプル３の出力だけ比較して一致することを確かめていたのだけど、厳密な比較をサボったそれ以外の２つのサンプルがどちらも合っていなかった。１ペナ。■D 問題 Repeated Sequence。数列を前から順番に処理しながら現在の要素を終端とするすべての累積和を列挙することができる。あとは N 項の和の余りをとったり、A 数列を２サイクル処理したりすることに注意する(数列を１周以上するケースや、N=7 のとき、A6+A7+A1+A2 のような累積和を対象に含めるため)。■E 問題 Takahashi is Slime 2。高橋くんスライムに隣接するマスをプライオリティキューに入れて、最小のものから取り出して併合する。■精進。F 問題 Double Sum 2。えっとね、つい最近、この問題と全く同じように数列を 0/1 で分類して数え上げる問題が出たと思うんだよね。時間外に考えてみてそれでも解けなかった問題なのでこの F 問題も解けないのがある意味当然だったのだけど、今日は時間はオーバーしたけど AC までたどり着けた。まず、trailing zeroes の数が異なる要素同士の和の f 値は簡単に求まる。一致するもの同士をどうするか。末尾の 1+1 の繰り上がりを考慮に入れたうえで、その次のビットを見る。一致していればそのビットが１に確定し、f 値が計算できる。異なっていれば、繰り上がりを考慮したうえでさらに次のビットを見る。提出 #60779596 (AC / 882 Byte / 608 ms)。数列を１つとる F 関数をまず書くんだけど、それにくわえて数列を２つとる FF 関数が書けるかどうかが AC に至れるかどうかの分かれ目だった。FF 関数に２つの数列をビットで分類した４つの変数 a0,a1,b0,b1 がある。10 通りの組み合わせのうち、a0×b0, a0×b1, a1×b0, a1×b1 の４つは答えに計上するけども、a0×a0, a0×a1, a1×a1, b0×b0, b0×b1, b1×b1 の６つは答えに計上してはいけない(これらはすでに F 関数で答えに計上されているので)。このように、0/1 で分類して 0×0, 0×1, 1×1 の組み合わせについて答えを計上する F 関数と、似ているけど異なる FF 関数がなかなか書けなかった。F 関数は FF 関数を呼ぶけど、FF 関数は FF 関数を呼ぶ再帰関数なので、FFFF 関数を定義する羽目には陥らないということも見通せなかった。F 関数の要求からとりあえず FF 関数を定義してみて、FF 関数が要求するものは FF 関数だったのでめでたしめでたしという流れ。■これかな？ PAST18-K「2で割り切れる回数」。解けなかったんだよね。シグマの範囲がちょっと違うだけで同じ問題だ。今なら解けるだろうか。ちなみに、Ruby で 81 バイトで解けるらしいです(#60224722)。通った。提出 #60784486 (AC / 650 Byte / 301 ms)。長さから判断するに明らかに不器用な数え方をしているけども、今日の F 問題と同じ構成で解けた。F 問題も K 問題も制限時間が４秒５秒なんだけど、想定解法ではない？ １秒しかいらないよ。