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

AtCoder Beginner Contest 199（Sponsored by Panasonic）

全探索が苦手すぎるマン

D - RGB Coloring 2

問題

$N$ 頂点 $M$ 辺のグラフが与えられる
辺でつながった頂点は異なる色となるように、RGBの3色で頂点を塗り分ける方法としてあり得るものの個数を求めよ
$1 \le N \le 20$

解法

グラフは連結とは限らないが、連結成分ことに答えを求めれば、それを掛け合わせたものが全体の答えとなる。

なので、連結なグラフの答えを考える。

頂点彩色問題というのはあるが……

辺で隣り合う頂点を全て異なる色に塗る問題は頂点彩色問題と呼ばれていて、一定の性質はあるものの、多項式時間で求められるものでもないらしい。

グラフ彩色#頂点彩色

ただし、2色で塗り分けられるか、という問題に限っては、二部グラフかどうかで判定できる。

（今回は3色なので、ある1色で塗る頂点を全探索して、残りを2色で塗れるか調べる、という方法でもACできたらしい）

全探索

制約も小さいことから、色の塗り方の全探索を考える。

しかし、全てのあり得る色を試すと $3^{20} \simeq 3.5 \times 10^9$ で間に合わない。

ある頂点の色を決めるとそこから辺でつながった頂点の選択肢は実質2つになるので、そのような枝刈りを実装することで $2^{20} \simeq 10^6$ を実現する。

適当に根を決めて、DFSして全域木を取り、各頂点の親を決める
- 全域木に使われなかった辺を集めておく
根の色を決め打つ
根以外の頂点の色の決め方は、「親と異なる２色のうち、どちらの色を用いるか」で、$2^{連結成分の頂点数-1}$ 通り
各色の決め方につき、他の辺と矛盾してないか確認する
- 全域木に使われなかった辺だけ確認すればよい

とすると、その答え $\times 3$（根の色のバリエーション）がその連結成分の答えとなる。

最初に全域木を取る理由

最初に全域木を取るのは、「各頂点は、どの頂点を基準に、それと異なる色にすればよいか（この場合は親頂点）」を固定したいため。
ここがコロコロ変わると、ある頂点の色を決めたいとき、基準としたい頂点の色がまだ決まっていなくて、決められないことが発生しうる。

①--③--②  数字を色を決めていく順とすると、
            ②の色を決めたいのに、それより後の③の色の情報が必要となり、立ち往生する

全域木で根に近い方から決めていくと、ある頂点の色を決めるときは必ず親頂点の色は決まっているので、ちゃんと決められる。

もちろん、うまく組めば一発のDFSで矛盾しない色の組み合わせ数を求められるが、混乱しやすい場合は、このようにまずDFSで情報を取り出して、段階を踏むとスッキリする。

bitフラグと色の塗り方の変換例

例えば、3色を $1,2,3$ で表し、根の色を $1$ と決め打ったとする。
根以外の頂点の色を表すbit集合を 0101 などと決めると、全て頂点の色が決定する。

色の具体的な決め方はあくまで一例
                                                            0 1
   根①       ②: 親①が1, bit集合の1bit目が'1' → 異なる色 2,3 から3を選ぶ
   ／  ＼     ③: 親①が1, bit集合の2bit目が'0' → 異なる色 2,3 から2を選ぶ
  ②    ③    ④: 親②が3, bit集合の3bit目が'1' → 異なる色 1,2 から2を選ぶ
 /  \         ⑤: 親②が3, bit集合の4bit目が'0' → 異なる色 1,2 から1を選ぶ
④  ⑤

全頂点の色が決まったら、全域木以外の辺を調べる。辺の両端の2頂点が同じ色となっている辺が1つでもあったらアウト。

無ければその組み合わせは正しい色配置となり、1つとしてカウントできる。

各連結成分につき 2^(連結成分の頂点数-1) で全頂点の色を確定できるところがポイント。

Python3

import os
import sys

import numpy as np


def solve(inp):
    def solve_component(s, links, visited):
        parents = {s: -1}
        visit_order = [s]
        q = [s]
        visited[s] = True
        check_links = []
        while q:
            v = q.pop()
            for u in links[v]:
                if visited[u]:
                    if parents[u] != v:
                        check_links.append((v, u))
                    continue
                visited[u] = True
                parents[u] = v
                visit_order.append(u)
                q.append(u)

        n = len(visit_order)
        ans = 0

        for bit in range(1 << (n - 1)):
            colors = {}
            colors[visit_order[0]] = 1
            for i, v in enumerate(visit_order[1:]):
                b = (bit >> i) & 1
                p = colors[parents[v]]
                if p == 1:
                    colors[v] = 2 if b else 3
                elif p == 2:
                    colors[v] = 1 if b else 3
                else:
                    colors[v] = 1 if b else 2

            for v, u in check_links:
                if colors[v] == colors[u]:
                    break
            else:
                ans += 1

        return ans

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2] - 1
    bbb = inp[3::2] - 1

    links_base_list = {aaa[0]}
    links_base_list.pop()
    links = [links_base_list.copy() for _ in range(n)]
    for i in range(m):
        links[aaa[i]].add(bbb[i])
        links[bbb[i]].add(aaa[i])

    ans = 1
    visited = np.zeros(n, np.int8)
    for v in range(n):
        if visited[v]:
            continue
        ans *= solve_component(v, links, visited) * 3

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

