ARC110

鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110） - AtCoder

A

• 全部掛けて+1したら余りの条件を満たすけど、大きくなりすぎるので最小公倍数を求めました
• 関連: 中国剰余定理 python

from math import gcd
N = int(input())
x = 1
for i in range(2, N + 1):
    g = gcd(x, i)
    x *= i // g
print(x + 1)

B

• 要するにこのオートマトンが受理するかどうか
  • 
• 入力が1文字の時にトラップがあるのでそこだけ場合わけ python

def solve(N, T):
    if N == 1:
        if T == "1":
            return 2 * 10 ** 10
        elif T == "0":
            return 10 ** 10

    state = [True, True, True]
    for c in T:
        nextState = [0] * 3
        for i in range(3):
            nextState[i] = state[i - 1] and (c == "011"[i])
        state = nextState
    ret = 0
    for i in range(3):
        if state[i]:
            ret += (3 * 10 ** 10 - ((i - N) % 3 + N)) // 3 + 1
    return ret

ARC110C ARC110D