ABC456 (Promotion of AtCoder Career Design DAY)参加録

結構実装が大変な回だった気がした。
今回もDまではすんなりいけ、Eも方針は思いついたものの実装しきれず。

A: Dice

3未満、19以上の目はサイコロ3つの和では実現できない。

def solve():
    input = sys.stdin.readline 
    X = int(input())
    if 3 <= X <= 18: print("Yes")
    else: print("No")

    return 0

B: 456

ゴリラ実装。
B問題なので。
6^3通りの出目のうち、(4, 5, 6)の組み合わせとなる出目の数を求める。

def solve():
    input = sys.stdin.readline 
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    total = 0
    # 4, 5, 6
    total += A.count(4) * B.count(5) * C.count(6)
    # 4, 6, 5
    total += A.count(4) * B.count(6) * C.count(5)
    # 5, 4, 6
    total += A.count(5) * B.count(4) * C.count(6)
    # 5, 6, 4
    total += A.count(5) * B.count(6) * C.count(4)
    # 6, 4, 5
    total += A.count(6) * B.count(4) * C.count(5)
    # 6, 5, 4
    total += A.count(6) * B.count(5) * C.count(4)

    print(total / (6 * 6 * 6))

    return 0

C: Not Adjacent

同じ文字が連続しない区間を伸ばせるだけ伸ばすと、その区間内でとれる全ての区間は条件を満たす。
あらかじめLまでの三角数を求めておくことで高速に計算できる。
変数名がfactorialになっているのは最初三角数ではなく階乗を計算してしまっていたため(苦笑)

def solve():
    input = sys.stdin.readline 
    S = input().strip("\n")
    count = 0
    mod = 998244353
    pre = ""
    left = 0
    L = len(S)
    factorial = [1] * (L + 1)
    for i in range(2, L+1):
        factorial[i] = (i + factorial[i-1]) % mod

    while left < L:
        right = left
        while right < L and S[right] != pre:
            pre = S[right]
            right += 1
        # print(f"Right: {right}, Left: {left}")
        count += factorial[right - left]
        pre = ""
        left = right
        
    print(count)

    return 0

D: Not Adjacent 2

DPでi番目時点での最後に使った文字毎に何通りあるのかを管理する。
i番目の文字を使う場合/使わない場合を考える。

def solve():
    input = sys.stdin.readline 
    S = input().strip("\n")
    L = len(S)
    mod = 998244353
    D = {"a": 0, "b": 1, "c": 2}
    DP = [[0, 0, 0] for _ in range(L)]
    init = D[S[0]]
    DP[0][init] = 1
    for i in range(1, L):
        s = S[i]
        idx = D[s]
        # 初めて使う
        DP[i][idx] = 1

        for j in range(3):
            # この文字を使う場合
            if j != idx:
                DP[i][idx] = (DP[i][idx] + DP[i-1][j]) % mod

            # この文字を使わない場合
            DP[i][j] = (DP[i][j] + DP[i-1][j]) % mod
    
    print(sum(DP[L-1]) % mod)

    return 0

E: Endless Holidays

ある都市にいるときに移動できる都市は次の日休日の都市のみなので、w曜日における移動経路を管理しておき、N都市 * W曜日を頂点とするグラフにおけるループ検出ができるとよい。
データの保持の仕方やらループ検出方法やらで実装に時間がかかり、方針は思いついたものの時間内に提出できなかった...

def solve():
    input = sys.stdin.readline 
    T = int(input())
    ans = ["No" for _ in range(T)]
    for t in range(T):
        N, M = map(int, input().split())
        E =[[] for _ in range(N)]
        for i in range(M):
            u, v = map(int, input().split())
            E[u-1].append(v-1)
            E[v-1].append(u-1)

        W = int(input())
        WN = [[] for _ in range(W)]
        WE = [[[] for n in range(N)] for _ in range(W)]

        S = [input().strip("\n") for _ in range(N)]
        for i, s in enumerate(S):
            for j in range(W):
                if s[j] == "o":
                    WN[j].append(i)
        for i, e in enumerate(E):
            ns = S[i]
            for ne in e:
                s = S[ne]
                for w in range(W):
                    if ns[w] == "o" and s[(w+1)%W] == "o":
                        WE[w][i].append(ne)
        
        
        def dfs(w, n, VD, FD):
            cycle = False
            VD[(w, n)] = True
            nd = (w+1)%W
            nes = WE[w][n]
            if S[n][nd] == "o":
                nes.append(n)
            
            for ne in nes:
                if not VD[(nd, ne)]:
                    cycle |= dfs(nd, ne, VD, FD)
                elif not FD[(nd, ne)]:
                    cycle = True
            FD[(w, n)] = True
            return cycle

        VD = {}
        FD = {}
        for w, nodes in enumerate(WN):
            for n in nodes:
                VD[(w, n)] = False
                FD[(w, n)] = False
        
        for n in WN[0]:
            if not VD[(0, n)]:
                if dfs(0, n, VD, FD):
                    ans[t] = "Yes"
                    break
        else:
            ans[t] = "No"

    
    print(*ans, sep="\n")


    return 0