AtCoder Beginner Contest 197（Sponsored by Panasonic）「ORXOR」纏め
AtCoderの問題を解き始めて、2つ目のコンテスト。(出場したとは言っていない)
大苦戦したので、ハマったポイントと、それに対する回答を整理したので、自己理解のために再整理しました。
今回は大苦戦した問題「AtCoder Beginner Contest 197（Sponsored by Panasonic）」の第3問「ORXOR」について、自己理解用にまとめました。
問題文
簡潔で、かつ難解な問題がこちら。
長さ の数列 が与えられます。
この数列を、 つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位 を計算します。
こうして得られた全ての値のビット単位 として考えられる最小値を求めてください。
2行目の意味
自分が良く分からなかったポイントが、2行目
この数列を、 つ以上の空でない連続した区間に分けます。
これをbit全探索を使って処理を書くらしいのですが、bit全探索って何？という私には最初からチンプンカンプン。
bit全探索を調べると、複数のtrue・falseを網羅して調べるために使う手法です。
ざっくりと別記事で整理したので、そちらを参照してください
bit全探索の意味を理解して、すぐに次の疑問。
bit全探索を使ってtrue・falseを網羅したいと言っても、何を網羅するの？
結論から言うと、数列と数列の間に区間を仕切る区切りがあるか、無いか、の状態を網羅したかったみたいでした。
説明だけだと、イメージがつかないと思うので、具体例を出すと
ａ ⋮ ｂ | ｃ ⋮ ｄ
ａとｂ、bとｃの間に区切りが存在するか、否かを網羅したいみたいです。
もう1個、分からなかったポイントが区間って2個だけじゃないの？ってところでした。
こちらの答えがNo。何個でも区間が作れます。
先のイメージに追加するなら、こんな感じですね。
ａ ⋮ ｂ | ｃ ⋮ ｄ | ｅ
aとｂで1区間、cとｄで1区間、e単体で1区間。合計3つの区間が存在します。
最大N個の区間ができるということですね。
ここまで理解するのに、3時間くらいかかりました。
マジで問題文が理解できなかった。
2区間だけと思っていた時の回答がこちら。
Submission #21467772 - AtCoder Beginner Contest 197（Sponsored by Panasonic）
サンプルはあっているのに、検証はことごとく✖なので、絶望しました。
ちなみに、問題文の3行目、4行目は問題なく理解できたので、省略します。
（多分、数学の教科書やプログラミングの教科書を漁れば、詳しい解説が出ていると思います。）
区切り判定処理は前？後ろ？
最後の詰まったポイントは区切り判定処理でした。
1個1個の区間にor演算をして、最後にxor演算をしていきます。
そのため、区切り判定をした上で
- 区切られていない場合はor演算
- 区切られて入れる場合は初期化してor演算
とする必要があります。
私が実装したのが、or演算の前に区切り判定をしてしまいました。
先ほどのイメージを用いると、
ａ ⋮ ｂ | ｃ ⋮ ｄ | ｅ
aでは区切り判定をせず、bの処理の前に区切り判定！cの前で区切り判定！みたいな感じで実装していました。
結果は概ねOKでしたが、1個だけNGになりました。
「ふぁ～、1個だけNGとか意味分かんね～」となりましたが、ここまでさらに2時間…もはや、意地になって調べました。
詳しくはソースコードを読んで欲しいのですが、NGだったのは「Nが1の時に処理がスキップされてしまう」
結果として、1件NGとなり、失敗しました。
この時のソースコードがこちら。
Submission #21478308 - AtCoder Beginner Contest 197（Sponsored by Panasonic）
先ほどのソースと違いコメントアウトが大量に書いているのは、マジで、ここまでしないと理解できなかったです。
最終的に、区切り判定をor演算の前に持ってきて、無事成功しました。
最終的なソースコードはこちらです。
Submission #21487697 - AtCoder Beginner Contest 197（Sponsored by Panasonic）
今まで1問あたりそんなに時間かからなかったのに、まさか6時間クラスになるとは夢にも思っていなかったです。
同じ挫折を味わう人がいた時の参考になるように、自分の詰まったところを整理しました。
