−目次

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) C,D,E,F問題メモ
- C - Unexpressed
  - 問題
  - 解法
- D - Poker
  - 問題
  - 例
  - 解法
- E - Oversleeping
  - 問題
  - 解法
- F - Zebraness
  - 問題
  - 例
  - 解法

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) C,D,E,F問題メモ

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

キャディのサラダ館。

C - Unexpressed

問題

$1～N$ までの整数の中で、2以上の整数 $a,b$ を使って $a^b$ の形で表せないものが何個あるか求めよ
$1 \le N \le 10^{10}$

解法

$a^b$ で表せるものを数えて、全体 $N$ から引く方針でいく。

範囲内の数で $a$ が取り得る最大値は、 $b=2$ の時に $\sqrt{N}$ なので、 $a$ を全探索するのは間に合う。

あとは、 $a$ を固定したときに $b$ が最大いくつまで取り得るかを、 $N$ を $a$ で何回割れるかで調べればよい。

ただし、 $2^6=4^3$ のように、異なる $a,b$ で同じ整数が表せることがあるので、一度出た整数はsetなどで管理しておく。

$a^b$ で表せる数があんまり多いとTLEやMLEになるが、最大の $N$ で試して大丈夫なら大丈夫。

Python3

D - Poker

問題

AとBの2人が以下のルールのゲームをする
ルール
- 表に $1～9$ が書かれたカードが $K$ 枚ずつ、計 $9K$ 枚ある
- ランダムにシャッフルして、2人に、それぞれ4枚を表に、1枚を裏にして配る
- 手札の点数は、 $i=1～9$ について「 $i \times 10^{手札に含まれるiの枚数}$ 」の合計値
2人に表で配られたカードが与えられるので、Aの点数がBより大きくなる確率を求めよ
$2 \le K \le 10^5$

例

1,3,3,5,(5) のカードが配られたとき、(※5枚目は裏向き)
手札の点数は
10 + 2 + 300 + 4 + 500 + 6 + 7 + 8 + 9 = 846 点

解法

裏になっているカードの状態は $9 \times 9$ で81通りしかないので、それぞれについて調べればよい。

確率の計算に注意。裏になっているカードが $i$ である確率は、表に見えている $i$ の枚数によって変わりうる。

たとえば、 $K=3$ のときに「A: 1122#」「B: 1345#」であれば、Aの裏になっているカードは

カード1はもう残っていない
カード2はあと1枚
カード3～5はあと2枚ずつ
カード6～9はあと3枚ずつ

で全部で21枚あるので、裏のカードがそれぞれの数である確率は、例えばカード3なら $\frac{2}{21}$ となる。

さらにBの裏になっているカードは、Aのカードが何だったかでさらに1枚消費した状態で同様に数える。

10個中2個の当たりが入ったくじを引くとき、2個同時に引いても、1個ずつ順番に引いても、結果の確率は変わらない、みたいな文章題、よく見た記憶がある。
今回も、裏になっているカードの状態をA,B同時に決めても、順番に決めても、確率は変わらない。

$p_i=$ Aの裏のカードが $i$ である確率
$q_{i,j}=$ Aの裏が $i$ だったとき、Bの裏が $j$ である確率

として、点数計算してAが勝つ場合だけ、 $p_i \times q_{i,j}$ を合計すれば答えとなる。

Python3

E - Oversleeping

問題

駅 $A,B$ 間を往復する電車があり、時刻0に $A$ を出発後、以下を繰り返す
- 電車の動き
  - $X$ 秒かけて駅 $B$ に移動
  - $Y$ 秒間 $B$ で停車
  - $X$ 秒かけて駅 $A$ に移動
  - $Y$ 秒間 $A$ で停車
高橋君は時刻0に $A$ を出発する電車に乗り、以下を繰り返す
- 高橋君の動き
  - $P$ 秒眠る
  - $Q$ 秒起きる
  - 電車が駅 $B$ に停車中、起きていれば、即座に下車する
