Magicode logo
Magicode
0
13 min read

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

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

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

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

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

ABC262 まとめ

全提出人数: 7897人

パフォーマンス

パフォAC点数時間順位(Rated内)
200A-------1006分5559(5298)位
400AB------30028分4576(4316)位
600ABC-----60084分3743(3490)位
800ABC-----60044分2919(2669)位
1000ABC-----60025分2199(1951)位
1200ABCD----1000116分1601(1354)位
1400ABCD----100053分1130(886)位
1600ABCD----100022分782(551)位
1800ABCDE---150077分504(313)位
2000ABCDE---150051分337(166)位
2200ABCDE---150034分228(80)位
2400ABCDEF--2000107分132(36)位

色別の正解率

人数ABCDEFGEx
247198.1 %45.5 %33.9 %2.1 %0.6 %0.0 %0.1 %0.0 %
134999.0 %90.0 %80.0 %6.4 %0.7 %0.0 %0.0 %0.1 %
106198.9 %97.8 %94.7 %31.9 %4.9 %0.2 %0.0 %0.3 %
64398.1 %98.0 %96.0 %77.5 %27.2 %1.1 %0.0 %0.8 %
39696.7 %96.2 %95.2 %94.4 %58.8 %13.1 %0.2 %0.5 %
19194.8 %94.2 %94.2 %92.2 %72.8 %30.4 %1.1 %3.1 %
4390.7 %90.7 %90.7 %90.7 %81.4 %67.4 %7.0 %9.3 %
2996.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文)を使って、YY44 で割った余りが 22 になるまで、YY11 ずつ足していくのが楽です。

YY44 で 割った余りが 22 ではない間、YY11 ずつ足していく」という処理をしたいので、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 %

考察

頂点数 N100N\le{100} ですから、三重forループですべての 1a<b<cN1\le{a}\lt{b}\lt{c}\le{N} の組を全て試す O(N3)O(N^3) のアルゴリズムでも実行時間制限以内に余裕で計算が終わります。

グラフは隣接行列表現で受けとります。(N+1)×(N+1)(N+1)\times(N+1) の二次元リストGを用意します。初期値はすべてFalseにします。頂点 uuvv を結ぶ辺を受け取ったら、G[u][v]G[v][u]Trueに変更します。(無向辺は uu から vvvv から uu の双方向に移動できるからです)

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

辺の受け取りも合わせて、全体の計算量は O(N3+M)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,ji,j の組を調べる O(N2)O(N^2) のコードは間に合わないので、工夫が必要です。

問題文通りに、1i<jN1\le{i}\lt{j}\le{N} とします。次の 22 つの条件のうちいずれか片方を満たす整数 i,ji,j は、問題文の条件をすべて満たします。

  1. ai=ia_i=i かつ aj=ja_j=jmin(ai,aj)=ai ,max(ai,aj)=aj\mathrm{min}(a_i,a_j)=a_i\ , \mathrm{max}(a_i,a_j)=a_j
  2. ai=ja_i=j かつ aj=ia_j=imin(ai,aj)=aj ,max(ai,aj)=ai\mathrm{min}(a_i,a_j)=a_j\ , \mathrm{max}(a_i,a_j)=a_i

上記の条件 1122 が、同時に満たされることはありません(排反事象といいます)。なぜなら、条件 11 では ai=ia_i=i、条件 22 では ai=ja_i=j がそれぞれ満たすべき条件の 一部ですが、i<ji<j より、iji\ne{j} です。

したがって、条件 11 を満たすi,ji,j の組の数と、条件 22 を満たす i,ji,j の組の数を別々に数えて、足し合わせれば答えがわかります。

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

条件 1

aj=ja_j=j の場合です。i<ji\lt{j} 、すなわち aja_j より左側にある要素で、 ai=ia_i=i となる要素の個数がそのまま、jj を固定したときの組み合わせ数になります。

毎回そのような ii の数を数えていては間に合いません。そこで、今までに何回 aj=ja_j=j である jj が出現したかを、変数 samesame に記憶しておきます。(初期値は 00 です)

