AtCoder Grand Contest 062 A,B,C問題メモ

AtCoder Grand Contest 062

BよりCの方が解かれていたけど、 100点くらいの差だったらやっぱり後ろの方がワンチャン狙いで挑戦されやすかったりするのかな。

A - Right Side Character

• 'A' と 'B' からなる長さ $N$ の文字列 $S$ が与えられる
• 以下の操作を $N-1$ 回行う
  • 現在の $S$ を $n$ 文字とする
  • $1～n-1$ 文字目の内、'A' が出てくる位置を順に $a_1,a_2,...,a_k$、'B' を $b_1,b_2,...,b_l$ とする
  • $S$ を以下の $n-1$ 文字の文字列に置き換える
    • $a_1$ の次の文字、$a_2$ の次の文字、…、$a_k$ の次の文字、$b_1$ の次の文字、…、$b_l$ の次の文字
• 最終的に $S$ は1文字になるが、その文字を答えよ
• $T$ ケース与えられる
• $2 \le N \le 3 \times 10^5$
• 1つの入力において、$N$ の総和 $\le 3 \times 10^5$

法則が見えづらい時は、実験するのが早い。
実験をしてみると、ほとんど答えが 'A' になる。

'B' になるケースを見てみると、'AAAABBB' のように、「'A'の連続→'B'の連続」の時のみ。
これが正しいかを確認する。

まず、全て'A'、全て'B'の時は明らかにその文字なので、混在する場合を考える。

最後の'B'の次の文字は'A'となる。（'B'だったら「最後の'B'」に矛盾）
よって、1回の操作後も末尾が'A'の状態が保たれ、繰り返すと最後も'A'が残ることになる。

同様に最後の'A'の次の文字は'B'となる。
'BA'という箇所があるかどうかを考える。

1回の操作後、「最後の'A'の次の文字の'B'」→「どこかにある'BA'から作られる'A'」が存在することになる。
よって、必ずしも連続していないかもしれないが、操作後もどこかには'BA'が存在する。

繰り返すと、どこかで末尾の文字が'A'になり、最終的な答えも'A'になる。

最初に実験したとおり、'B' が残る。

'A'が1つずつ少なくなり、どこかで全て'B'になる。

Python3

B - Split and Insert

• $1～N$ の順列 $A=(A_1,...,A_N)$ があり、はじめ、$A=(1,2,3,...,N)$
• 以下の操作を $K$ 回おこなう
  • $0 \le k \lt N$ を満たす $k$ を選ぶ
  • $A$ を、前 $N-k$ 項と後ろ $k$ 項に分割する
  • 前 $N-k$ 項に、後ろ $k$ 項を挿入する（下の例 参照）
• 操作にはコスト $C_1,...,C_K$ が設定されている
  • $i$ 回目の操作で $k=k_i$ とした場合、その1回の操作コストは $C_ik_i$
  • 全体のコストはその総和
• $K$ 回の操作後、$A=(P_1,...,P_N)$ にできるか判定し、できる場合は必要な最小コストを求めよ
• $1 \le N \le 100$
• $1 \le K \le 100$

やることが文章で分かりづらい。

A = (1 2 3 4 5 6 7)
k = 3 を選んで操作 ... (1 2 3 4) に (5 6 7) を挿入

挿入例1  1   2   3   4  →  1 5 2 6 3 7 4
           5   6   7

挿入例2      1 2 3 4    →  5 6 1 2 3 4 7
         5 6         7

高速道路の合流区間のように、
2つの数列それぞれの順序を変えないまま、織り込む感じ

(1, 3, 4, 2) の 3→2 のように、$x+1$ が $x$ より前にあると、そこを境界として1回は操作しないといけない。
そうしない限り、初期状態の (1, 2, 3, 4) から 2→3 の並びが変わることはない。

逆に、こういう位置を全て操作で分割すれば、上手く挿入することで $P$ への並べ替えを実現できる？
以下、それを確認する。（あくまで最適な操作ができることの確認であり、実際に操作を復元する必要は無い）

1ずつ増加する部分列を $P$ から取れるだけ取ったものを「ブロック」とする。
ブロックを昇順に並べ、その境界が操作が必要となる箇所である。

