🐶

[ABC262] AtCoder Beginner Contest 262（A-E 問題 Python）

2022/08/02に公開

Python

競技プログラミング

AtCoder

tech

AtCoder Beginner Contest 262 の復習記録です。
A問題からE問題までやります。使用言語はPythonです。

A問題

考え方

こういう問題は、何の数字が何に変化してほしいかを考えると分かりやすいです。

元の数字(Y)	2018	2019	2020	2021	2022	2023
変化後の数字（出力値）	2018	2022	2022	2022	2022	2026

4ごとに変わりますので、4で割って整数切り捨てを行い、4をかけると上手くいきそうです。また、2018-2019、2022-2023 の間に数値の変換点がありますので、+1してから、4で割ると良いと分かります。

元の数字(Y)	2018	2019	2020	2021	2022	2023
Y+1	2019	2020	2021	2022	2023	2024
(Y+1) // 4	503	504	504	504	504	505
(Y+1) // 4 * 4	2016	2020	2020	2020	2020	2024
(Y+1) // 4 * 4 + 2	2018	2022	2022	2022	2022	2026

提出コード

Y = int(input())
ans = (Y+1) //4 * 4 + 2
print(ans)

B問題

考え方

制約が小さいので、全探索して間に合います。
E[ $i$ ][ $j$ ] = 1 であれば $i$ と $j$ を結ぶ辺があります。

提出コード

N,M = map(int,input().split())
E = [[0]*N for _ in range(N)]

for _ in range(M):
    u,v = map(int,input().split())
    u-=1; v-=1  #0-indexedに変換
    E[u][v] = E[v][u] = 1

ans = 0
for a in range(N-2):
    for b in range(a+1,N-1):
        if E[a][b] == 0: #a,bに辺がなければ次ステップは省略
            continue
        for c in range(b+1,N):
            if E[b][c] == 1 and E[c][a] == 1:
                ans += 1
print(ans)

C問題

考え方

条件を満たす $i$ , $j$ の組合せは、
(1) $a_i = j$ かつ $a_j = i$ となるとき（ $i$ , $j$ が入れ替わるパターン）

(2) $a_i = i$ かつ $a_j = j$ となるとき

のいずれかです。(1)の場合は、そのままカウントすれば良いですが、(2)の場合については、 $a_n = n$ となるような $n$ の数を数え、それを $cnt$ とおいて、 $cnt$ 個から2つを選ぶ組合せを考えれば良いので、 $cnt \times (cnt-1) //2$ 通りになります。

提出コード

N = int(input())
a = list(map(int,input().split()))

ans = 0
cnt = 0
for i in range(N):
    if a[i] == i+1:
        cnt += 1
    
    elif a[i]>i+1 and a[a[i]-1] == i+1:
        ans += 1

ans += (cnt-1)*cnt//2
print(ans)

D問題

考え方

割る数が変わるものは同時に処理できませんので、平均をとる上で何個(項)選択するかについては、個々に考える必要があります。
$i$ 個の項を選択するとき、 $j$ 番目まで見た場合の、合計値としてあり得る値と、その場合の数をdefaultdictの、keyとvalueに記録していきます。

入力例1で $i=3$ を考えたときを例に挙げると、

さらに、keyについては、 $i$ で割った余りだけ考えれば十分なので、

とすれば良いです。DPの更新を添字が大きいものから評価するようにすれば、準備しなければいけないDPの次元数を節約することができます（ $j$ については次元を分けて準備する必要がない）。
$j$ 番目まで見て、 $k$ 個(項)選択したとき、合計値を $i$ で割った余りが $r$ となる場合の数（パターン数）がDP[ $k$ ][ $r$ ]となります。最終的に求めたいのは余り $0$ となる場合なので、DP[ $i$ ][ $0$ ]を加算して集めます。

提出コード

from collections import defaultdict
MOD = 998244353
N = int(input())
a = list(map(int,input().split()))

def i_select(i):
    DP = [defaultdict(int) for _ in range(i+1)]
    DP[0][0] = 1
    for j in range(N):
        for k in range(i-1,-1,-1):　#大きい方から処理する
            for r, cnt in DP[k].items():
                DP[k+1][(r+a[j])%i] += cnt
                DP[k+1][(r+a[j])%i] %= MOD
    return DP[i][0]

ans = 0
for i in range(1,N+1):
    ans += i_select(i)
    ans %= MOD

print(ans)

E問題

考え方

公式解説が分かりやすいです。
「異なる色で塗られた頂点を結ぶ辺の本数は偶数」という条件を「赤色に塗った頂点の次数の合計が偶数となる」と言い換えます。頂点を順番に見ていき、赤色に塗った頂点につながる辺を数えていくと、ある辺の両端の頂点の色によって、辺が数えられる回数が変わります。

辺が結ぶ頂点の色	数えられる回数
赤と赤	2回
赤と青	1回
青と青	0回

赤と青の異なる色を結ぶ辺は、1回(奇数回)しか数えられないので、これが偶数個であることと、赤色に塗った頂点の次数の合計が偶数となることは同値となります。

こう考えると、もうグラフで考える必要はなく、それぞれの頂点の次数にだけ注目すれば良くなります。もっと言えば、それぞれの頂点の次数の偶奇だけ見れば良いです。次数が奇数の頂点のうち、赤色に塗られるのは偶数個です。

各頂点の次数の偶奇を調べて、次数が奇数の頂点の個数(odd)と、次数が偶数の頂点の個数(even)をそれぞれ求めます。次数が奇数の頂点 odd 個の中から、赤色に塗る偶数個( $i=0,2,4,\dots$ )を選ぶ組合せを考え、残りの赤頂点は、even 個の中から $K-i$ 個選びます。
組合せについて、998244353で割った余りを考えるので、逆元を用います。

提出コード

逆元の準備をします。

MOD = 998244353
N,M,K = map(int,input().split())

fact = [1]*(N+1)
invfact = [0]*(N+1)
for i in range(1,N+1):
    fact[i] = fact[i-1] * i % MOD

invfact[N] = pow(fact[N], MOD-2, MOD)

for i in range(N,0,-1):
    invfact[i-1] = invfact[i] * i % MOD

def Cmb(n,k):
    if n<0 or k<0 or n<k:
        return 0
    r = fact[n]
    r *= invfact[k]
    r %= MOD
    r *= invfact[n-k]
    r %= MOD
    return r

$deg$ に次数(degree)の偶奇を記録します。%2を見ることで、0または1の値しかとりません。
次数が偶数のとき $deg=0$ なので、その後で $sum(deg)$ をすれば、次数が奇数の頂点の個数が求まります。

deg = [0]*N
for _ in range(M):
    u,v = map(int,input().split())
    u-=1; v-=1
    deg[u] = (deg[u]+1)%2
    deg[v] = (deg[v]+1)%2

odd = sum(deg)
even = N-odd
ans = 0
for i in range(0,min(odd,K)+1,2):
    ans += Cmb(odd,i) * Cmb(even,K-i)
    ans %= MOD

print(ans)

A問題

考え方

提出コード

B問題

考え方

提出コード

C問題

考え方

提出コード

D問題

考え方

提出コード

E問題

考え方

提出コード

Discussion