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

4完0ペナ 33分でした

A - Blood Pressure

式が与えられているのでその通りに実装しました。誤差は生じても小さいので気にしなくて良いです。

A, B = map(int, input().split())
print((A-B)/3+B)

B - Cycle Hit

やり方はいくつかあると思いますが、問題文中の「ただし、全ての $S_i$ は H , 2B , 3B , HR のいずれかと一致します。」というところから、種類数を見れば確定できることがわかったので、そちらで実装しました。

l = set([])
for _ in range(4):
    s = input()
    l.add(s)
if len(l) == 4: print('Yes')
else: print('No')

C - chokudai

なんか似たような問題を直近やったような。ちゃんと復習してますか？と問われたような気持ちになりました。 DP が苦手でバグらせつつ、14分くらいでAC。ここ早解きできる人はアドバンテージだと思います。

DP 配列 1行目を初期化しているなら 0 行目いらなくない...？とか色々ありますがこれで出しました。。計算量は $O(|S|)$ です。

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    S = '*' + input()
    T = '#chokudai'
    DP = [[0] * len(S) for _ in range(len(T))]

    for j in range(1, len(S)):
        DP[1][j] = DP[1][j-1] + (S[j] == T[1])
        DP[1][j] %= MOD

    for i in range(2, len(T)):
        for j in range(1, len(S)):
            DP[i][j] = DP[i-1][j-1]*(S[j] == T[i]) + DP[i][j-1]
            DP[i][j] %= MOD
    print(DP[len(T)-1][len(S)-1])


if __name__ == "__main__":
    main()

D - Number of Shortest paths

最短経路かと思いきや、場合の数を求める問題でした。どの道路も同じ長さなので、幅優先探索でできそうです。最短で探索しつつ、その頂点に入ってくる最短経路の場合の数を足し合わせて管理していきます。

例えば下の図では、各都市で、都市1 からの最短距離を青字の数字、その都市に最短で到達するまでの場合の数をそれぞれ記載しています。最短距離は幅優先探索の容量で良いです。場合の数の方は、今見ている都市を fr、隣接している都市を v とおくと、都市1からの最短距離 d について d[v]-1 == d[fr] が成り立つときに、v で記録している場合の数を fr に加算していきます。

f:id:Xenous:20210724230128p:plain — 距離と場合の数の管理の例

計算量は $O(N+M)$ くらいだと思います。

提出コード

from collections import deque
import sys

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A-1].append(B-1)
        graph[B-1].append(A-1)
    
    fr = 0
    que = deque([fr])
    goneset = set([fr])
    pattern = [0] * N; pattern[0] = 1
    count = [0] * N
    while que:
        fr = que.popleft()
        for v in graph[fr]:
            pattern[fr] += pattern[v] * (count[fr]-1 == count[v])
            pattern[fr] %= MOD
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
    print(pattern[N-1])


if __name__ == "__main__":
    main()