ただし、各時間は半開区間として扱うので、以下の2ケースは下車できない
- 電車が出発する瞬間に目覚める
- 入眠する瞬間に電車が駅に着く
高橋君が駅 $B$ で下車できる最も早い時間を求めよ
- ただし永遠に不可能な場合、'infinity' を出力せよ
問題は $T$ ケース与えられるので、全てについて答えよ
$1 \le T \le 10$
$1 \le X,P \le 10^9$
$1 \le Y,Q \le 500$

解法

電車で寝て、起きたら既に終点を通り越して逆方向だった経験、誰しもあるよね！

問題設定が少々長いが、実体験でもあり得る問題なので飲み込みやすくて嬉しい。
（日常生活からそういう性質を持ったものを何個も見つけるのは難しいと思う）

制約をよく見ると「 $Y$ : 電車が停車している時間」「 $Q$ : 高橋君が起きている時間」が圧倒的に短い。

高橋君が下車できる条件をもっと限定的に表現すると、「電車が $B$ に停車してから $i$ 秒後と、高橋君が起きてから $j$ 秒後の時刻が一致する」といえる。

$0 \le i \lt Y, 0 \le j \lt Q$ で $(i,j)$ を全探索して、さらにそれを $T$ ケースやっても十分間に合う。

それぞれを数式で表すと、 $k,l$ を適当な非負整数としてそれぞれ以下のようになる。

$(2X+2Y)k+X+i$
$(P+Q)l + P+j$

modを使えば $k,l$ を省いて以下のように表せる。

$X+i \mod{(2X+2Y)} \equiv P+j \mod{(P+Q)}$

中国剰余定理を使えば、これを満たす解が存在するか、存在するなら正の最小値はいくつかを求めることができる。

中国剰余定理

AtCoder Libraryにも crt として用意されている。

Python3

よく考えると、 $(i,j)$ を全探索しなくても、最適になり得るのは「駅に着いた瞬間」か「起きた瞬間」のいずれかに限られるのだから、

$i$ を全探索して、 $X+i \mod{(2X+2Y)} \equiv P \mod{(P+Q)}$ を解く
$j$ を全探索して、 $X \mod{(2X+2Y)} \equiv P+j \mod{(P+Q)}$ を解く

とすれば計算量がもっと減らせたね。

F - Zebraness

問題

$N \times N$ マスのグリッドを黒か白に塗る
グリッドの初期状態は $N \times N$ の文字列で与えられる
- 既に黒、白で塗られているマスは 'B', 'W'、まだ塗られていないマスは '?' で表現される
'?'のマスを適切に塗って「隣り合う、一方が黒で一方が白のマスの組の個数」の最大数を求めよ
$1 \le N \le 100$

例

■■■
■□□

このような最終形は、以下の3つの黒白ペアがある。

・■・    ・・■    ・・・
・□・    ・・□    ■□・

解法

過去に類題見たことあると思いつきやすいかも知れない。

俗に燃やす埋める問題と呼ばれる、グラフの最小カット問題に帰結できる問題パターンがある。

燃やす埋める問題

$N$ 個のゴミを、それぞれ燃やすか埋めるか決める
ゴミ $i$ は燃やすとコスト $c_{i,1}$ 、埋めるとコスト $c_{i,2}$ が発生する
また「ゴミ $i$ を燃やし、 $j$ を埋めると、追加コスト $d_{i,j}$ が発生する」という条件が何個かある
処遇を適切に決めて、総コストを最小化せよ

今回の場合、上の説明でゴミが「'?'マス」、燃やす埋めるが「白に塗る、黒に塗る」にあたるのだが、コストの最小化でなくて得点の最大化となる。

このような場合、負辺ができないようにあらかじめ下駄を履かせた上で正負逆転させる。
今回では「隣接するマスの個数分だけ既に得点をもらった後、同じ色のマスが隣りあった場合をコストとする」とよい。

