/ 最近 .rdf 追記 編集 設定 本棚

脳log[20220820]



2022年08月20日 (土) [AtCoder] 今日は ARC146 があった。それほど悪い日ではなかった。A 問題「Three Cards」を丁寧にそこそこ早く書いて9分で AC した>提出 #34165283。ちなみに灰 diff。B 問題「Plus and AND」(水 diff) は時間中には 307 ms オーバーの TLE 解しか作れなかった。Crystal なら通っていたと考えることもできるけど、終了15分前の2完遅解きと1完早解きでは期待するほどのパフォーマンス差はないので、終了後でも AC できたのが良かった。■B 問題解答の紆余曲折。提出 #34170444 (WA×55)。最初の提出は派手に間違えた。サンプルの1を見ると、解が X のとき、K 個の A 要素が A&X==X になることがわかる。X に立っているが A に立っていないビットがその要素に必要な操作回数であり、A に立っているが X に立っていないビットが節約できる操作回数だと考えて式 b = a^x; (b&x)-(b&a) を書いた。これの間違いは A の方が X より大きな MSB を持つときに、それを操作(足し算)回数の節約には利用できないし、ましてや負の操作回数によって操作回数を貯金することもできないのにしてしまっているところ。■提出 #34171598 (WA×4 / TLE×10)。さっきの提出の修正版。BIT の添字の操作と同じように LSB を順番に取り出して、節約できる操作回数を正確に数えるようにした。WA が大幅に減って TLE が生じてるのはその結果。ではすべてが TLE になるのではなく依然として WA が4つあるのはなぜか。解を二分探索しているのだけど、MSB が異なる2つの解を比較したとき、ある要素 A にとって小さい方の解では無視されたビットが大きい方の解では操作回数の節約に利用できるという状況が起こりうる。判定に単調性がない。■……1時間経過。提出 #34178565 (TLE×1 / 5307 ms)。解の MSB が同じなら単調性があるわけなので高次のビットから 0/1 を決める方針。1ケースだけ 307 ms オーバーした。■終了後の提出 #34182184 (AC / 2052 ms)。判定が済んだ部分について入力のビットを折っておくことで時間の節約をした。そうすると決めて時間があれば書き換えはただの作業。■あわや緑落ちかというところまで下降しているレートにとっては1完でも +1 だったので、悪い日ではなかった。