N=8
 7 5 3 1 8 6 4 2
 ↓
[1 2] [3 4] [5 6] [7 8]    4ブロックに分けられる（境界は3箇所）

野菜を切るときのように、1回分割したブロックは、次以降の分割時、重ね合わせられる。

1 2 3 4 | 5 6 7 8
↓
5 1 6 2 7 3 8 4
↓
5 1 6 2 | 7 3 8 4  ←ここで、[1 2 | 3 4] の境界と [5 6 | 7 8] の境界を同時に切っている
↓
7 5 3 1 8 6 4 2    3個の分割点を2回の操作で分割可能

1回の操作で、2つの列の、1番目のブロック同士、2番目のブロック同士、、、などといった要領で、 順番を保って2ブロックずつをペアにして1つに統合できる。
統合するブロック同士で、その中での順序を $P$ に合わせていけばよい。

[1 2] [3 4] | [5 6] [7 8]
↓
[5 1 6 2] [7 3 8 4]         ブロックを統合、その中での順序をPに合わせていく

統合するのに最適なブロックはコストによって変わり、必ずしも1番目同士、2番目同士というわけではなく、飛ばすこともある。

[A] [B] [C] | [D] [E]
↓
[AD] [B] [CE]

のように統合した後、[CE] を分割、[B] は単独で分割、とした方がコストが安い、みたいなこともあり得るので一概に言えない。

が、最適な操作（どのブロック間を何番目の操作で分割するか）が決まっているとして、 「もう以降の操作で分割されない（順序を入れ替えられない）ブロック同士」というのは復元できるので、 そのタイミングで順番を揃えていけばよい。

これで、ブロックの境界を1回ずつ切ることで並べ替えが実現できることが分かった。

今回のコストはあくまで「分割時の末尾からの文字数」なので、挿入の仕方は関係ない。
分割さえすれば挿入は何とでも上手いことできることが確認できた今、 コストを考える上では「いつ、どのブロック間を分割するか」だけに着目して考えてよい。

大まかには、まとめて切る方針と、末尾から1つ1つ切る方針がありそうだが、

• まとめて切る
  • メリット:
    • 安いときに一度に複数ブロックの境界を切れる
    • 回数を節約できる
  • デメリット:
    • 準備のため、前もって長いブロックを切って重ねておかないといけない
    • その重ねたブロックをまた切るので、同じブロックが複数の操作で $k$ に計上される
    • （上の例では、まとめて切るため [7 8] ブロックは1,2回目の操作の両方で $k$ に計上されている）
• 末尾からちまちま切る
  • だいたい上記の逆。安いときでも1つの境界しか切れないが、同じブロックを複数回 $k$ に計上するなどの無駄がない

最終的な操作はこれらの複合的なものとなり、とても貪欲には求められそうにない。

何らかのDPを使う前提で、部分問題に分割できないか考える。

挿入は放置して、昇順に並んだブロック列を、ただ分割していくと捉える。

[ A ] [ B ] [ C ] [ D ] | [ E ] [ F ]
 ↓
[ A ] [ B ] [ C ] [ D ]
[ E ] [ F ]

[ A ] [ B ] | [ C ] [ D ]  2回目以降は、分割されたブロック列の
[ E ] | [ F ]              それぞれの末尾から好きなだけ取った合計を k にする、と考えてよい
 ↓                      （それより前の操作で、これが可能なように挿入しておけば良い）
[ A ] [ B ]
[ C ] [ D ]
[ E ]
[ F ]

全てのブロックがバラバラになれば完了。

よって、分割後の各ブロック列は、他のブロック列に依存せずその列だけで、残りの操作における最適解を求められる。

分割された2つのブロック列 $a,b$ が、 部分問題を解く上で、操作 $i$ でそれぞれ末尾から $k_a,k_b$ で分割するのが最適だったとして、 $C_i(k_a+k_b) = C_ik_a + C_ik_b$ なので、部分問題同士のコストを合計したものを、元の問題のコストとして問題ない。

操作を逆順に考えて、全てバラバラの状態から統合していく区間DPで解ける。

