AtCoder Beginner Contest 199（Sponsored by Panasonic）

(D 以外全部を解くのにかかった時間) < (D を解くのにかかった時間) になってしまった...

A - Square Inequality

YNeos を書こうとして頭と手が止まった．普通に書いた方がはやいね...

A, B, C = map(int, input().split())
print("YNeos"[A ** 2 + B ** 2 >= C ** 2::2])

B - Intersection

つまりは $\displaystyle \max _ {1\leq i\leq N} A _ i \leq x \leq \min _ {1\leq j\leq N} B _ j$ を満たす $x$ を数える問題． $\max A \gt \min B$ のケースに注意．

N = int(input())
L = max(map(int, input().split()))
R = min(map(int, input().split()))
print(max(0, R - L + 1))

C - IPFL

type 2 のクエリで実際に swap する代わりに，swap されているかどうかのフラグを持つ．もし swap されていれば，添え字 $i$ (0-indexed) は次のように読み替えられる．

$i\lt N$ のとき: $i+N$
$i\geq N$ のとき: $i-N$

この変換法則を用いて type 1 のクエリを処理する．フラグが true の場合，最後の出力時に swap し忘れると間違えるので注意．

下に示すコードでは rev が swap のフラグとなっている．

N = int(input())
S = [c for c in input()]
Q = int(input())
rev = False
for _ in range(Q):
    t, a, b = map(int, input().split())
    a -= 1
    b -= 1
    if t == 1:
        if rev:
            if a < N:
                a += N
            else:
                a -= N
            if b < N:
                b += N
            else:
                b -= N
        S[a], S[b] = S[b], S[a]
    else:
        rev = not rev
if rev:
    S[:N], S[N:] = S[N:], S[:N]
print(''.join(S))

D - RGB Coloring 2

やばいやつ．

そのまま全探索をすると $O(M 3 ^ N)$ で厳しいので，少し工夫して探索する必要がある．ある頂点 $u$ の色が決まっている場合， $u$ に隣接する頂点 $v$ の色は $u$ の色以外の $2$ 通りしか存在しない．

従って，各連結成分に対して始点 $u$ を取って色を決め， $u$ からの距離が近い順であったり，あるいは $u$ を根とする (連結成分に対する) 全域木をとって DFS/BFS の行きがけ順であったり，適切な順番に色を決めることにするとよい．そうすると，サイズ $C$ の連結成分に対する答えは $O((C + M) 2 ^ C)$ 程度で求めることが出来る．

また，各連結成分は独立に数えられるので，各連結成分に対する答えを求めて最後にかけ合わせればよい．

以下は Java による AC コード．DisjointSetUnion クラスや Graph などの実装は省略している．

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] us = new int[m];
    int[] vs = new int[m];
    DisjointSetUnion dsu = new DisjointSetUnion(n);
    for (int i = 0; i < m; ++i) {
        us[i] = sc.nextInt() - 1;
        vs[i] = sc.nextInt() - 1;
        dsu.merge(us[i], vs[i]);
    }
    int[][] groups = dsu.groups(); // 連結成分を取得
    long ans = 1;
    for (int[] group : groups) {
        boolean[] con = new boolean[n]; // 連結成分に属するかどうか
        int k = group.length;
        Graph<SimpleEdge> g = new Graph<>(k);
        for (int id = 0; id < k; ++id) {
            con[group[id]] = true;
        }
        for (int i = 0; i < m; ++i) {
            int u = us[i];
            int v = vs[i];
            if (con[u] && con[v]) {
                int ui = ids[u];
                int vi = ids[v];
                g.addEdge(new SimpleEdge(ui, vi));
            }
        }
        ans *= solve(g);
    }
    pw.println(ans);
}

static long solve(Graph<SimpleEdge> g) {
    int n = g.getV();
    IntArrayList pre = new IntArrayList(); // BFS で訪問した順番
    int[] par = new int[n]; // 全域木における親
    Arrays.fill(par, -1);
    boolean[] vis = new boolean[n];
    vis[0] = true;
    IntDeque dq = new IntDeque(n);
    dq.addLast(0);
    while (dq.size() > 0) {
        int u = dq.removeLast();
        pre.add(u);
        for (var e : g.getEdges(u)) {
            int v = e.to;
            if (!vis[v]) {
                vis[v] = true;
                par[v] = u;
                dq.addLast(v);
            }
        }
    }
    int[] color = new int[n];
    long ans = 0;
    Out:for (int i = 0; i < 1 << n - 1; ++i) {
        Arrays.fill(color, 1, n, -1);
        for (int j = 1; j < n; ++j) { // 色を BFS の訪問順に決定していく．
            int v = pre.get(j);
            color[v] = (color[par[v]] + 1 + ((i >> (v - 1)) & 1)) % 3;
        }
        for (int u = 0; u < n; ++u) {
            for (var e : g.getEdges(u)) {
                int v = e.to;
                if (color[u] == color[v]) {
                    continue Out;
                }
            }
        }
        ++ans;
    }
    return ans * 3;
}

