AtCoder Beginner Contest 205 D,E,F問題メモ

AtCoder Beginner Contest 205

D - Kth Excluded

これが茶Diffになるんですねえ。

• $N$ 個の正整数 $A_1,A_2,...,A_N$ 「以外」で $K_i$ 番目の正整数を答えよ
• クエリは $Q$ 個与えられるので、それぞれの $K_i$ について求めよ
• $1 \le N,Q \le 10^5$
• $1 \le A_i,K_i \le 10^{18}$

$A_1～A_N$ 以外の正整数を「列挙対象」とする。

各 $A_i$ から、「自身より小さい列挙対象の個数 $B_i$」を作っておく。
$A_0=0$ と便宜的に置いた上で、$A_{i-1}$ と $A_i$ の間には $A_i-A_{i-1}-1$ 個の列挙対象があるので、それを累積的に足し合わせると作れる。

$K$ をこの $B$ から二分探索することで、

• 答えがどの $A_{i-1}～A_i$ 間にあるか
• $A_i$ よりいくつ小さいか

がわかるので、直接求めることができる。

i    0   1  2  3  4  5  6
A   (0)  3  4  5  8 12 14
B    0   2  2  2  4  7  8

K=6 なら、
    二分探索でBへの挿入位置を求めると i=5
  →答えは A5=12 から B5-K+1=2 だけ戻った数
  →Ans = 10

解法1は事前計算によって二分探索を1発で済ませたが、こちらでは1つの $K$ につき何回か繰り返す。

まず、$A_i$ の除外がなければ、当然だが $K$ 番目の要素は $K$ になる。

$f(K)=$「$K$ 以下の $A_i$ の個数」を二分探索で求める。
$x$ 個あったら、$x$ 個分スキップされているのでその分だけ $K$ からずれ、暫定の答えは $K+x$ となる。

しかしそのスキップした $K+1～K+x$ の中にも $A_i$ が含まれているかも知れない。

最終的に $f(K+x)=x$ という均衡状態になれば $K+x$ が答えなので、この $x$ を求める。 （複数ある場合は最も小さいもの）

