脳log[20220217]

2022年02月17日 (木) [AtCoder] 精進。先週末の ARC135-C「XOR to All」(水 diff)。XOR なのでまず考えたのはビットの分離。最大で 30 ある各ビットが A 数列を通していくつ立っているかを数えた。その数が N の半分より多いならそのままで、半分より少ないならビットを反転させたとして最大値を計算してみた。サンプルの１が合わない。どうやらビットごとに好きなビットを立てたり下げたりすることはできなくて、ビット間に拘束条件があるらしい。しばらく具体的に考えてみた。Ai を作用させてみて、Ai を作用させた Aj を作用させてみて……、そうすると Aj を作用させた段階で最初に作用させた Ai の効果が消えるなあ、と。提出 #29378726 (TLE×31)。これがコンテスト終了１分前の提出でなければ効率を考えて清書することができた。TLE の背後に WA が隠れていたりはしなかった。■提出 #29378726 (AC / 253 Byte / 1197 ms)。提出 #29378845 (AC / 202 Byte / 990 ms)。■以前日記にこう書いた。「コンテストの時に限って頭ヨワヨワの神経衰弱になること、あると思います」。この問題に当てはめるとそれはこう。「制約に Ai が 2^{30} 未満ってあるけど、Ai が取り得る値は 30 ビット符号無し整数の範囲だろうか、それとも 29 ビットだろうか。2^{30} は 1<<30 だろうか 1<<29 だろうか。(1<<30).bit_length は 31 かな、30 かな。Ruby で Integer#[] メソッドを使って整数の右端のビットを得るときの引数は(たぶん) 0 だから、引数の範囲は 0..29 だろうかそれとも 0..30 まで必要だろうか。ぐるぐるぐるぐる」 添字と序数とサイズと左シフトの回数がそれぞれ微妙に異なっていたり一致していたりするのに答えが出せなくて、無為に時間が過ぎていく現象のこと。