トップ > AtCoder > AtCoder Beginner Contest 199

AtCoder Beginner Contest 199

AtCoder AtCoder-Beginner Contest Python

A~Cに回答できました．直前にグラフの勉強をした（Pythonで蟻本2-5 - グラフ - 競プロはじめました，E - Unique Color | ABC198）ので，Dも回答したいところでした．

A - Square Inequality

if 文が書ければできます．

B - Intersection

ナイーブには$\min(B)-\max(A)+1$で良いですが，解なしの場合はこの値がゼロ以下になります（※ $\min(B)=\max(A)$のとき$1$）．よって，
\begin{aligned}
\max\bigl(0, \min(B)-\max(A)+1 \bigr)
\end{aligned}
が答えです．

C - IPFL

1回目TLEしました．

$T_{i}=2$のときの処理は，$T_{i}=2$が奇数回あるときにだけ，最後に1回実施すれば良いことに気づけばできます．

最速の回答がわかりやすいです：Submission #21998990 - AtCoder Beginner Contest 199（Sponsored by Panasonic）
【内容】

  • indexを指定して文字を代入したいため，文字列をリスト化する．最後に「''.join(S)」で文字列に戻す．
  • 「○文字目→配列のindex」と変換するため，A -= 1, B -= 1 としている．
  • T=2が出るたびに，flippedのFalse↔Trueを入れ替える．最終的にflipped=Trueなら，前半と後半の$N$文字を入れ替える．
  • T=1の処理は，flipped=Trueのときに文字列を入れ替えていない分の補正が必要．具体的には，$A+N \pmod{2N}$とまとめてかける（わかりにくければ，$A\leq N$と$N < A$で場合分けすれば良い）．


D - RGB Coloring 2

UnionFind（Union-Find木 | 蟻本2-4）を使っているものとそうでないものがあるみたいです．読んでみたいものをメモしておきます．

Union Findを使う方法

UnionFindを使った処理がわかりやすかったので，コメントを加えました．

【内容】
3色を0, 1, 2で表現します．次の手順で処理します．

  1. 連結成分でまとめた頂点のリストを作る
    • Union-Find木で根が同じ頂点をグループ化
    • ↑を根をキーに辞書化 (後で連結成分ごとに呼びたい)
  2. 連結成分の頂点のうち1つを0で塗る→dfsで連結成分の頂点(隣接頂点とは限らない)を順に見ていく．今いる頂点を隣接頂点とは異なる色で塗っていく．
    • dfs(連結成分の頂点v)
    • 全ての頂点を見終わったら結果+1 (res)
    • vが塗られているなら次
    • vが塗られていないなら，隣接頂点にない色を全て試す（処理が終わったらもとに戻す）
  3. 最初の1つは0, 1, 2の塗り方があるから，3倍すれば各連結成分を塗る方法になる．
  4. 最終的な答えは，各連結成分を塗る方法の積．

# https://atcoder.jp/contests/abc199/submissions/22019350
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline

n,m = map(int,readline().split())

UF = UnionFind(n)
# 隣接リストの作成→UnionFindTree化(連結成分でまとめる)
g = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,readline().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    UF.merge(a-1,b-1)

ans = 1
color = [-1]*n  # 頂点の色．-1が塗られていない状態．

# d[根ノード]=[根と連結なノードのリスト]
# ※ 根ノード自身も含まれる
from collections import defaultdict
d = defaultdict(list)
for i in range(n):
    d[UF.root(i)].append(i)

def dfs(n):
    '''
    n=調べるノード(連結成分内の番号)
    対応する頂点v = lst[n]
    '''
    global res
    if n == -1:
        # 連結成分全て(n=0まで)塗り終えたらres+1して終了
        res += 1
        return
    # 今いる頂点
    v = lst[n]
    if color[v] >= 0:
        # すでに色が塗られているなら次(あとの処理はしない)
        dfs(n-1)
        return
    # vの色が塗られていないなら，全ての場合を考える
    for i in range(3):
        # vの隣接頂点に色iのものがなければ，vを色iで塗ってdfs
        for c in g[v]:
            if color[c] == i:
                break
        else:
            color[v] = i
            dfs(n-1)
    # vの塗り替え操作をした場合は，
    # 元(塗られていない状態)に戻す
    color[v] = -1

# 各連結成分([根と連結なノードのリスト])ごとにdfs実行
for lst in d.values():
    # 初期化(res=色を塗る方法)
    res = 0
    color[lst[0]] = 0  # 1つ選んで0で塗る
    # dfs実行(lst[0]以外のノード)
    dfs(len(lst)-1)
    # 上のdfsではlst[0]の色を0で固定した→×3する
    # 各連結成分を塗る方法の積が答え
    ans *= res*3  

print(ans)


E - Permutation

これがわかりやすいです（PyPyでないとTLEのようです）：Submission #22008592 - AtCoder Beginner Contest 199（Sponsored by Panasonic）
【内容】
$\{1,2,...,N\}$の部分集合$S$に対して
  • $\mathrm{dp}[S]=S$を並び替えてできる数列$\{a_{i}\}$で，$X_{i}\leq |S|$について条件を満たすものの総数
とします．漸化式は
\begin{aligned}
&\mathrm{dp}[S] \\
&=
\begin{cases}
\, \displaystyle \sum_{x\in S} \mathrm{dp}[S\setminus\{x\}] & (\text{$S$が条件を満たす}) \\
\, 0 &(\text{$S$が条件を満たさない})
\end{cases}
\end{aligned}
となります．

初期条件は，$\mathrm{dp}[\emptyset]=1$とすれば，要素数1のときに満たすべき条件

\begin{aligned}
&\mathrm{dp}[\{k\}] \\
&=
\begin{cases}
\, 1 &(\text{$X_{i}=1$の条件をすべて満たす}) \\
\, 0 & (\text{otherwise})
\end{cases}
\end{aligned}
が成り立つことが，漸化式からわかります．

以上のDPは部分列$S$をビットで表すとコード化できます．
  1. 要素数が1つ小さい$\mathrm{dp}$の値をすべて加える
    • $S$からフラグを1つ消した$\mathrm{dp}$は前のループまでで計算済み
    • $i$番目のフラグ消去は，S ^ (1 << i) または S & ~(1 << i)
    • cntでSの要素数を表す
  2. $X_{i}=$cnt (Sの要素数) となる条件式をすべて満たすか調べ，満たさないものがあれば$\mathrm{dp}[S]=0$で上書きする．
    • $i+1$を表すフラグはS >> i & 1で取り出せる
    • S >> 0=S
  3. 最後尾の要素$\mathrm{dp}[-1]$が答え

また，「$a_{1},a_{2},,,a_{X_{i}}$の中に$Y_{i}$以下の数は$Z_{i}$以下」という条件は，$a_{1},a_{2},,,a_{X_{i}}$の並び順とは関係ないことに注意しましょう．

F - Graph Smoothing