作成日 : 2021-09-27
更新日 : 2021-11-01
11 min readAtCoder

【備忘録】AtCoder Beginner Contest 220 A~D問題

AtCoder Beginner Contest 220のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 220」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 220」

コンテスト情報

• コンテスト時間 : 100分
• レーティング更新対象 : 0 - 1999

配点

ルール

1. コンテスト中に問題に正解すると点数を獲得できます。
2. 順位は総合得点で決定します。
3. 同点の場合は提出時間の早い人が上の順位になります。
4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> Find Multiple

問題文

A以上B以下であるようなCの倍数を、1つ出力してください。条件を満たす数が存在しない場合は-1を出力してください。

制約

• 1 ≤ A ≤ B ≤ 1000
• 1 ≤ C ≤ 1000
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

1A B C

出力

答えを出力せよ。条件を満たす数が存在しない場合は-1を出力せよ。

本問題は、AtCoder株式会社で作成された、A - Find Multiple問題を参照しております。

Contest中に考えたこと

• A以上B以下の倍数が見つかるかどうかのflagを用意する。flagをFalseにしておく。
• A以上B以下の倍数が見つかるまで、while文を回す。
• A以上B以下の倍数が見つかったら、flagをTrueにし、while文をbreakする。
• A以上B以下の倍数が見つかるまで、C = C + Cを繰り返す。(次のCの倍数の値がA以上B以下に含まれるか、確認するため。)
• B < Cになったら、while文をbreakする。(検証終了のため)
• flagがTrueのとき、現在のCの値を出力する。flagがFalseのとき、-1を出力する。

解答

1# 標準入力を受け付ける。
2A, B, C = map(int, input().split())
3 
4# A以上B以下の倍数が見つかるかどうかのflagを用意する。flagをFalseにしておく。
5flag = False
6# A以上B以下の倍数が見つかるまで、while文を回す。
7while True:
8    # A以上B以下の倍数が見つかったら、flagをTrueにし、while文をbreakする。
9    if A <= C and B >= C:
10        flag = True
11        break
12    
13    # B < Cになったら、while文をbreakする。(検証終了のため)
14    if B < C:
15        break
16 
17    # A以上B以下の倍数が見つかるまで、C = C + Cを繰り返す。(次のCの倍数の値がA以上B以下に含まれるか、確認するため。)
18    C += C
19
20# flagがTrueのとき、現在のCの値を出力する。flagがFalseのとき、-1を出力する。 
21if flag:
22    print(C)
23else:
24    print(-1)

B -> Base K

問題文

整数A, BがK進法表記で与えられます。A × Bを10進法表記で出力してください。

注記

K進法表記については、Wikipedia「位取り記数法」を参照してください。

制約

• 2 ≤ K ≤ 10
• 1 ≤ A, B ≤ 10の5乗
• A, BはK進法表記で与えられる

入力

入力は以下の形式で標準入力から与えられる。

1K
2A B

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、B - Base K問題を参照しております。

Contest中に考えたこと

• 「python K進法」でGoogle検索して、実装方法を探した。こちらのサイトを参考にした。

解答

1# 標準入力を受け付ける。
2K = int(input())
3 
4A, B = input().split()
5
6# 参考 : https://science-log.com/python%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0tips%E9%9B%86/%E3%80%90python%E3%80%91%E8%A8%98%E6%95%B0%E6%B3%95%E3%81%AE%E5%A4%89%E6%8F%9B/ 
7print(int(str(A), K) * int(str(B), K))

C -> Long Sequence

問題文

https://atcoder.jp/contests/abc220/tasks/abc220_c

制約

• 1 ≤ N ≤ 10の5乗
• 1 ≤ Ai ≤ 10の9乗
• 1 ≤ X ≤ 10の18乗
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

1N
2A1 … AN
3​X

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、C - Long Sequence問題を参照しております。

Contest中に考えたこと

• Aiを繰り返しカウントして、Xを超えるまで検証するのは、制約上難しい。
• Aの配列を合算しておく。
• XはAの配列を合算したものを、何個ぶん持てるのか演算する。
• Aiのはじめの項(A0)からXを超えているのか検証するのではなく、(Xが持つことのできる、Aの配列を合算したものの個数) x (Aの配列を合算したもの)から検証を始める。