E - Permutation

問題

$1,2,...,N$ の順列 $a_1,a_2,...,a_N$ を考える
$M$ 個の条件が与えられるので、それを全て満たす順列の個数を求めよ
条件
- $i$ 番目の条件は、$X_i,Y_i,Z_i$ で与えられる
- $a_1～a_{X_i}$ の中に、$Y_i$ 以下の数は $Z_i$ 個以下しか存在しない
$1 \le N \le 18$
$0 \le M \le 100$

解法

これまたD問題に続いて制約が小さい。

左端から決めていって、今まで使った数の組み合わせを管理しても $2^{18}$ 程度の状態数で済む。

$DP[i][S]=$ 順列の先頭 $i$ 番目まで決める方法で、条件は全て満たしつつ、使った数字の組み合わせが $S$（bit集合）である場合の数
- 実際は $S$ を決めると、その'1'が立っている個数で $i$ も決まるので実装上は $DP[S]$ でもいいのだが、まぁ説明のために $i$ もつけることとする

S = 10100  →    3,5を先頭2文字に使った、条件を満たす順列の個数
S = 01101  →  1,3,4を先頭3文字に使った、条件を満たす順列の個数

まず、$M$ 個の条件を $X_i$ を基準にまとめておく。
$i$ 番目の数を置く際、$i=X_k$ である条件 $k$ を満たしているかをチェックしていくと、漏れなく全ての条件をチェックできる。

実際に遷移を考える。

10100 からの遷移を考える。

どれか1つの数字を置く
たとえば1を置くことにする
  10101

    条件のうち、Xi=3 であるものは、(X,Y,Z)=(3,4,3),(3,3,1) の2つとする
    これらが全て満たされているかチェックする

      (4,3):  _0101 の中に立っているbitが3個以下ならよい → OK
      (3,1):  __101 の中に立っているbitが1個以下ならよい → NG

    全てを満たせなかったので、10101は遷移先として不適当ということになる。
    何もせず、次に置く数字を試す。

たとえば4を置くことにする
  11100
  
    同様に条件が全て満たされているかチェックする

      (4,3):  _1100 の中に立っているbitが3個以下ならよい → OK
      (3,1):  __100 の中に立っているbitが1個以下ならよい → OK

    遷移先として適当なので、遷移先に遷移元の状態数を加算する
      DP[3][11100] += DP[2][10100]

このように、遷移元のbit集合を決める→次に置く数字（立てるbit）を決める→条件が満たされているかチェック、というループを回す。

遷移元となるのは $2^{N}$、立てるbitを決めるのに $N$、それが条件を満たしているかの確認は $X$ の分布に依るのだが、、、

最悪ケースは $N=18,i=9$ で一番状態数が多い遷移に全ての $X_i$ がまとまっている状態で、その場合 ${}_{18}C_{9}\times 9 \times 100 \simeq 4.7 \times 10^7$ と少々厳しめの見積もりとなるが、まぁそこまで極端なケースは無かったのか、通った。

より高速にするにはループの順番を変えて、遷移元のbit集合を決める→現時点でギリギリの条件を探し、次に置くことが可能な最小の数字を求める→それ以上の数字は置けるので置く、とする方法もある。

Python3

import os
import sys

import numpy as np


def solve(inp):
    def pop_count(n):
        c = (n & 0x55555555) + ((n >> 1) & 0x55555555)
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
        c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f)
        c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
        c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff)
        return c

    n = inp[0]
    m = inp[1]
    xxx = inp[2::3]
    yyy = inp[3::3]
    zzz = inp[4::3]

    tuple_list = [(n, n)]
    tuple_list.clear()
    events = [tuple_list.copy() for _ in range(n + 1)]
    for i in range(m):
        events[xxx[i]].append((yyy[i], zzz[i]))

    dp_from = {0: 1}
    dp_to = dp_from.copy()
    dp_to.clear()
    for i in range(1, n + 1):
        for bit in dp_from:
            for j in range(n):
                b = 1 << j
                if bit & b:
                    continue
                new = bit | b
                for y, z in events[i]:
                    if pop_count(new & ((1 << y) - 1)) > z:
                        break
                else:
                    if new in dp_to:
                        dp_to[new] += dp_from[bit]
                    else:
                        dp_to[new] = dp_from[bit]
        dp_from, dp_to = dp_to, dp_from
        dp_to.clear()
        print(dp_from)

    full_bit = (1 << n) - 1
    if full_bit in dp_from:
        return dp_from[full_bit]
    else:
        return 0


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

