ABC199 参加記録 - Xenous の精進記録

3完0ペナ 26分でした
DかE解いたら出そうと思ったことで提出が遅れました。。

A - Square Inequality

問題文の通り実装します。

A, B, C = map(int, input().split())
if A ** 2 + B ** 2 < C**2:
    print('Yes')
else:
    print('No')

B - Intersection

全ての $i$ で $A_i \leq x \leq B_i$ が成り立つと言うことは、 $A_i$ の中で最も大きいものが $x$ の最低ラインになり、 $B_i$ の中で最も小さいものが $x$ の最大ラインになります。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = min(B) - max(A) + 1
if ans < 0: ans = 0
print(ans)

C - IPFL

$T_i = 1$ のときは単純に入れ替えをすればよさそうですが、 $T_i = 2$ のときの操作をそのまま実装すると、文字列の結合の計算量は結合される文字列の長さに依存するため、 $O(N^{2})$ になりTLEになることが予想できます。

したがって、前後半を入れ替える操作をするのではなく、入れ替える場所を前後半で変える操作にします。具体的には以下のイメージです。

f:id:Xenous:20210425142432p:plain — 1番目と4番目の入れ替え操作イメージ

0-index で考えると、 $T=2$ の操作で入れ替えが起こった状態のときに、 $T=1$ の操作をするときは、入れ替え先が $(A, B)$ から $(N+A, N+B) \ \mathrm{mod}\ 2N$ となります。

$T=2$ の入れ替えが起こった状態の管理は flag 等で管理して、最後に前後半を入れ替える必要があれば実際に行って出力すれば良いです。

import sys
input = sys.stdin.readline

N = int(input())
S = list(input()[:-1])
Q = int(input())
flag = True
for _ in range(Q):
    T, A, B = map(int, input().split())
    A -= 1; B -= 1
    if T == 1:
        if flag:
            S[A], S[B] = S[B], S[A]
        else:
            a = (N+A)%(2*N)
            b = (N+B)%(2*N)
            S[a], S[b] = S[b], S[a]
    else:
        if flag: flag = False
        else: flag = True
if flag: ans = S
else: ans = S[N:] + S[:N]
print(''.join(ans))

D - RGB Coloring 2

本番では DFS で実装しましたが、いくつか考察が甘いところがあり、結局正解からは程遠かったです。。自分用の戒めとして正解に辿り着くまでの軌跡を残しておきます。

まずサンプルにあるように、非連結の場合があります。したがって UnionFind を使って連結成分ごとの管理をし、各グループに対して配色を探索することにします。頂点が 1 つであれば、3 通りです。そうでない場合は DFS で探索する方針にしました。

(考察が甘かった部分その1) 重複のある探索

最初に実装したのは単純な DFS による探索です。最初の頂点の色を固定して、他の頂点はグラフに沿って「直前の頂点の色と異なる」条件で探索します。この方法は、下記のような重複が発生してしまい、答えが合いません。

f:id:Xenous:20210426215913p:plain — 頂点1 を`R`で固定した DFS の色の重複

※ 頂点 1 を赤で固定します。DFS で、2 が緑、3 が青のパターンと、2 が青、3が緑のパターンをやり切った後、今度は右図のように 3 が緑、2 が青という探索をします。このとき、この並び順はすでに出てきており、重複が発生します。

(考察が甘かった部分その2) 全ての頂点を配色していない

上記を解消すべく、全域木を作る要領で辺と頂点を管理して探索を行うようにしたところ、重複をしない探索が可能になりました。しかし、まだ問題は残っています。下記のようなグラフで DFS をすると、「全ての頂点を塗った状態」を作れません。

f:id:Xenous:20210426224954p:plain — 頂点 1 から DFS を行ったときのイメージ

最初は頂点 1, 2 と色を決め, 頂点 3 で赤, 青の二通りを探索します。その後頂点 4 に向かうわけですが、このとき頂点 3 の色を戻しておかないと、頂点 2 の次の色 (この図だと青) の探索のときに先に進まなくなってしまいます。

ということで、グラフをそのままDFSして探索するのはなかなか難しそうです。下の図の左側のように、頂点3 に行った後、そのまま頂点4 に向かって欲しいわけです。頂点を隣接した順に塗っていくにはどうしたらいいかを考えます。

f:id:Xenous:20210426231354p:plain — 頂点の巡り方イメージ

（図の右側のグラフでは、頂点 1 → 2 → 5 → 3 → 4 と探索する、というようなイメージです。）

巡る頂点の順番を決めてから探索する

上のイメージのように、頂点を隣接している順に見ていくには、配色しないただグラフをたどるだけの DFS を最初に行い、探索した順の頂点リストを用意すればOKです。このリストに対して配色の DFS を行うと、望んだ動きを実現できます。

この方針は、公式解説と同じになります。以下は参考で、提出コードです。

提出コード

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# union find は省略

def dfs_vertex(p:int, fr:int) -> None:
    """
    探索する頂点の順番を決めるために DFS しとく
    """
    global graph, vertexlist, goneset
    for to in graph[fr]:
        if to in goneset:
            continue
        goneset.add(to)
        vertexlist.append(to)
        dfs_vertex(fr, to)


