🔖

AtCoder ABC199 個人的メモ

2021/04/25に公開

Python

競技プログラミング

AtCoder

tech

所感

abc3完
cが場合分け考えるの面倒くさいなと思って後回しにしたのが悪かった
abc199

A - Square Inequality

問題通りに

A, B, C = map(int, input().split())

if A ** 2 + B ** 2 < C ** 2:
    print("Yes")
else:
    print("No")

B - Intersection

問題文より，xは全てのA以上かつ全てのB以下の数字であればおｋ
なので，Aの最大値以上でBの最低値以下の数字の個数が答え

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

print(max(0, min(B) - max(A) + 1))

C - IPFL

問題文通り実装するとTLEする(した)
なので，高速化する必要がある
T=1のクエリはO(1)で済みそうなので，T=2を高速化したい
文字列Sの前半分と後ろ半分を2つの変数で管理する
T=2のクエリではこの2つを入れ替える
T=1のクエリでは，以下の様に2つを連結してからAとBを交換すれば楽そうだが，そうするとTLEする

if T == 1:
    S = first + last
    S[a], S[b] = S[b], S[a]
    first = S[:N]
    last = S[-N:]

というわけで，連結せずにAとBを交換する
AとBがそれぞれ前半分と後ろ半分どちらの部分を示しているかに注意しながら交換すればおk

N = int(input())
S = list(input())
Q = int(input())

first = S[:N]
last = S[-N:]
for _ in range(Q):
    t, a, b = map(int, input().split())

    if t == 2:
        first, last = last, first
        continue

    a, b = sorted([a - 1, b - 1])
    if b + 1 <= N:
        first[a], first[b] = first[b], first[a]
    elif a + 1 <= N and N < b + 1:
        first[a], last[b - N] = last[b - N], first[a]
    else:
        last[a - N], last[b - N] = last[b - N], last[a - N]

print("".join((first + last)))

D - RGB Coloring 2

自力で実装しきれなくて，参考にしたコードのほぼコピーになった

連結成分ごとに独立していそうなので，各連結成分ごとに考える．
各連結成分ごとに色の条件を満たすようにDFSすれば，解が求まりそう．
なので，DFSの実装を考える．
最初の頂点iを適当な色で塗った後，隣接する頂点を条件を満たすように塗っていく．
iに隣接している頂点はiの色以外の2色の選択肢がある．
以上の繰り返しを各頂点で実行するので，計算量は $O(N\times 2^N)$ となり十分高速．

今回のグラフは単純グラフで閉路を持つ可能性がある．
木のDFSの様にある頂点に訪問したか否かを管理しつつ隣接する頂点に移動していくと，頂点の訪問順は異なるが色の塗り方は同じ場合を重複して数えてしまう．
これを回避するために，頂点の塗る順番を固定する．

参考

def search_connect(n: int):
    """連結成分をDFSで探索

    Args:
        n (int): 頂点の番号
    """
    seen[n] = True
    connect.append(n)
    for i in E[n]:
        if seen[i]:
            continue
        search_connect(i)
    return


def paint(con_i: int):
    """connect配列に含まれている頂点番号順に，頂点に色を塗っていく．
    color配列は各頂点の色，インデックスは頂点の番号

    Args:
        con_i (int): connect配列のインデックス

    Returns:
        (int): 場合の数
    """
    node_num = connect[con_i]
    # 隣接する2頂点の色が重複していないかを確認
    if any(color[node_num] == color[j] for j in E[node_num]):
        return 0

    # 全ての頂点に色を振り，重複してカウントしていないかを確認
    if con_i == len(connect) - 1:
        return 1

    # 頂点に色を塗っていく順番がconnect配列によって一意に定まっているため，
    # 次の頂点の色は必ず未定である0になっている．
    # よって，次の色が既に塗られているかどうかといった判定は不要
    res = 0
    for j in (1, 2, 3):
        color[connect[con_i + 1]] = j
        res += paint(con_i + 1)
    color[connect[con_i + 1]] = 0
    return res


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    E[a].append(b)
    E[b].append(a)

ans = 1
seen = [False] * N
for i in range(N):
    if seen[i]:
        continue
    # 連結成分を探索
    connect = []
    search_connect(i)

    color = [0] * N
    color[i] = 1
    # 最初の色が何でもそれぞれの色での場合の数は一緒なので，1色の場合の数を3倍
    ans *= paint(0) * 3

print(ans)

所感

A - Square Inequality

B - Intersection

C - IPFL

D - RGB Coloring 2

参考

Discussion