差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0511_diverta2019 [2019/05/15] – [問題] ikatakos | programming_algorithm:contest_history:atcoder:2019:0511_diverta2019 [2019/05/16] – [解法] ikatakos | ||
|---|---|---|---|
| 行 131: | 行 131: | ||
| 累積xor | 累積xor | ||
| ~~~ | ~~~ | ||
| - | なので、累積xorを求めてDPをする。累積XOR上で「$X, | + | なので、累積xorを求めてDPをする。$a$ の累積XORを $acc$ とし、$acc$ |
| ===DP構築の考察=== | ===DP構築の考察=== | ||
| - | * 数列の末尾の1要素は必ず区間の終端なので、その累積xorは「$X, | + | * 数列の末尾の1要素は必ず拾われる。$acc$ |
| - | * そのため、累積xorの末尾が0以外の場合、それが唯一の $X$ である | + | * そのため、$acc$ の末尾が0以外の場合、それが唯一の $X$ である |
| - | * 末尾が0の場合、$X$ は累積xor上に出てくる全ての整数が候補として考えられる | + | * $acc$ の末尾が0の場合、$X$ は $acc$ 上に出てくる全ての整数が候補として考えられる |
| - | * →処理を分ける | + | * →処理を分ける |
| * $X$ は0でもよいが、実装の上で分けて考えた方がやりやすい | * $X$ は0でもよいが、実装の上で分けて考えた方がやりやすい | ||
| - | $DP[x][i][k=0/ | + | $DP[x][i][k:0/ |
| すると、 | すると、 | ||
| - | * $a_i=0$ の時 $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x]$ | + | * $acc_i=0$ の時 $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x]$ |
| - | * $a_i=x$ の時 $DP[x][i][x] = DP[x][i-1][0] + DP[x][i-1][x]$ | + | * $acc_i=x$ の時 $DP[x][i][x] = DP[x][i-1][0] + DP[x][i-1][x]$ |
| となる。言及されていないものは前の結果を引き継ぐ。（$DP[x][i][k] = DP[x][i-1][k]$） | となる。言及されていないものは前の結果を引き継ぐ。（$DP[x][i][k] = DP[x][i-1][k]$） | ||
| - | 例えば $a_i=0$ の時、新規確定無し（$i-1$ からの引き継ぎ）に加え、最後に確定した区間が $x$ だった場合から新しく区間を確定して 0 に遷移するケースを足し合わせることを示す。 | + | 例えば $acc_i=0$ の時、新規確定無し（$i-1$ からの引き継ぎ）に加え、最後に確定した区間が $x$ だった場合から新しく区間を確定して 0 に遷移するケースを足し合わせることを示す。 |
| - | ===累積xorの末尾が0以外だった場合=== | + | 直前に確定した区間 |
| + | | ||
| + | ... 0｜ ... 0 | ||
| + | ... x｜ ... 0｜ (iで新規区間確定) | ||
| + | ↑ | ||
| + | 直前に確定した区間 | ||
| + | |||
| + | ===accの末尾が0以外だった場合=== | ||
| 先述の通り、$X$ は一意に確定する。末尾の $X$ へは $DP[X][N][0]$ から遷移するので、それが答え。 | 先述の通り、$X$ は一意に確定する。末尾の $X$ へは $DP[X][N][0]$ から遷移するので、それが答え。 | ||
| - | 累積xor上で最後に出現した0の後に $X$ が複数個あろうが、条件を満たすようにするには末尾の $X$ 以外は使えない。 | + | 末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのか、と一瞬思うが、最後は必ず区間を確定するので、遷移元である0の方を見る。 |
| + | |||
| + | $acc$ 上で最後に出現した0の後に $X$ が複数個あろうが、条件を満たすようにするには末尾の $X$ 以外は使えない。 | ||
| - | $DP[X][N][X]$ は、そのような使えない $X$ も混ざった値となってしまっているため注意。 | + | $DP[X][N][X]$ は、そのような使えない $X$ も混ざった値となってしまっている。 |
| 累積xor | 累積xor | ||
| 行 168: | 行 177: | ||
| ===累積xorの末尾が0だった場合=== | ===累積xorの末尾が0だった場合=== | ||
| - | まず、$X=0$ の場合、累積xorが0の時に区切るか区切らないかを（末尾以外）独立に選べるので、$2^{0の出現回数-1}$ である。 | + | まず、$X=0$ の場合、$acc_i$ |
| $X \ne 0$ とする。 | $X \ne 0$ とする。 | ||
| 行 174: | 行 183: | ||
| $X$ は最悪 $N$ の数だけ考えられるので、$X$ ごとに上記DPを繰り返すと $O(N^2)$ となり間に合わない。 | $X$ は最悪 $N$ の数だけ考えられるので、$X$ ごとに上記DPを繰り返すと $O(N^2)$ となり間に合わない。 | ||
| - | まとめて複数の $X$ について処理することを考える。ただこれも、工夫が必要。遷移式を再掲する。 | + | まとめて複数の $X$ について処理することを考える。遷移式を再掲する。 |
| - | * $a_i=0$ の時 $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x]$ | + | * $acc_i=0$ の時 $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x]$ |
| - | * $a_i=x$ の時 $DP[x][i][x] = DP[x][i-1][0] + DP[x][i-1][x]$ | + | * $acc_i=x$ の時 $DP[x][i][x] = DP[x][i-1][0] + DP[x][i-1][x]$ |
| - | $a_i=x$ の時は $DP[x][i][x]$ だけ更新すればいいのだが、$a_i=0$ の時、愚直にやると、今まで出てきた全ての $X=x$ について $DP[x][i][0]$ を更新しなければならない。これでは計算量が減らせていない。 | + | $acc_i=x$ の時は、影響があるのが |
| + | $acc_i=0$ の時、今まで出てきた全ての $X=x$ について $DP[x][i][0]$ を更新しなければならない。これではやはり間に合わない。 | ||
| - | $DP[x][i][0]$ も $a_i=x$ の時のみ更新すればいいようにできれば、$O(N)$ にできそうである。 | + | $DP[x][i][0]$ も $acc_i=x$ の時のみ更新すればいい、ということにできれば、$O(N)$ にできそうである。 |
| - | 遷移を考えると、$x$ が出てこない間に0が複数回出てきても、その時に $DP[x][i][0]$ の更新に加算される $DP[x][i-1][x]$ の値は一律であることがわかる。（$DP[x][i][k]$ | + | 遷移を考えると、$x$ が出てこない間に0が複数回出てきても、その時に $DP[x][i][0]$ の更新に加算される $DP[x][i-1][x]$ の値は一律である。 |
| xor x x x 0 0 0 x x 0 0 x 0 | xor x x x 0 0 0 x x 0 0 x 0 | ||
| 行 189: | 行 199: | ||
| ↓ ↓ ↓ ↑ ↑ ↑ ↓ ↓ ↑ ↑ ↓ ↑ | ↓ ↓ ↓ ↑ ↑ ↑ ↓ ↓ ↑ ↑ ↓ ↑ | ||
| dpx | dpx | ||
| + | ~~~~~~~ | ||
| + | 連続した0の時にdp0に加算される値は一定 | ||
| よって「前回 $x$ が出てきてから、0が出現した回数」がわかれば、次に $x$ が出てきたときにまとめて $DP[x][i][0]$ の更新も行える。 | よって「前回 $x$ が出てきてから、0が出現した回数」がわかれば、次に $x$ が出てきたときにまとめて $DP[x][i][0]$ の更新も行える。 | ||
| - | $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x] \times (0の出現回数)$（※ $a_i=x$ の時、一括更新） | + | $DP[x][i][0] = DP[x][i-1][0] + DP[x][i-1][x] \times (0の出現回数)$（※ $acc_i=x$ の時、遅延更新） |
| xor x x x 0 0 0 ┌x┐ | xor x x x 0 0 0 ┌x┐ | ||
| dp0 | dp0 | ||
| - | ↓ ↓ ↓ 3x3↑ ↓ ↓ | + | ↓ ↓ ↓ , |
| - | dpx | + | dpx |
| - | また、末尾が0以外だった場合と同じ理屈で、累積xor上で最後に $x$ が出現した後に0が複数回出現しても末尾の0以外は使用不可なので、答えの算出に使用するのは $DP[x][N][x]$ の方。$DP[x][N][0]$ の最後の評価は必要ない。 | + | また、末尾が0以外だった場合と同じ理屈で、答えの算出に使用するのは $DP[x][N][x]$ の方。$DP[x][N][0]$ の最後の評価は必要ない。 |
| 最後までやったら、$DP[x][N][x]$ を全ての $x$ について合計したら、それが $X \ne 0$ の時の答え。$X=0$ と合わせて最終的な答えとなる。 | 最後までやったら、$DP[x][N][x]$ を全ての $x$ について合計したら、それが $X \ne 0$ の時の答え。$X=0$ と合わせて最終的な答えとなる。 | ||
