20か月前公開・20か月前更新・13 min read

【AtCoder解説】PythonでABC262のA,B,C,D,E問題を制する！

AtCoder競技プログラミングPythonPython3AtCoderBeginnerContest

https://cdn.magicode.io/media/notebox/blob_fLRrSoX

ABC262のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

シンプル：余計なことを考えずに済む
実装が楽：ミスやバグが減ってうれしい
時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッター、マシュマロまでお気軽にどうぞ！

Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

ABC262 まとめ

全提出人数: 7897人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	A-------	100	6分	5559(5298)位
400	AB------	300	28分	4576(4316)位
600	ABC-----	600	84分	3743(3490)位
800	ABC-----	600	44分	2919(2669)位
1000	ABC-----	600	25分	2199(1951)位
1200	ABCD----	1000	116分	1601(1354)位
1400	ABCD----	1000	53分	1130(886)位
1600	ABCD----	1000	22分	782(551)位
1800	ABCDE---	1500	77分	504(313)位
2000	ABCDE---	1500	51分	337(166)位
2200	ABCDE---	1500	34分	228(80)位
2400	ABCDEF--	2000	107分	132(36)位

色別の正解率

色	人数	A	B	C	D	E	F	G	Ex
灰	2471	98.1 %	45.5 %	33.9 %	2.1 %	0.6 %	0.0 %	0.1 %	0.0 %
茶	1349	99.0 %	90.0 %	80.0 %	6.4 %	0.7 %	0.0 %	0.0 %	0.1 %
緑	1061	98.9 %	97.8 %	94.7 %	31.9 %	4.9 %	0.2 %	0.0 %	0.3 %
水	643	98.1 %	98.0 %	96.0 %	77.5 %	27.2 %	1.1 %	0.0 %	0.8 %
青	396	96.7 %	96.2 %	95.2 %	94.4 %	58.8 %	13.1 %	0.2 %	0.5 %
黄	191	94.8 %	94.2 %	94.2 %	92.2 %	72.8 %	30.4 %	1.1 %	3.1 %
橙	43	90.7 %	90.7 %	90.7 %	90.7 %	81.4 %	67.4 %	7.0 %	9.3 %
赤	29	96.5 %	96.5 %	100.0 %	96.5 %	89.7 %	79.3 %	34.5 %	31.0 %

※表示レート、灰に初参加者は含めず

A問題『World Cup』

問題ページ：A - World Cup
灰コーダー正解率：98.1 %
茶コーダー正解率：99.0 %
緑コーダー正解率：98.9 %

考察

if文で場合分けしてもいいですが、何も考えずにwhile文（またはfor文）を使って、

Y

を

4

で割った余りが

2

になるまで、

Y

に

1

ずつ足していくのが楽です。

「 $Y$ を $4$ で割った余りが $2$ ではない間、 $Y$ に $1$ ずつ足していく」という処理をしたいので、while文の条件は Y % 4 != 2 です。

コード

def solve():
    Y = int(input())
    while Y % 4 != 2:
        Y += 1
    return Y


print(solve())

B問題『Triangle (Easier)』

問題ページ：B - Triangle (Easier)
灰コーダー正解率：45.5 %
茶コーダー正解率：90.0 %
緑コーダー正解率：97.8 %

考察

頂点数

N\le{100}

ですから、三重forループですべての

1\le{a}\lt{b}\lt{c}\le{N}

の組を全て試す

O(N^3)

のアルゴリズムでも実行時間制限以内に余裕で計算が終わります。

グラフは隣接行列表現で受けとります。

(N+1)\times(N+1)

の二次元リストGを用意します。初期値はすべてFalseにします。頂点

u

と

v

を結ぶ辺を受け取ったら、G[u][v]とG[v][u]をTrueに変更します。（無向辺は

u

から

v

、

v

から

u

の双方向に移動できるからです）

あとは、三重ループで問題文に書いてある条件を判定するだけです。

辺の受け取りも合わせて、全体の計算量は

O(N^3+M)

です。

コード