• $DP[i,l,r]=i$ 回目の操作後に $[l,r)$ のブロックが未分割の時、その区間のブロックを $K$ 回までに全て分割するのに必要な最小コスト

$l,r$ は、$A$ でなくブロックに対するindex（0-indexed）とする。ブロック数を $b$ とする。
初期値は $DP[K,l,l+1]=0$ （$l=0～b-1$）で、他はINFとしておく。

$DP[i,*,*]$ から $DP[i-1,*,*]$ をもとめる。

$i$ 回目の操作で $[l,m)$ と $[m,r)$ を分割する場合、$k_m$ を $[m,r)$ ブロック内にある項数として、

• $DP[i,l,m]+DP[i,m,r]+C_i \times k_m$

のコストがかかる。$m=l+1～r$ を試し（$m=r$ の場合は $k_m=0$、つまり実質的に操作をしない）、最小値を取ればOK。

• $DP[i-1,l,r]=\min_{m}(DP[i,l,m]+DP[i,m,r]+C_i \times k_m)$

最終的に、$DP[0,0,b]$ が答え。INFなら不可能となる。

$DP$ の状態数が $O(N^3)$、1回の遷移で $O(N)$ で全体 $O(N^4)$ だが、定数倍が大体6分の1くらいになるので間に合う。

Python3

C - Mex of Subset Sum

• $N$ 個の正整数 $A_1,...,A_N$ の、部分集合の和として作れない正整数を、小さい方から $K$ 個列挙せよ
• $1 \le N \le 60$
• $1 \le K \le 1000$
• $1 \le A_i \le 10^{15}$

作れる数を列挙して、後からそこに含まれない数を列挙しようとしても、作れる数は $2^60$ 通りになりえるので無理。 （実際は $A_i$ の上限のため頭打ちになるが、それでも $2^{50}$ はくだらない）

上限を決めてそれ以下のみを管理することで計算量を抑える？
それでも、「$10^{15}$ 以下の数は全部作れるよ」みたいな $A$ もあり得るので無理。

作れない数を列挙するDPを考える。
実際には無理だが、もし、負の数や無限大まで含めた、サイズ無限大の集合で考えていいなら、

• $DP'[i] = i$ 番目までの要素を使って作れない整数の集合