解答

1# 標準入力を受け付ける。
2N = int(input())
3 
4A = list(map(int, input().split()))
5 
6X = int(input())
7 
8# Aの配列を合算する。
9ASum = sum(A)
10 
11# XはAの配列を合算したものを、何個ぶん持てるのか演算する。(はじめの項(A0)から足し合わせて、制約違反するのを防ぐため。)
12cnt = X // ASum
13 
14# Aiのはじめの項(A0)からXを超えているのか検証するのではなく、(Xが持つことのできる、Aの配列を合算したものの個数) x (Aの配列を合算したもの)から検証を始める。
15AiList = cnt * ASum
16remainCnt = 0
17for i in range(len(A)):
18    # Xを超えたら検証を終了する。
19    if AiList > X:
20        break
21    # Ai項を足し合わせる。(Xを超えるか検証を続けるため。)
22    AiList += A[i]
23    # Xを超えるために費やした、残りの項数を数える。
24    remainCnt += 1
25 
26print(cnt * len(A) + remainCnt)

D -> FG operation

問題文

0以上9以下の整数からなる長さNの数列A=(A1, …, AN)があり、この順に左から右に並んでいます。数列の長さが1になるまで、操作Fまたは操作Gを繰り返し行います。

• 操作F : 左端の2つの値(x, yとする)を削除した後、一番左に(x + y) % 10を挿入する
• 操作G : 左端の2つの値(x, yとする)を削除した後、一番左に(x × y) % 10を挿入する

なお、a % bはaをbで割った余りを意味します。

K = 0, 1, …, 9について、以下の問題に答えてください。

操作手順としてあり得るものは2のN−1乗通りありますが、このうち最終的に残る値がKとなる操作手順は何通りありますか？ただし答えは非常に大きくなる可能性があるので、998244353で割った余りを求めてください。

制約

• 2 ≤ N ≤ 10の5乗
• 0 ≤ Ai ≤ 9
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

1N
2A1 … AN

出力

答えを10行に出力せよ。ただし、i行目にはK = i − 1としたときの答えを出力せよ。

本問題は、AtCoder株式会社で作成された、D - FG operation問題を参照しております。

Contest中に考えたこと

• 操作した前の結果を利用する、動的計画法を用いるとうまくいくと思ったが、どのように実装すればいいのかわからなかった。ここで終了しました。

解答

1def main():
2    MOD = 998244353
3
4    # 標準入力を受け付ける。
5    N = int(input())
6    A = list(map(int, input().split()))
7
8    # 一番左になる数字(0~9)のとりうる数を保存する。
9    dp = [[0] * 10 for _ in range(N)]
10    # A[0](一番左)の場合の数を+1する。
11    dp[0][A[0]] = 1
12
13    # A[1]と一番左の値を比較するところから検証したいので、range(1, N)となる。
14    for i in range(1, N):
15        # F, Gの操作を行った場合に、一番左になる数字(0~9)のとりうる数を保存しておく。
16        # j : 一番左になりうる値を全通り試す。
17        for j in range(10):
18            # 一番左のjと、二番目に左のA[i]に操作Fをしたとき、新たに一番左になる数字
19            f = (j + A[i]) % 10
20            # 一番左のjと、二番目に左のA[i]に操作Gをしたとき、新たに一番左になる数字
21            g = (j * A[i]) % 10
22
23            # 前の状態を受け継ぐ。
24            dp[i][f] += dp[i - 1][j]
25            dp[i][g] += dp[i - 1][j]
26
27            dp[i][f] %= MOD
28            dp[i][g] %= MOD
29
30    # 一番最後の行に0~9のとりうる数が入っているので、dp[N - 1][i]を出力する。
31    for i in range(10):
32        print(dp[N - 1][i])
33
34if __name__ == '__main__':
35    main()

2021年9月26日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• Atcoder 220に関するコードまとめ
• Wikipedia「位取り記数法」について
• 動的計画法とは?