def dfs(n:int) -> None:
    """
    色を実際に試す
    自分の色を決める
    """
    global graph, vertexlist, colorlist, res
    colorselect = set(['R', 'G', 'B'])
    fr = vertexlist[n]
    # 色の候補を絞る
    for to in graph[fr]:
        if colorlist[to] in colorselect: colorselect.remove(colorlist[to])
    # 配色を探索する
    for s in colorselect:
        colorlist[fr] = s
        if n+1 < len(vertexlist):
            dfs(n+1)
        else:
            # 全ての頂点を塗れたらカウントする
            res += 1
        colorlist[fr] = '*'


def main():
    global graph, vertexlist, goneset, colorlist, res
    N, M = map(int, input().split())

    # グラフの作成
    uf = UnionFind(N)
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1; B -= 1
        graph[A].append(B)
        graph[B].append(A)
        uf.union(A, B)

    # 答え計算用のリスト
    ans = [1] * N
    # 配色を一時保存するリスト
    colorlist = ['*'] * (N+1)

    # 各グループの代表の頂点ごとに見る
    for p in uf.grouping:
        # 頂点が 1 つだけのときは 3 通り
        if uf.msize(p) == 1:
            ans[p] = 3
        # それ以外は DFS して探索
        else:
            # まずは巡る頂点の順番を作るための DFS
            goneset = set([p]) # 一度通った頂点管理用
            vertexlist = [p]   # 探索した順の頂点リスト
            dfs_vertex(-1, p)
            
            # 各頂点の配色を行う DFS
            res = 0
            colorlist[p] = 'R'
            dfs(1)
            ans[p] = res * 3

    # 答え計算
    r = 1
    for a in ans:
        r *= a
    print(r)


if __name__ == "__main__":
    main()

E - Permutation

2021-05-09 追記. (解説 AC)

bitDP の問題でした。順序の情報が必要かどうかで bitDP ができるかどうかが決まると思うのですが、本番中では順序の情報が不要であることに自信が持てず、解けませんでした。

まず全探索は $O(N!)$ なので間に合いません。bitDP はこれを(多くの場合) $O(N2^{N})$ に改善してくれるわけですが、順序を無くした集合として状態を持っていいのかどうかがポイントになります。

例えば $N = 5$ で、3番目までを $\{1, 2, 5\}$ と持っていたとして、次に 3 を加える操作について考えます。条件で 3, 3, 2、つまり「3番目までの数列で 3 以下の数が 2 つ以下しかない」があったとき、3 を加えると $\{1, 2, 5, 3\}$ となります。

ここで、この集合において、上記の条件を満たさない [3, 1, 2] や [1, 3, 2] は気にしなくて良いのか、と思ってしまい（それ自体は良い）、本番で止まってしまったのですが、結果的には「上記のような条件を満たさない場合はちゃんと除いてあって、すでに正しく計算している」ことになります。DPなので。それぞれ以下のように遷移してきているはずです。

集合 $\{3\}$ に 1 を加えて $\{1, 3\}$ 。さらに $\{1, 3\}$ から 2 を加えて $\{1, 2, 3\}$
集合 $\{1\}$ に 3 を加えて $\{1, 3\}$ 。さらに $\{1, 3\}$ から 2 を加えて $\{1, 2, 3\}$

集合 $\{1, 3\}$ の結果には、1 から並べた場合と、3 から並べた場合の両方を調べた結果が入っています。従って、これまでの並び順によらず、加えた後の長さと等しい条件だけ調べれば良いことになります。

このように考えることができるのは、DPの定義をうまく定めるからです。今回の場合は公式解説の通り、 $\mbox{DP}_S$ （ $S$ は $\{1, 2, \cdots, N\}$ の部分集合）を「 $a$ の先頭 $|S|$ 要素まで決めていて、その $|S|$ 要素で使った数の集合がちょうど $S$ に一致し、 $X_i \leq |S|$ であるような条件は全て満たしているような場合の数」とすると、上記のような考え方が成り立ちます。

さて、実装部分についてですが、大枠の方針は以下の通りです。

$1$ から $2^{N}$ までをループ。各値の bit 列の 1 が立っているところを集合 $S$ として持っている状態と考える（5 なら二進数は 101 で集合としては $\{3, 1\}$ ）
集合 $S$ の中に含まれている要素 $x$ でループ。その要素を除いた集合を $D$ とする。 $S = D \cup \{x\}$ が成り立つ。 $D$ に $\{x\}$ を加える操作として考える。
$|S|$ での条件が存在しない場合は、そのまま $\{x\}$ を加える。すなわち、 $\mbox{DP}_S$ に $\mbox{DP}_D$ を加算する。
$|S|$ での条件が存在する場合は、数列の最後に $x$ を加えたときに全ての条件が成立するかチェックし、成立すれば $\mbox{DP}_S$ に $\mbox{DP}_D$ を加算する。成り立たない場合は $\mbox{DP}_S$ への加算は行わない。