• $DP'[0] = (全ての整数からなる集合) \setminus \{0\}$
• $DP'[i] = DP'[i-1] \cap (DP'[i-1] の各要素に$A_i$を足した数の集合)$

作れる数（部分和問題）の補集合なので、上のようになる。
よくある部分和問題のDPの初期状態を反転させ、OR条件をAND条件に変えればよい。

ただ、このままでは扱えないので「負の数」「それまでの総和を超える数」という、明らかに作れない数は保持しないことにする。
$S_i=A_1+A_2+...+A_i$ として、

• $DP[i] = i$ 番目までの要素を使って作れない、$S_i$ 以下の正整数の集合

最終的に、正整数の小さい方から $K$ 個さえ分かればよいので、 サイズ上限を決めてそれ以上は保持しないことでできそう。

部分和問題はbitsetでも解くことができる。無限大の要素を管理する $DP'$ で考えると、

               0        S[i-1]
               |          |
DP'[i-1] ...111100010111101011111....   （負と無限大方向にはずっと1が続く）

         ...1111111100010111101011111....  Ai だけ右bitshift (この例では4)

このbitごとのANDを取ったものがDP[i]

         ...1111000101111010111111111....
         ...1111111100010111101011111....
         --------------------------------
DP'[i]   ...1111000100010010101011111....

で、負と $S_i$ を超える数は管理しないことにした場合に困るのは、

• bitshift後に、負から正に来る'1'
• bitshift後に、$S_{i-1}$ を飛び出る'1'

なので、$DP[i-1]$ の各要素が $DP[i]$ にも残留できるかのチェックは、数字の区間によって場合分けして考える。

なお、今回は'0'が続く区間がすご～く長くなり得るので、bitsetの実装はやはり無理。
「数字の範囲を区切る」イメージの説明であって、あくまで、データとして持つのは作れない数字1個1個の集合。

S(i-1) >= Ai の場合
                     0          Ai        S(i-1)
v       [    負    ]   [      DP[i-1]     ]   [ to 無限大 
        ~~~~~~~~~~~~                          ~~~~~~~~~~~~~
        全て作れない                          全て作れない

                     0          Ai                    Si
                       |-------- DP[i] の管轄 -------|
v+Ai    [    負+Ai            ]   [    DP[i-1]+Ai    ]   [ to 無限大 
                       ~~~~~~~~   ~~~~~~~~    ~~~~~~~~
                          ①         ②          ③

• ①: $0 \lt v \lt A_i$
  • $DP[i-1]$ に $v$ が含まれていれば、$DP[i]$ にも $v$ が含まれる
• ②: $0 \lt v \lt S_{i-1}-A_i$
  • $DP[i-1]$ に $v$ と $v+A_i$ が含まれていれば、$DP[i]$ にも $v+A_i$ が含まれる
• ③: $S_{i-1}-A_i \lt v \lt S_{i-1}$
  • $DP[i-1]$ に $v$ が含まれていれば、$DP[i]$ に $v+A_i$ が含まれる

S(i-1) < Ai の場合
                     0            S(i-1)     Ai
v            負    ]   [  DP[i-1]  ]   [ to 無限大  
        ~~~~~~~~~~~~                   ~~~~~~~~~~~~~
        全て作れない                    全て作れない

                     0                       Ai            Si
                       |----------- DP[i] の管轄 ---------|
v+Ai         負+Ai                         ]   [DP[i-1]+Ai]   [ to 無限大 
                       ~~~~~~~~~~~~~   ~~~~~   ~~~~~~~~~~~~
                             ①          ②         ③

• ①: $0 \lt v \lt S_{i-1}$
  • $DP[i-1]$ に $v$ が含まれていれば、$DP[i]$ にも $v$ が含まれる
• ②: $S_{i-1} \lt v \lt A_i$
  • 全て $DP[i]$ にも含まれる
• ③: $0 \lt v \lt S_{i-1}$
  • $DP[i-1]$ に $v$ が含まれていれば、$DP[i]$ に $v+A_i$ が含まれる

この遷移に従って、$DP$ の要素数の上限を $L$ と定めておけば、$O(NL)$ で計算できる。

$N \le 60$ なので、だいたい計算量が $10^7$ くらいになるように逆算して、 $L=2 \times 10^5$ とかにすると、通る。

①、②、③は、区間長はとても大きくなり得るので、間違っても区間の数字を1つずつ全探索などしてはいけない。
あくまで、$DP[i-1]$ に含まれる数の方をイテレートして求めていくのが大事。

適当に $L=2 \times 10^5$ とかで切り詰めてしまったが、 実際は、$DP[i]$ の要素は存在していたものがどんどん消えていく（追加もされるが）ので、 「$DP[1]$ で捨てちゃった $L+1$ 番目の要素が、実は答えに含まれるべき数でした」みたいなことがあり得るかもしれない。

それが無いこと、また、$L$ をいくつにすれば大丈夫と言えるのかは、どう証明したらいいんだろう？（わからない）

同じアプローチでは無いが、以下に、正確な答えが求まる証明がある。「確定したら打ち切る」がポイント。

• 解説 - AtCoder Grand Contest 062

まず、先ほど考察した遷移から「$DP[i-1]$ のうち、$A_i$ より小さい数は、必ず $DP[i]$ に引き継がれる」ことがわかる。

よって、$A_i$ を昇順にソートした上で処理していくと、 $A_i$ 未満の $DP[i]$ 内の数が $K$ 個以上になったら、その $K$ 個で確定なので打ち切れる。

$DP[i]$ で管理される数は「$0$ 以上 $A_i$ 未満」と「$A_i$ 以上 $S_i$ 未満」に分けられる。
前者の個数は、未確定という条件の下で $K$ 個未満、 後者は $DP[i-1]$ 個以下（先ほどの図参照）なので、 DPの管理対象は $i$ が1進むごとに、たかだか $K$ 個しか増えない。

よって、$L$ 個で切り詰めるとかしなくても、 確定しない限り、DPの要素数は $NK$ 個未満で抑えられ、全体で $O(N^2K)$ で計算できる。

Python3