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$ を組にすればよい。

import sys

n = int(input())
ans = 0
tail_a = 0
head_b = 0
both = 0
for s in sys.stdin:
    s = s.rstrip()
    ans += s.count('AB')
    if s[0] == 'B':
        if s[-1] == 'A':
            both += 1
        else:
            head_b += 1
    elif s[-1] == 'A':
        tail_a += 1
if both:
    ans += both - 1
    if tail_a:
        ans += 1
        tail_a -= 1
    if head_b:
        ans += 1
        head_b -= 1
ans += min(tail_a, head_b)
print(ans)

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})$ で抑えられる。

n = int(input())
i = 1
ans = 0
while True:
    d, m = divmod(n, i)
    d -= 1
    if i >= d:
        break
    if m != 0:
        i += 1
        continue
    ans += d
    i += 1
print(ans)

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,...$」と拾える数が、区切りの入れ方の数となる。

DP構築の考察

数列の末尾の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]
        ↑
直前に確定した区間

accの末尾が0以外だった場合

先述の通り、$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]は、これとかで終わったまま
                        末尾では区間未確定なパターンも含まれる

accの末尾が0だった場合

まず、$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$ と合わせて最終的な答えとなる。

from itertools import accumulate
from operator import xor


def solve(acc):
    MOD = 10 ** 9 + 7
    cnt0 = 0
    dp0 = {}
    dp1 = {}
    last_0 = {}
    for a in acc:
        if a == 0:
            cnt0 += 1
        elif a not in dp1:
            dp0[a] = 1
            dp1[a] = 1
            last_0[a] = cnt0
        else:
            bw0 = cnt0 - last_0[a]
            if bw0 > 0:
                dp0[a] = (dp0[a] + dp1[a] * bw0) % MOD
                last_0[a] = cnt0
            dp1[a] = (dp1[a] + dp0[a]) % MOD

    if acc[-1] == 0:
        return (pow(2, cnt0 - 1, MOD) + sum(dp1.values())) % MOD
    else:
        return dp0[acc[-1]]


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
print(solve(acc))

目次