AtCoder ABC 262 参戦記

今回はDまでの4完。Eは解説ACです。

あーレートの溶ける音ー。

atcoder.jp

A問題 (World Cup)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    Y = int(input())
    if Y % 4 == 0: print(Y + 2)
    elif Y % 4 == 1: print(Y + 1)
    elif Y % 4 == 2: print(Y)
    else: print(Y + 3)
    return 0
  
if __name__ == "__main__":
    solve()

色々考えるのがめんどくさかったので、(どうせ4だし)全パターン分岐しました。

B問題 (Triangle(Easier))

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    E = [[0 for _ in range(N)] for i in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        E[u-1][v-1] = E[v-1][u-1] = 1
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            for k in range(j+1, N):
                if E[i][j] == 1 and E[j][k] == 1 and E[k][i] == 1:
                    ans += 1
    print(ans)
    return 0
  
if __name__ == "__main__":
    solve()

高々頂点100個なので、全頂点の組み合わせを確認して条件を満たすものをカウントしました。

C問題 (Min Max Pair)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N = int(input())
    A = list(map(int, input().split()))
    same = 0
    ans = 0
    for i in range(N):
        if A[i] == i + 1: 
            ans += same
            same += 1
        else:
            if A[i] < i + 1:
                if A[A[i] - 1] == i + 1: ans += 1
    print(ans)
    return 0
  
if __name__ == "__main__":
    solve()

i番目がiならば、それまでに出てきたインデックスと数値が同じものの個数を加算。

違うなら、i番目の数値aをインデックスとする箇所の数値を見てiであれば加算。

小さいほうだけ見るようにして二重にカウントするのを防いでいます。

D問題 (I Hate Non-integer Number)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 998244353
    N = int(input())
    A = list(map(int, input().split()))
    ans = N
    if N == 1:
        print(ans)
        return 0 
    for i in range(2, N + 1): #i個選ぶ
        DP = [[[0 for _ in range(i)] for j in range(i + 1)] for a in range(N)]
        DP[0][1][A[0] % i] = 1
        DP[0][0][0] = 1
        for a in range(1, N):
            for count in range(i):
                for m in range(i):
                    if DP[a-1][count][m] > 0:
                        DP[a][count + 1][(m + A[a]) % i] += DP[a-1][count][m]
                        DP[a][count + 1][(m + A[a]) % i] %= mod
                        DP[a][count][m] += DP[a-1][count][m]
                        DP[a][count][m] %= mod 
            DP[a][i][0] += DP[a-1][i][0] 
            DP[a][i][0] %= mod
        ans += DP[N-1][i][0]
        ans %= mod
    print(ans)
    return 0
  
if __name__ == "__main__":
    solve()

要素を何個選ぶかを決め打ちしてDP。

何個選ぶか決めたらmodで計算できるので、後はN^4の計算量で通るかですが...10^8で2.5sならpypyで通るのでそのまま投げます。

ほんとはDPの次数が一つ減るはず(なんか合わなかったから減らさなかったけど)。

E問題 (Red and Blue Graph)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 998244353
    N, M, K = map(int, input().split())
    E = [0 for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        E[u-1] += 1
        E[v-1] += 1
    odd = 0
    for e in E:
        odd += e % 2
 
    fact = [1] * (N + 1)
    fact[1] = 1
    for i in range(2, N + 1):
        fact[i] = (fact[i-1] * i) % mod
    revFact = [1] * (N + 1)
    revFact[N] = pow(fact[N], mod - 2, mod)
    for i in reversed(range(2, N)):
        revFact[i] = (revFact[i+1] * (i+1)) % mod
 
    ans = 0
    for i in range(min(odd, K) + 1):
        if i % 2 == 1 or N - odd < K - i: continue
        # 次数がoddのものからi個、evenのものからK-i個赤く塗る
        ans += comb(odd, i, fact, revFact, mod) * comb(N - odd, K - i, fact, revFact, mod)
        ans %= mod
    print(ans)
 
    return 0
  
if __name__ == "__main__":
    solve()

どうせ1回全頂点走査するだけでなんとかなるんでしょ、とは思うものの次数に着目するとこにたどり着かず...