数列 aa を 左から(添字が小さいほうから)順に見ていって、aj=ja_j=j である jj が見つかったら、答えに samesame を足します。その後、same=same+1same=same+1 とします。

条件2

ajja_j\ne{j} の場合です。aj=ia_j=i とおきます。ただし、i<ji\lt{j} ですから、aj<ja_j\lt{j} を満たさなければスキップします。(そうしないと、同じ組を二重にカウントしてしまいます)

  • aj=ia_j=i
  • ai=ja_i=j

を両方満たすなら答えに 11 を足します。

コード

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 %

考察

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

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

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

動的計画法

動的計画法(DP)で解きます。

dp[i][j][k]\mathrm{dp[i][j][k]}: AAii 番目 の要素まで考慮して、jj 個選んでいて、総和を mm で割った余りが kk である組み合わせ数(を 998244353998244353 で割った余り)

このDPを m=1,2,3,,N1,Nm=1,2,3,\dots,N-1,N に対して行い、dp[N][m][0]\mathrm{dp[N][m][0]} を足し合わせれば良いです。

計算量

NN 個の整数から mm 個ちょうど選んで、総和が mm で割り切れる選び方の総数はいくつか?』というDPの計算量は O(Nm2)O(Nm^2) です。つまり、全体の計算量は O(Nm2)O(N\sum{m^2}) です。m2\sum{m^2} は およそ N33\dfrac{N^3}{3} なので、全体の計算量はO(N4)O(N^4) といえます。

N100N\le{100} とはいえ、PyPyのような低速な言語ではやや怪しそうに見えますが、定数倍の 33 分 の 11 倍が軽く、実行時間制限が 2.52.5 secであることも合わせて、十分通ります。

実装

考察では 33 次元DPで説明しましたが、一次元目の ii11 個前しか参照しないので、22 つの二次元配列を使ってDPするほうが、実装が楽で、速度も高速です。(コード 22 番目参照)

コード

どちらも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で解けそうな気がしますが、この大きさの無向グラフではうまくいかなそうです。

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

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

ある頂点 uu を赤く塗ったとき、良い辺の本数 DD がどう変化するか考えてみます。

周りに赤頂点がない場合

頂点 uu と直接辺で繋がった頂点に赤く塗られている頂点がなければ、頂点 uu から出ている辺の数(次数といいます)と同じだけ DD が増えます。

周りに赤頂点がある場合

頂点 uu と直接辺で繋がった頂点に、赤く塗られている頂点 vv11 つだけある場合を考えましょう。頂点 vv が赤くなければ、頂点 uu の次数と同じだけ DD が増えるはずです。しかし、「uvu-v は新たに良い辺にはならない。そのうえ、元々良い辺であった辺 uvu-v が、良い辺ではなくなる」ので、11 増えるはずだったところが、逆に 11 減ってしまうので、差し引き 2-2 です。つまり、(頂点uの次数)2(頂点uの次数)-2 だけ DD が増えます。

赤く塗られた頂点が 22 つ以上の場合も同様で、(頂点uの次数)2(頂点uと直接辺でつながっている赤い頂点の個数)(頂点uの次数)-2(頂点uと直接辺でつながっている赤い頂点の個数) だけ DD が増えます。

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

全体で KK 個頂点を赤く塗った場合を考えます。赤く塗った頂点の次数の総和を SS、赤く塗られた 22 つの頂点であって、辺で直接つながっている組の個数を RR とします。すると、良い辺の数 DD

D=S2RD=S-2R

と表されます。

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

上式を mod 2\mathrm{mod}\ 2 の世界で考えてみましょう。

DS2RS(mod2)D\equiv{S-2R}\equiv{S}\pmod{2}

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

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

次数が偶数・奇数の頂点の数を求めたあと、次数が奇数である頂点を0,2,4,0,2,4,\dots 個、偶数である頂点を K,K2,K4,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()

Discussion

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