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

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

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

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

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

Twitter: u2dayo
マシュマロ： [https://marshmallow-qa.com/u2dayo]
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share

よかったらLGTMや拡散していただけると喜びます！

目次

ABC220 まとめ
A問題『Find Multiple』
B問題『Base K』
C問題『Long Sequence』
D問題『FG operation』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

• レート別問題正解率
• パフォーマンス目安
• 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC220 まとめ

全提出人数: 7469人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	ABC-----	600	117分	5608(5397)位
400	ABC-----	600	49分	4625(4419)位
600	ABC-----	600	25分	3826(3621)位
800	ABCD----	1000	86分	3006(2803)位
1000	ABCD----	1000	46分	2253(2050)位
1200	ABCD----	1000	19分	1632(1432)位
1400	ABCD-F--	1500	78分	1141(955)位
1600	ABCD-F--	1500	42分	785(602)位
1800	ABCDEF--	2000	94分	513(351)位
2000	ABCDEF--	2000	73分	326(187)位
2200	ABCDEF--	2000	57分	202(92)位
2400	ABCDEF--	2000	41分	132(43)位

色別の正解率

色	人数	A	B	C	D	E	F	G	H
灰	3128	94.4 %	77.4 %	60.9 %	10.1 %	0.6 %	2.5 %	0.1 %	0.0 %
茶	1344	99.5 %	97.6 %	95.8 %	52.8 %	3.6 %	8.3 %	0.0 %	0.0 %
緑	1041	99.7 %	98.8 %	97.9 %	87.0 %	8.9 %	27.3 %	0.2 %	0.0 %
水	653	99.7 %	98.9 %	98.8 %	97.1 %	34.0 %	55.0 %	1.2 %	0.0 %
青	389	99.2 %	99.0 %	99.5 %	98.7 %	69.7 %	85.1 %	5.4 %	0.0 %
黄	165	92.7 %	90.3 %	90.3 %	90.9 %	78.8 %	87.3 %	26.1 %	3.0 %
橙	37	91.9 %	91.9 %	91.9 %	91.9 %	89.2 %	86.5 %	73.0 %	13.5 %
赤	20	90.0 %	85.0 %	90.0 %	85.0 %	80.0 %	85.0 %	60.0 %	45.0 %

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

A問題『Find Multiple』

問題ページ：A - Find Multiple
灰コーダー正解率：94.4 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.7 %

入力

$A,B,C$ : $0$ 以上 $1000$ 以下の整数

考察

解法1. forループで全探索

$A$ から $B$ までの整数をforループで全探索します。$C$ の倍数（＝$C$ で割りきれる数＝$C$ で割った余りが $0$ の数）が $1$ つでも見つかればそれを出力して、見つからなければ $-1$ を出力します。

解法2. 算数

『$B$ 以下で最大の $C$ の倍数』は $\lfloor{\frac{B}{C}}\rfloor \times{C}$ で求められます。（$B$ を $C$ で割って切り捨てて $C$ を掛ける）これが $A$ 以上かどうか判定して、もしそうならそれを出力、そうでなければ $A$ 以上 $B$ 以下に $C$ の倍数はないので $-1$ を出力します。

例えば、$A=17,B=31,C=5$とします。$\lfloor{\frac{B}{C}}\rfloor \times{C}=\lfloor{\frac{31}{5}}\rfloor\times{5}=6\times{5}=30$です。これは $17$ 以上なので、$30$ を出力します。正の $5$ の倍数は $5,10,15,20,25,30,35,\dots$ で、$31$ 以下で最大の正の $5$ の倍数はたしかに $30$ です。

コード

解法1. forループで全探索

def solve():
    for i in range(A, B + 1):
        if i % C == 0:
            return i
    return -1  # A以上B以下の整数にCの倍数がなかったので、-1を返します


A, B, C = map(int, input().split())
print(solve())

解法2. 算数

A, B, C = map(int, input().split())
x = B // C * C  # xはB以下で最大のCの倍数
print(x)
print(x if x >= A else -1)

B問題『Base K』

問題ページ：B - Base K
灰コーダー正解率：77.4 %
茶コーダー正解率：97.6 %
緑コーダー正解率：98.8 %

入力

$K$ : $A,B$ が $K$ 進法で与えられる
$A,B$: $K$ 進法表記の整数

実装

$K$ 進法表記の整数 $A,B$ それぞれを$10$ 進法の整数に変換できれば、あとは $A\times{B}$ をするだけで解けます。

解法1. int関数を使う方法

Pythonの組み込み関数int関数を使うと、$K$ 進法の数値を $10$ 進法の数値に 変換することができます。

解法2. 自分で変換する

頑張って自分で変換します。$K$ 進法表記の下から $i$ 桁目が $x$ ならば、$10$ 進法表記では $x\times{K^{i}}$ 増えます。桁ごとに足し合わせればいいです。

コード

解法1. int関数を使う方法

K = int(input())
A, B = input().split()  # int関数で基数変換をするために、A, Bはstring（文字列）で受け取る必要があります
ans = int(A, K) * int(B, K)
print(ans)

解法2: 自分で変換する

def convert(x, k):
    ret = 0
    i = 0
    while x > 0:
        ret += (x % 10) * (k ** i)
        x //= 10
        i += 1
    return ret


K = int(input())
A, B = map(int, input().split())
ans = convert(A, K) * convert(B, K)
print(ans)

C問題『Long Sequence』

問題ページ：C - Long Sequence
灰コーダー正解率：60.9 %
茶コーダー正解率：95.8 %
緑コーダー正解率：97.9 %

入力

$N$ : $A$ の長さ
$A_i$ : $A$ の $i$ 番目の要素
$X$ : 和が初めて $X$ を超えるのは何項目か求める（以上ではない）

考察

$1$ 項ずつ $A$ の要素を $X$ が超えるまで足し合わせるとTLEになります。（例えば $N=2, A_1=1,A_2=1, X=10^{18}$ だと、答えは $10^{18}$ です）

そこで、まずは $A$ の $N$ 要素全体を何回使うかを、計算で求めます。これは、$A$ の総和を $sum_A$ とすると、$\lfloor{\frac{X}{sum_A}}\rfloor$ 回 です。（$X$ を $sum_A$ で割って切り捨てた回数）

それから、$A$ の一部をどこまで使うと$X$ を超えるか、forループで足し合わせて求めればいいです。

計算量は $O(N)$ です。

コード

N = int(input())
A = list(map(int, input().split()))
X = int(input())

ans = 0  # 現在の項数
S = 0  # 現在の総和
sum_A = sum(A)

c = X // sum_A  # A全体を何回使うか
ans += c * N  # A全体を何回使うか×Aの項数
S += c * sum_A  # A全体を何回使うか×Aの総和

for a in A:
    S += a
    ans += 1
    if S > X:  # Xを超えるときなので > です
        break

print(ans)

D問題『FG operation』

問題ページ：D - FG operation
灰コーダー正解率：10.1 %
茶コーダー正解率：52.8 %
緑コーダー正解率：87.0 %

入力

$N$ : $A$ の長さ
$A_i$ : $A$ の $i$ 番目の数（$0$ 以上 $9$ 以下の整数）

考察

二次元の動的計画法（DP）で解きます。

状態

$A$ の最初の要素を $0$ 要素目として数えることにします。

$dp[i][j]$ : $A$ の $i$ 要素目まで見て、一番左の要素が $j$ である操作の方法が何通りあるか

答え

$K=0,\,1\,,\dots\,,9$ に対して、$dp[N-1][K]$ がそれぞれの答えです。

初期状態

$dp[0][A_0] = 1$
$dp[i][j]=0\,(上以外のすべてのi,j)$

遷移

$i=0$ の状態（まだ一度も操作をしていない、$A$ が最初から変わっていないとき）は左端が$A_0$ の $1$ 通りで確定しているので、$A_0$ と $A_1$ に操作を行う、$i=1$ から状態を決めていきます。

状態 $dp[i-1][j]$ からの遷移は以下の通りです。

$f=(j+A_{i})\,\%\,10$
$g=(j\times{A_i})\,\%\,10$

とします。（それぞれ操作F,Gを行ったあと、新たに一番左になる数字です）

$dp[i][f]\,+=dp[i-1][j]$
$dp[i][g]\,+=dp[i-1][j]$

コード

def main():
    MOD = 998244353

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

    dp = [[0] * 10 for _ in range(N)]
    dp[0][A[0]] = 1

    for i in range(1, N):
        for j in range(10):
            f = (j + A[i]) % 10  # 一番左のjと、二番目に左のA[i]に操作Fをしたとき、新たに一番左になる数字
            g = (j * A[i]) % 10  # 操作G
            dp[i][f] += dp[i - 1][j]
            dp[i][g] += dp[i - 1][j]
            dp[i][f] %= MOD
            dp[i][g] %= MOD

    for i in range(10):
        print(dp[N-1][i])


if __name__ == '__main__':
    main()