各'?'マスの周囲の黒、白、'?'マスを数えておいて、以下のようなグラフを構築する。 $s,t$ は仮想的な始点・終点とする。辺上の数字はその辺のコストとする。

  白に塗る        黒に塗る
 ,-  1 -→ ?マス1 -- 1 --,      周囲に白が1個、黒が1個
 |                       ↓
 s - 2 -→ ?マス2 -- 0 → t     周囲に白が2個、黒が0個
 |                       ↑
 `-  1 -→ ?マス3 -- 2 --'      周囲に白が1個、黒が2個

さて、ここで'?'マス同士が隣り合った場合の追加コストを表現する辺を追加していきたいのだが、燃やす埋める問題の制約として「同じ側の処遇を行った場合の追加コストは表現できない」というのがある（たぶん）。

つまり、本来は隣り合った'?'マス2個を「どちらも白」「どちらも黒」にした場合にコストが発生するのだが、これは“同じ処遇”なのでグラフで表現できない。

ここで、グリッドグラフは、2部グラフになることが利用できる。

どういうことかというと、左を「白に塗る」、右を「黒に塗る」と意味づけしたのはあくまで人間の理解のためで、アルゴリズム上は個別に左右反転しても問題ない。

 ,-白- 1 -→ ?マス1 -- 1 -黒-,      周囲に白が1個、黒が1個
 |                           ↓
 s 黒- 0 -→ ?マス2 -- 2 -白→ t    周囲に白が2個、黒が0個
 |                           ↑
 `-白- 1 -→ ?マス3 -- 2 -黒-'      周囲に白が1個、黒が2個

こうすると、例えば'?'マス1と2が隣り合っていたとしても、追加コストの辺をちゃんと表現できる。

 ,-白- 1 -→ ?マス1 -- 1 -黒-,
 |            ｜↑           ｜
 |           1｜｜1          ｜
 |            ↓｜           ↓
 s 黒- 0 -→ ?マス2 -- 2 -白→ t
 |                           ↑
 `-白- 0 -→ ?マス3 -- 2 -黒-'

そして、例えば市松模様の白いマスだけを左右反転する、というように決めると、全ての「隣り合った'?'マス同士」は「左右反転してないのが1個と、したのが1個」となり、必ず追加コストの辺を張れるようになる。

こうやってグラフを構築して、最小カット問題（＝最大流問題）を解けば、答えが求まる。

入れ替わっただけのペアを重複して数えないように注意。

Python3

        
          
          
              
              from collections import deque
 
 
class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, 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)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))
 
 
n = int(input())
field = [input() for _ in range(n)]
 
vertices = {}  # {i,j: 頂点番号, 周囲の黒, 周囲の白個数, [周囲の'?'の(i,j)]}
fixed_zebra = 0
for i, row in enumerate(field):
    for j, c in enumerate(row):
 
        def register(ni, nj, b, w, ques):
            if field[ni][nj] == 'B':
                b += 1
            elif field[ni][nj] == 'W':
                w += 1
            else:
                ques.append((ni, nj))
            return b, w
 
 
        b, w = 0, 0
        ques = []
 
        if i > 0:
            b, w = register(i - 1, j, b, w, ques)
        if i < n - 1:
            b, w = register(i + 1, j, b, w, ques)
        if j > 0:
            b, w = register(i, j - 1, b, w, ques)
        if j < n - 1:
            b, w = register(i, j + 1, b, w, ques)
 
        if c == 'B':
            fixed_zebra += w
        elif c == 'W':
            fixed_zebra += b
        else:
            v = len(vertices)
            vertices[i, j] = [v, b, w, ques]
 
fixed_zebra //= 2
 
mf = Dinic(len(vertices) + 2)
s = len(vertices)
t = len(vertices) + 1
geta0 = 0
geta1 = 0
for (i, j), (v, b, w, ques) in vertices.items():
    geta0 += b + w
    geta1 += len(ques)
    if (i + j) % 2 == 0:
        mf.add_link(s, v, w)
        mf.add_link(v, t, b)
    else:
        mf.add_link(s, v, b)
        mf.add_link(v, t, w)
    for ti, tj in ques:
        u = vertices[ti, tj][0]
        mf.add_link(v, u, 1)
 
f = mf.max_flow(s, t)
 
print(fixed_zebra + geta0 + geta1 // 2 - f)

            

        
      