diverta 2019 Programming Contest C,D,E問題メモ

diverta 2019 Programming Contest

• diverta 2019 Programming Contest 解説放送 - YouTube

C - AB Substrings

• 文字列が $N$ 個、$s_1,s_2,...,s_N$
• 好きな順に連結して1つの文字列にする
• 'AB' が多く含まれるように連結順を決めると、最大いくつ含めることができるか

まず1つの文字列の中に'AB'が出てくるのは、そのまま使えるので数える。

問題は、「XXXA」「BXXX」みたいなのを連結していくつ増やせるか。

「末尾がA」「先頭がB」で1組作れるので、個数をそれぞれ数えて小さい方…とすると上手くいかない。

「BXXXA」のように両方に当てはまる文字列があり得るからである。 これを分けて数える。

• (1) 先頭がB、末尾がA: $x$ 個
• (2) 末尾がAのみ: $y$ 個
• (3) 先頭がBのみ: $z$ 個

(1) は、その個数だけ連結させるのが効率がよい。$x-1$ 個のABが作れる。

......... BXXA  BXXXA  BXA  BXXXXA .........

さらに、$y,z$ がそれぞれ1つ以上あれば、もう1つずつ増やせる。

... XXXA  BXXA  BXXXA  BXA  BXXXXA  BXXX ...

ここまでしたら、残りの $y,z$ を組にすればよい。

D - DivRem Number

• 正整数 $N$ が与えられる
• $N$ を正整数 $m$ で割ったとき、商と余りが一致するような $m$ を「お気に入りの数」とする
• あり得る「お気に入りの数」の総和を求めよ
• $1 \le N \le 10^{12}$

「商と余り」に共通する値（$k$ とする）を決めてしまえば、$m$ は逆算できる。

$m=\frac{N-k}{k}$

さらに、余りは割る数未満なので、$m>k$ である。また、$k$ を増やしていくと、$m$ は小さくなっていく。

すると、$k$ を小さい方から試して、逆算された $m$ が $k$ 以下になった時点で打ち切ってよい。$O(\sqrt{N})$ で抑えられる。

E - XOR Partitioning

• 長さ $N$ の数列 $a_1,a_2,...,a_N$
• 要素の間に好きなだけ区切りを入れて、連続する区間に分割する。区切りの入れ方は $2^{N-1}$ 通りある
• 区間内の全ての要素のxorを、その区間の「美しさ」とする
• 美しさが全ての区間で等しくなるような区切りの入れ方の数を、$\mod{10^9+7}$ で求めよ
• $1 \le N \le 5 \times 10^5$
• $0 \le a_i \lt 2^{20}$

全ての区間でxorが等しいということは、累積xorを取れば2区間ごとに打ち消し合って、区間の最後の要素だけを拾うと「$X,0,X,0,...$」というようになっているはず。$X$ は任意の数。

a        001  010 | 110  100  001 | 011
xor        011    |      011      | 011
累積xor  001  011   101  001  000   011
              ~~~             ~~~   ~~~

なので、累積xorを求めてDPをする。$a$ の累積XORを $acc$ とし、$acc$ 上で先頭から「$X,0,X,0,...$」と拾える数が、区切りの入れ方の数となる。

• 数列の末尾の1要素は必ず拾われる。$acc$ の最終要素は「$X,0,X,0,...$」の最終要素でないといけない
  • そのため、$acc$ の末尾が0以外の場合、それが唯一の $X$ である
  • $acc$ の末尾が0の場合、$X$ は $acc$ 上に出てくる全ての整数が候補として考えられる
  • →処理を分ける

• $X$ は0でもよいが、実装の上で分けて考えた方がやりやすい

$DP[x][i][k:0/x]=$「$X=x$ の場合において、$acc_i$ まで見たとき、最後に確定した区間の累積xorが $k=0/x$ である場合のパターン数」

すると、

• $acc_i=0$ の時 $DP[x][i][0] = 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]$）

例えば $acc_i=0$ の時、新規確定無し（$i-1$ からの引き継ぎ）に加え、最後に確定した区間が $x$ だった場合から新しく区間を確定して 0 に遷移するケースを足し合わせることを示す。

直前に確定した区間
           ↓      i
      ... 0｜  ... 0   (iでは区間を確定しない) DP[x][i-1][0]
   ... x｜ ...     0｜ (iで新規区間確定)       DP[x][i-1][x]
        ↑
直前に確定した区間

先述の通り、$X$ は一意に確定する。末尾の $X$ へは $DP[X][N][0]$ から遷移するので、それが答え。

末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのかと一瞬思うが、これはあくまで「最後に決定した区間が $X$ であるもの」の数。$acc$ の末尾は必ず区間として確定しなければならないが、$DP[X][N][X]$ にはその前の $X$ で確定したまま末尾で未確定状態の場合も含まれる。$DP[X][N][0]$ であれば、最後に確定した 0 から必ず末尾の $X$ に遷移できる。

acc  X  0  1  ...  0  X  X  2  X
                      ~~~~     ~ ←末尾は必ず使う
                      └DP[X][N][X]は、これとかで終わったまま
                        末尾では区間未確定なパターンも含まれる

まず、$X=0$ の場合、$acc_i$ が0の時に区切るか区切らないかを（末尾以外）独立に選べるので、$2^{0の出現回数-1}$ である。

$X \ne 0$ とする。

$X$ は最悪 $N$ の数だけ考えられるので、$X$ ごとに上記DPを繰り返すと $O(N^2)$ となり間に合わない。

まとめて複数の $X$ について処理することを考える。遷移式を再掲する。

• $acc_i=0$ の時 $DP[x][i][0] = 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]$

$acc_i=x$ の時は、影響があるのが $DP[x][i][x]$ だけなのでそれだけ更新すればいいのだが、 $acc_i=0$ の時、今まで出てきた全ての $X=x$ について $DP[x][i][0]$ を更新しなければならない。これではやはり間に合わない。

$DP[x][i][0]$ も $acc_i=x$ の時のみ更新すればいい、ということにできれば、$O(N)$ にできそうである。

遷移を考えると、$x$ が出てこない間に0が複数回出てきても、その時に $DP[x][i][0]$ の更新に加算される $DP[x][i-1][x]$ の値は一律である。

xor      x  x  x  0  0  0  x  x  0  0  x  0
dp0   1  1  1  1  4  7 10 10 10 33 56 56 135
        ↓ ↓ ↓ ↑ ↑ ↑ ↓ ↓ ↑ ↑ ↓ ↑
dpx   0  1  2  3  3  3  3 13 23 23 23 79 79
                  ~~~~~~~       ~~~~~
          連続した0の時にdp0に加算される値は一定

よって「前回 $x$ が出てきてから、0が出現した回数」がわかれば、次に $x$ が出てきたときにまとめて $DP[x][i][0]$ の更新も行える。

$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┐  x  0  0     ┌x┐  0
dp0   1  1  1  1  1  1  1    10 10 10 10 10     56 56 56
        ↓ ↓ ↓  ,--,--,-3x3↑ ↓ ↓  ,--,-23x2↑ ↓
dpx   0  1  2  3  3  3  3       13 23 23 23        79 79

また、末尾が0以外だった場合と同じ理屈で、答えの算出に使用するのは $DP[x][N][x]$ の方。$DP[x][N][0]$ の最後の評価は必要ない。

最後までやったら、$DP[x][N][x]$ を全ての $x$ について合計したら、それが $X \ne 0$ の時の答え。$X=0$ と合わせて最終的な答えとなる。