F - Graph Smoothing

問題

$N$ 頂点 $M$ 辺の単純無向グラフ
各頂点には最初、数 $A_1,A_2,...,A_N$ が書かれている
これから $K$ 回にわたり、以下の操作を行う
操作
- $M$ 本の辺からランダムに1本選び、両端の頂点の値を、その2数の平均値に置き換える
全ての操作後、各頂点に書かれている値の期待値を $\mod{10^9+7}$ で求めよ
$2 \le N \le 100$
$0 \le K \le 10^9$

解法

競プロ的な典型に慣れていると、D～Fの中ではこれが一番解法を思いつきやすいかも知れない。

まず、1回の操作でどうなるか考える。丸数字は $A_i$（各頂点の値）を示す。

⑤----③----②
｜    ｜   /
⑨----①--'

⑤の頂点は、1回の操作後、6本の各辺が選ばれた場合のそれぞれで以下のようになる。

⑤-③の辺: $\dfrac{5+3}{2}=4$
⑤-⑨の辺: $\dfrac{5+9}{2}=7$
それ以外の4辺: $5$ のまま

で、期待値としてはこれらの平均を取って、$\dfrac{31}{6}$ となる。

頂点の値を一般化すると、頂点 $1$ にとって1回操作後の期待値は、

A1----A2----A3
｜    ｜   /
A4----A5--'

$\dfrac{A_1+A_2}{6 \times 2}+\dfrac{A_1+A_4}{6 \times 2}+4 \times \dfrac{A_1}{6}$

というように、現在の $A_1～A_5$ の値の線形和で表現できる。

他の頂点も同様。

ここで、期待値の線形性を使う。

$A_i$ に1回操作した後の期待値を $A'_i$ とする
$A_i$ に2回操作した後の期待値を $A''_i$ とする
$A''_i$ は、$A'_i$ を初期値とした状態から1回操作した後の期待値と等しい

和の期待値は期待値の和 | 高校数学の美しい物語

従って、1回分の操作を行列 $M$ で表すと、$K$ 回分の操作を表す行列は、$M^K$ となる。

$$ Ans.= \left( \begin{array}{ccccc} \frac{10}{12} & \frac{1}{12} & 0 & \frac{1}{12} & 0 \\ \frac{1}{12} & \frac{9}{12} & \frac{1}{12} & 0 & \frac{1}{12} \\ 0 & \frac{1}{12} & \frac{10}{12} & 0 & \frac{1}{12} \\ \frac{1}{12} & 0 & 0 & \frac{10}{12} & \frac{1}{12} \\ 0 & \frac{1}{12} & \frac{1}{12} & \frac{1}{12} & \frac{9}{12} \end{array} \right)^K \left( \begin{array}{c} A_1 \\ A_2 \\ A_3 \\ A_4 \\ A_5 \end{array} \right) $$

行列累乗はダブリングで高速化できる。

Python3

import numba
import numpy as np


@numba.njit('i8[:,:](i8[:,:],i8[:,:],i8)', cache=True)
def dot(mat1, mat2, MOD):
    ret = np.zeros_like(mat1)
    n = mat1.shape[0]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                ret[i][j] = (ret[i][j] + mat1[i][k] * mat2[k][j]) % MOD
    return ret


@numba.njit('i8[:](i8[:,:],i8[:],i8)', cache=True)
def dot2(mat1, mat2, MOD):
    ret = np.zeros_like(mat2)
    n = mat1.shape[0]
    for i in range(n):
        for k in range(n):
            ret[i] = (ret[i] + mat1[i][k] * mat2[k]) % MOD
    return ret


n, m, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
rm = pow(m, MOD - 2, MOD)
rm2 = rm * pow(2, MOD - 2, MOD) % MOD

mat = [[0] * n for _ in range(n)]
complement_degrees = [m] * n

for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    mat[x][x] += rm2
    mat[x][y] += rm2
    mat[y][y] += rm2
    mat[y][x] += rm2
    complement_degrees[x] -= 1
    complement_degrees[y] -= 1

for i in range(n):
    mat[i][i] += rm * complement_degrees[i]

mat = np.array(mat, np.int64) % MOD
ans = np.identity(n, np.int64)
t = k
while t:
    if t & 1:
        ans = dot(mat, ans, MOD)
    mat = dot(mat, mat, MOD)
    t >>= 1

aaa = np.array(aaa, np.int64)
ans = dot2(ans, aaa, MOD).tolist()

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

目次

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

D - RGB Coloring 2

問題

解法

頂点彩色問題というのはあるが……

全探索

最初に全域木を取る理由

bitフラグと色の塗り方の変換例

E - Permutation

問題

解法

F - Graph Smoothing

問題

解法