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

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}$

解法1

$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

解法2

解法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})$ で求められる。

解法3

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

解法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

import sys
from bisect import bisect

n, q, *ak = map(int, sys.stdin.buffer.read().split())
aaa = ak[:n]
kkk = ak[n:]

buf = []
for k in kkk:
    offset = 0
    while True:
        i = bisect(aaa, k + offset)
        if i == offset:
            break
        offset = i
    buf.append(k + offset)

print('\n'.join(map(str, buf)))

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

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, m, k):
    if n == 0:
        return 1
    if m == 0:
        if n <= k:
            return 1
        else:
            return 0
    if n > m + k:
        return 0

    MOD = 10 ** 9 + 7
    facts, finvs = prepare(n + m, MOD)

    ans = facts[n + m] * finvs[n] * finvs[m]
    if n > k:
        ans -= facts[n + m] * finvs[n - k - 1] * finvs[m + k + 1]

    return ans % MOD


n, m, k = map(int, input().split())

print(solve(n, m, k))

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

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

from collections import deque


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]

    def add_link(self, from_, to, capacity):
        self.links[from_].append([capacity, to, len(self.links[to])])
        self.links[to].append([0, from_, len(self.links[from_]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s, t, depth, progress, link_counts):
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s, t):
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow


h, w, n = map(int, input().split())

dnc = Dinic(h + w + n * 2 + 2)
s = h + w + n * 2
t = s + 1

for i in range(h):
    dnc.add_link(s, i, 1)
for j in range(h, h + w):
    dnc.add_link(j, t, 1)

for k in range(h + w, h + w + n):
    dnc.add_link(k, k + n, 1)

    a, b, c, d = map(int, input().split())
    for i in range(a - 1, c):
        dnc.add_link(i, k, 1)
    for j in range(b - 1 + h, d + h):
        dnc.add_link(k + n, j, 1)

print(dnc.max_flow(s, t))

目次

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

D - Kth Excluded

問題

解法1

解法2

解法3

E - White and Black Balls

問題

解法

カタラン数

上手な発想

F - Grid and Tokens

問題

解法