$x'$ が真の $x$ より小さければ $x' \lt f(K+x')$、大きければ $x' \ge f(K+x')$ となるので、 これを判定基準に二分探索を行えば、 $x$ を特定できる。

計算量は $O(Q \log{N}\log{K})$ で求められる。

本番ではこの方法で通したけど、計算量が問題ないかきちんと証明できていない。

解法2の $f(K)$ を使うところまでは同じだが、$x$ を求める際、$x←f(K+x)$ を収束するまで繰り返す。
これでも正しい答えは求まる。

こうすると、たとえば $A=(1,2,3,...,10^5)$ で、$K=1$ のとき、$10^5$ 回の処理 $f$ が1回のクエリで走ってしまう。
$f$ は二分探索を含むので、1回 $O(\log{N})$ かかる。

ただ、このように回数がかさむ $K$ は限られて、 上例のように1から隙間無く連続した $A$ に対して $f$ が走る回数は $\frac{N}{K_i}$ 回となり、 調和数列の和で、全体を通して $O(N\log{N})$ で抑えられる。

これなら $O(Q+N (\log{N})^2)$ なので間に合う。 （$K_i$ が全て異なる制約はないが、同じ $K_i$ に対してはメモ化をすればよい）

ただ、他にもっと意地悪な $A$ が無いという証明ができていない。

Python3

E - White and Black Balls

• 白のボール $N$ 個、黒のボール $M$ 個を一列に並べる（同色同士は区別しない）
• 整数 $K$ が与えられて、以下の条件を満たすように並べなければならない
• 条件
  • 左から $x$ 個の中に含まれる白いボールを $w_x$、黒いボールを $b_x$ とする
  • $w_x \le b_x+K$ が、全ての $1 \le x \le N+M$ で成り立っている
• 並べ方の個数を $\mod{10^9+7}$ で求めよ
• $0 \le N,M \le 10^6$

2色のボールを並べる操作は、$(0,0)$ から $(N,M)$ までのグリッド経路数の数え上げに言い換えられる。

そのうち $(K+1,0)～(N,M-K-1)$ の部分（白ボールを下方向、黒ボールを右方向とすると、左下の◣部分）を通過する経路が、条件を満たさない経路となる。

  →b
↓   0 1 2 3 4 5
w 0  . . . . . .  K=1
  1  . . . . . .
  2  x . . . . .
  3  x x . . . .
  4  x x x . . .

これを全体から除いたものが答えなのだが、重複を除くのが意外と難しい。

似た問題の1つに、カタラン数による経路数え上げがある。

• カタラン数の意味と漸化式 | 高校数学の美しい物語

$N \times N$ のグリッドで、対角線を超えない経路の答え（今回の問題で $H=W, K=1$ に限定したケース）は、カタラン数となる。

• $c_n = {}_{2n}C_{n} - {}_{2n}C_{n-1}$

動的計画法で考えると、「$(0,0)$ 以降で対角線に最初に触れたのが $(i,i)$」としたときの $i$ を固定すると、そこで分割することでより小さい2つのカタラン数の和で表現できる。
これを $0～N$ まで和を取ったものが次のカタラン数となる。

• $\displaystyle c_{n+1} = \sum_{i=0}^{n}{c_i c_{n-i}}$

ただこの方針でいこうとしても、今回は「最初に対角線（入ってはいけない境界ギリギリ）に触れた」などで分類したくても最後まで触れないルートもあるし、またその経路数が $K$ にも依存するので、DPが2次元になり、$O(WK)$ は間に合わない。

ナナメの直線でグリッド全体をまるっと反転させてしまうと、「元の始点→反転後の終点への経路数」が、 元のグリッドで条件を満たさない経路数と同じになる（Editorial参照）。

これは、「元の始点→最初に踏んだNG頂点→元の終点」と「元の始点→最初に踏んだNG頂点→反転後の終点」が綺麗に1対1対応することによる。

Python3

この解法を典型として覚えてしまってもいいけど、動的計画法的には解けないもんなのかな。考えたり検索したけどいまいち見つからない。

F - Grid and Tokens

• $H \times W$ の盤面と、$N$ 個のコマがある
• コマ $i$ は、$(A_i,B_i)$ を左上、$(C_i,D_i)$ を右下とする矩形の範囲にしか置けない
• 全ての行・列に、コマが2つ以上置かれてはいけない
• 置けるコマの最大数を求めよ
• $1 \le H,W,N \le 100$

最大流。

グリッドの1行あたり・1列あたりに置ける数が限られた中で最大化、みたいな問題は、 行と列をそれぞれ $H,W$ 個の頂点とした二部マッチング問題に置きかえられることがある。

今回はそのままでは上手くいかないが、この考えの応用で解ける。

適当にコマの頂点を追加してこねくり回していたらできたけど、いまいちどうやって考えを進めればよいか、よくわからない。

• 辺の張り方
  • [source]→[行に対応する頂点]→[コマに対応する頂点1]→[コマに対応する頂点2]→[列に対応する頂点]→[sink]
  • 辺の容量は全て1
  • より詳細はEditorial参照

コマに対応する頂点が1層だと、1つの矩形の中にコマが複数置ける場合、分身して置ける限り置くことになってしまう。

頂点を分離して容量1の辺を張ることで、複数置けたとしてもその中の1つ、ということが表現できる。

問題のアレンジとして、

• もし1行に $k$ 個まで置ける場合、[source]→[行] の辺の容量を $k$ にすればよい
• もし1列に $k$ 個まで置ける場合、[列]→[sink] の辺の容量を $k$ にすればよい
• もしコマを $k$ 個まで分身させてもよい場合、[コマ1]→[コマ2] の辺の容量を $k$ にすればよい。

Python3