E - Permutation

典型的な bit DP で，確実に D よりは易しいと思う．

$\displaystyle \mathrm{dp}[S]=\text{制約に違反せず $\{a_1,\ldots,a_{|S|}\}=S$ となるような $a_1,\ldots,a_{|S|}$ の決め方}$

と定義する．遷移に関しては，最後に追加する $x\in S$ を全探索して，実際に制約に違反していないかを確かめればよい．

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] xs = new int[m];
    int[] ys = new int[m];
    int[] zs = new int[m];
    for (int i = 0; i < m; ++i) {
        xs[i] = sc.nextInt();
        ys[i] = sc.nextInt();
        zs[i] = sc.nextInt();
    }
    int[][] bits = BitUtil .bits(n); // bits[i] := i の 2 進数表記において立っている bit の位置を記録した配列
    long[] dp = new long[1 << n];
    dp[0] = 1;
    for (int s = 1; s < 1 << n; ++s) {
        int[] cnt = new int[n + 1]; // cnt[i] = i 未満の要素の個数
        for (int x : bits[s]) {
            ++cnt[x + 1];
        }
        for (int i = 0; i < n; ++i) {
            cnt[i + 1] += cnt[i];
        }
        int k = bits[s].length; // k=|S|
        for (int x : bits[s]) { // 追加する要素を全探索
            int t = s ^ (1 << x);
            boolean ok = true;
            for (int j = 0; j < m; ++j) {
                if (xs[j] >= k) { // Xj<k なる j に関する制約は満たされていることが保証されている
                    ok &= cnt[ys[j]] <= zs[j];
                }
            }
            if (ok) dp[s] += dp[t];
        }
    }
    pw.println(dp[(1 << n) - 1]);
}

F - Graph Smoothing

一回の選択で辺 $(u,\ v)$ が選択されたときの頂点 $i$ への寄与を考える．

$i \in \{u,v\}$ のとき: $\dfrac{A _ u + A _ v}{2M}$
$i \not\in \{u,v\}$ のとき: $\dfrac{A _ i}{M}$

従って， $N\times N$ 行列 $B$ の要素を全て $0$ で初期化し，各辺 $(u,\ v)$ に対して

$B _ {u, u} \leftarrow B _ {u, u} + \dfrac{1}{2M}$
$B _ {u, v} \leftarrow B _ {u, v} + \dfrac{1}{2M}$
$B _ {v, u} \leftarrow B _ {v, u} + \dfrac{1}{2M}$
$B _ {v, v} \leftarrow B _ {v, v} + \dfrac{1}{2M}$
$B _ {i, i} \leftarrow B _ {i, i} + \dfrac{1}{M}\quad (i\not\in\{u,v\})$

で更新し，行列累乗で $B ^ K$ を求めてベクトル $A$ に掛けると答えのベクトルが求まる．

// mod 関連の演算をやるクラス
static final ModArithmetic ma = ModArithmetic1000000007.INSTANCE;
// mod M 上の行列演算をやるクラス
static final ModMatrixFactory mmf = new ModMatrixFactory(ma);

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int k = sc.nextInt();
    long im = ma.inv(m);
    long i2 = ma.inv(2);
    long[] a = sc.longs(n);
    long[][] mat = new long[n][n];
    for (int i = 0; i < m; ++i) {
        int u = sc.nextInt() - 1;
        int v = sc.nextInt() - 1;
        for (int j = 0; j < n; ++j) {
            if (j == u) {
                mat[j][j] += ma.mul(i2, im);
                mat[j][v] += ma.mul(i2, im);
            } else if (j == v) {
                mat[j][j] += ma.mul(i2, im);
                mat[j][u] += ma.mul(i2, im);
            } else {
                mat[j][j] += im;
            }
        }
    }
    long[] x = mmf.create(mat).pow(k).mul(a);
    for (long e : x) {
        pw.println(e);
    }
}