def solve():
    N, M = map(int, input().split())
    G = [[False] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        G[a][b] = G[b][a] = True
    ans = 0
    for a in range(1, N + 1):
        for b in range(a + 1, N + 1):
            for c in range(b + 1, N + 1):
                if G[a][b] and G[b][c] and G[c][a]:
                    ans += 1
    return ans


print(solve())

C問題『Min Max Pair』

問題ページ：C - Min Max Pair
灰コーダー正解率：33.9 %
茶コーダー正解率：80.0 %
緑コーダー正解率：94.7 %

考察

すべての

i,j

の組を調べる

O(N^2)

のコードは間に合わないので、工夫が必要です。

問題文通りに、

1\le{i}\lt{j}\le{N}

とします。次の

2

つの条件のうちいずれか片方を満たす整数

i,j

は、問題文の条件をすべて満たします。

$a_i=i$ かつ $a_j=j$ （ $\mathrm{min}(a_i,a_j)=a_i\ , \mathrm{max}(a_i,a_j)=a_j$ ）
$a_i=j$ かつ $a_j=i$ （ $\mathrm{min}(a_i,a_j)=a_j\ , \mathrm{max}(a_i,a_j)=a_i$ ）

上記の条件

1

と

2

が、同時に満たされることはありません（排反事象といいます）。なぜなら、条件

1

では

a_i=i

、条件

2

では

a_i=j

がそれぞれ満たすべき条件の一部ですが、

i<j

より、

i\ne{j}

です。

したがって、条件

1

を満たす

i,j

の組の数と、条件

2

を満たす

i,j

の組の数を別々に数えて、足し合わせれば答えがわかります。

以下、数列の左から、すなわち添字が小さい順に見ていきます。

条件 1

a_j=j

の場合です。

i\lt{j}

、すなわち

a_j

より左側にある要素で、

a_i=i

となる要素の個数がそのまま、

j

を固定したときの組み合わせ数になります。

毎回そのような

i

の数を数えていては間に合いません。そこで、今までに何回

a_j=j

である

j

が出現したかを、変数

same

に記憶しておきます。（初期値は

0

です）

数列

a

を左から（添字が小さいほうから）順に見ていって、

a_j=j

である

j

が見つかったら、答えに

same

を足します。その後、

same=same+1

とします。

条件2

a_j\ne{j}

の場合です。

a_j=i

とおきます。ただし、

i\lt{j}

ですから、

a_j\lt{j}

を満たさなければスキップします。（そうしないと、同じ組を二重にカウントしてしまいます）

$a_j=i$
$a_i=j$

を両方満たすなら答えに

1

を足します。

コード

def solve():
    N = int(input())
    A = [-1] + list(map(int, input().split()))  # 1はじまりにしたいので、A[0]に適当なゴミを入れておきます（使いません）
    ans = 0
    same = 0
    for j, a in enumerate(A[1:], 1):
        if a == j:  # 条件1
            ans += same
            same += 1
        elif a < j and A[a] == j:
            ans += 1
    return ans

print(solve())

D問題『I Hate Non-integer Number』

問題ページ：D - I Hate Non-integer Number
灰コーダー正解率：2.1 %
茶コーダー正解率：6.4 %
緑コーダー正解率：31.9 %

考察

『整数を $m$ 個選んで、選んだ項の平均値が整数である条件』は『選んだ $m$ 個の整数の総和が、 $m$ で割り切れる』ことです。

『 $N$ 個の整数から $m$ 個ちょうど選んで、総和が $m$ で割り切れる選び方の総数はいくつか？』という問題を解くことを考えます。この問題が解ければ、 $m$ に $1,2,3,\dots,N-1,N$ を代入したときの答えを求めて全て足し合わせたものが、この問題の答えになるからです。

『 $N$ 個の整数から $m$ 個ちょうど選んで、総和が $m$ で割り切れる選び方の総数はいくつか？』をもう少し言い換えると、『 $N$ 個の整数から $m$ 個ちょうど選んで、総和を $m$ で割った余りが $0$ になる選び方の総数はいくつか？』です。

動的計画法

動的計画法（DP）で解きます。

\mathrm{dp[i][j][k]}

A

の

i

番目の要素まで考慮して、

j

個選んでいて、総和を

m

で割った余りが

k

である組み合わせ数（を

998244353

で割った余り）

このDPを

m=1,2,3,\dots,N-1,N

に対して行い、

\mathrm{dp[N][m][0]}

を足し合わせれば良いです。

計算量

『 $N$ 個の整数から $m$ 個ちょうど選んで、総和が $m$ で割り切れる選び方の総数はいくつか？』というDPの計算量は

O(Nm^2)

です。つまり、全体の計算量は

O(N\sum{m^2})

です。

\sum{m^2}

はおよそ

\dfrac{N^3}{3}

なので、全体の計算量は

O(N^4)

といえます。

N\le{100}

とはいえ、PyPyのような低速な言語ではやや怪しそうに見えますが、定数倍の

3

分の

1

倍が軽く、実行時間制限が

2.5

secであることも合わせて、十分通ります。

実装

考察では

3

次元DPで説明しましたが、一次元目の

i

は

1

個前しか参照しないので、

2

つの二次元配列を使ってDPするほうが、実装が楽で、速度も高速です。（コード

2

番目参照）

コード

どちらもPyPyで提出しないとTLEになると思います。

3次元版

MOD = 998_244_353


def main():
    def solve(m):
        dp = [[[0] * m for _ in range(m + 1)] for _ in range(N+1)]
        dp[0][0][0] = 1  # 0個選んで余りが0は1通りです
        for i, x in enumerate(A):
            for j in range(m+1):
                for k in range(m):
                    if j + 1 <= m:
                        k2 = (k + x) % m
                        dp[i+1][j+1][k2] += dp[i][j][k]
                        dp[i+1][j+1][k2] %= MOD
                    dp[i+1][j][k] += dp[i][j][k]
                    dp[i+1][j][k] %= MOD

        return dp[N][m][0]  # m個選んで総和の余りが0

    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(1, N + 1):
        ans += solve(i)
        ans %= MOD  # 忘れずにMODをとりましょう
    print(ans)

if __name__ == '__main__':
    main()

2次元版

MOD = 998_244_353


def main():
    def solve(m):
        dpp = [[0] * m for _ in range(m + 1)]
        dpp[0][0] = 1  # 0個選んで余りが0は1通りです
        for x in A:
            dpn = [_r[:] for _r in dpp]
            for i in range(m):
                for j in range(m):
                    j2 = (j + x) % m
                    dpn[i + 1][j2] += dpp[i][j]
                    dpn[i + 1][j2] %= MOD
            dpp = dpn
        return dpp[m][0]  # m個選んで総和の余りが0

    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(1, N + 1):
        ans += solve(i)
        ans %= MOD  # 忘れずにMODをとりましょう
    print(ans)

if __name__ == '__main__':
    main()

E問題『Red and Blue Graph』

問題ページ：E - Red and Blue Graph
灰コーダー正解率：0.6 %
茶コーダー正解率：0.7 %
緑コーダー正解率：4.9 %

※図を入れたかったのですが、力つきたので手元の紙で実験してみてください

考察

木であればDPで解けそうな気がしますが、この大きさの無向グラフではうまくいかなそうです。

グラフを塗って法則を見極めてみる

長いので、『異なる色で塗られた頂点を結ぶ辺』のことを『良い辺』と呼ぶことにしましょう。

ある頂点

u

を赤く塗ったとき、良い辺の本数

D

がどう変化するか考えてみます。

周りに赤頂点がない場合

頂点

u

と直接辺で繋がった頂点に赤く塗られている頂点がなければ、頂点

u

から出ている辺の数（次数といいます）と同じだけ

D

が増えます。

周りに赤頂点がある場合

頂点

u

と直接辺で繋がった頂点に、赤く塗られている頂点

v

が

1

つだけある場合を考えましょう。頂点

v

が赤くなければ、頂点

u

の次数と同じだけ

D

が増えるはずです。しかし、「辺 $u-v$ は新たに良い辺にはならない。そのうえ、元々良い辺であった辺 $u-v$ が、良い辺ではなくなる」ので、

1

増えるはずだったところが、逆に

1

減ってしまうので、差し引き

-2

です。つまり、

(頂点uの次数)-2

だけ

D

が増えます。

赤く塗られた頂点が

2

つ以上の場合も同様で、

(頂点uの次数)-2(頂点uと直接辺でつながっている赤い頂点の個数)

だけ

D

が増えます。

K個塗る場合～遇奇を考えよう～

全体で

K

個頂点を赤く塗った場合を考えます。赤く塗った頂点の次数の総和を

S

、赤く塗られた

2

つの頂点であって、辺で直接つながっている組の個数を

R

とします。すると、良い辺の数

D

は

D=S-2R

と表されます。

ここで、この問題で問われているのは『良い辺の本数が偶数である塗り方』の総数です。つまり、『 $D$ を $2$ で割った余りが $0$ になる塗り方』の総数を問われています。

上式を

\mathrm{mod}\ 2

の世界で考えてみましょう。

D\equiv{S-2R}\equiv{S}\pmod{2}

つまり、赤く塗った頂点がいくつ隣接していようと、 $D$ の遇奇に影響を及ぼしません。結局 $S$ が偶数、すなわち $K$ 個選んだ頂点の次数の総和が偶数であれば良いです。

S

が偶数になる条件は、次数が奇数である頂点が偶数個選ばれることです。

次数が偶数・奇数の頂点の数を求めたあと、次数が奇数である頂点を

0,2,4,\dots

個、偶数である頂点を

K,K-2,K-4,\dots

個選ぶ場合の組み合わせ数をかけ合わせて、すべて足し合わせればいいです。

コード

MOD = 998_244_353


def main():
    def solve():
        N, M, K = map(int, input().split())
        degree = [0] * N
        for _ in range(M):
            a, b = map(int, input().split())
            degree[a - 1] += 1
            degree[b - 1] += 1
        degree = [x % 2 for x in degree]
        even_cnt = degree.count(0)  # 次数が偶数の頂点数
        odd_cnt = degree.count(1)  # 次数が奇数の頂点数

        comb = comb_precalc(MOD)
        ret = 0
        for odd in range(0, K + 1, 2):
            even = K - odd
            ret += comb(even_cnt, even) * comb(odd_cnt, odd)
            ret %= MOD
        return ret

    print(solve())


def comb_precalc(mod, n_init=200000):
    def extend_fac_inv_list(k):
        nonlocal n_max
        extend_len = max(n_max // 2, k - n_max)  # 最低1.5倍に伸ばす
        fac.extend([0] * extend_len)
        inv.extend([0] * extend_len)
        for i in range(n_max + 1, n_max + 1 + extend_len): fac[i] = fac[i - 1] * i % mod
        inv[-1] = pow(fac[-1], mod - 2, mod)
        for i in reversed(range(n_max + 1, n_max + extend_len)): inv[i] = inv[i + 1] * (i + 1) % mod
        n_max += extend_len

    def f(n, r):
        if n > n_max: extend_fac_inv_list(n)
        return fac[n] * inv[r] % mod * inv[n - r] % mod if n >= r else 0

    fac, inv, n_max = [1], [1], 0
    extend_fac_inv_list(n_init)
    return f


if __name__ == '__main__':
    main()

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

Discussion

コメントにはログインが必要です。

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

【AtCoder解説】PythonでABC262のA,B,C,D,E問題を制する！

ABC262 まとめ

パフォーマンス

色別の正解率

A問題『World Cup』

考察

コード

B問題『Triangle (Easier)』

考察

コード

C問題『Min Max Pair』

考察

条件 1

条件2

コード

D問題『I Hate Non-integer Number』

考察

動的計画法

計算量

実装

コード

3次元版

2次元版

E問題『Red and Blue Graph』

考察

グラフを塗って法則を見極めてみる

周りに赤頂点がない場合

周りに赤頂点がある場合

K個塗る場合 ～遇奇を考えよう～

コード

Discussion

コメントにはログインが必要です。

K個塗る場合～遇奇を考えよう～