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

【備考録】AtCoder Beginner Contest 211 A~D問題

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 211」

コンテスト情報

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

配点

ルール

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

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

A -> Blood Pressure

問題文

収縮期血圧Aと拡張期血圧Bが与えられます。平均血圧Cを求めてください。ただし、平均血圧は以下のように定義されるとします。

• C = A − B / 3 + B

制約

• 50 ≤ B ≤ A ≤ 300
• 入力に含まれる値は全て整数である

入力

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

1A B

出力

Cを出力せよ。

出力値と想定解答の絶対誤差または相対誤差が10の−5乗以下であれば正解と判定される。 ⏩ 小数第5位まで答えが正しければ正解となる。

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

Contest中に考えたこと

• 計算式通りに出力する。

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3 
4print((A - B) / 3 + B)

B -> Cycle Hit

問題文

4つの文字列S1, S2, S3, S4が与えられます。この中に、H, 2B, 3B, HRがそれぞれ1つずつあるか判定してください。ただし、全てのSiはH, 2B, 3B, HRのいずれかと一致します。

制約

• SiはH, 2B, 3B, HRのいずれかと一致する

入力

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

1S1
2​S2
3S3
4S4

出力

H, 2B, 3B, HRがそれぞれ1つずつあるならばYesと出力せよ。そうでないならばNoと出力せよ。

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

Contest中に考えたこと

• H, 2B, 3B, HRのリストを作成する。
• s1, s2, ...が入力される度に、上記で作成したリスト内に含まれるか確かめる。
• リスト内にsiが含まれれば、リストからsiを削除する。
• リスト内に値が残っている場合、Yes, そうでない場合Noとする。

解答

1# H, 2B, 3B, HRのリストを作成する。
2sList = [
3    'H',
4    '2B',
5    '3B',
6    'HR',
7]
8 
9inputList = []
10 
11# 標準入力を受け付ける。
12inputList.append(input())
13inputList.append(input())
14inputList.append(input())
15inputList.append(input())
16 
17for i in range(0, len(inputList)):
18    # 上記で作成したリスト内に含まれるか確かめる。
19    if inputList[i] in sList:
20        # リスト内にsiが含まれれば、リストからsiを削除する。
21        # remove関数参考 : https://note.nkmk.me/python-list-clear-pop-remove-del/
22        sList.remove(inputList[i])
23 
24# リスト内に値が残っている場合、Yes, そうでない場合Noとする。
25if len(sList) == 0:
26    print('Yes')
27else:
28    print('No')

C -> chokudai

問題文

文字列Sが与えられます。このうち8文字を選び下線を引き、下線を引いた文字が左から順にc, h, o, k, u, d, a, iとなるようにする方法は何通りありますか？ただし答えは非常に大きくなる可能性があるので、(10の9乗 + 7)で割った余りを出力してください。

制約

• 8 ≤ ∣S∣ ≤ 10の5乗
• Sは英小文字からなる

入力

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

1S

出力

答えを(10の9乗 + 7)で割った余りを出力せよ。

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

Contest中に考えたこと

• 入力されるSの文字列を、1文字単位に分解する。
• 2重ループを回して、左からchikudaiの文字列がどれくらい生成されるかカウントする。 ⏩ 一度chikudaiとしてカウントした文字を、再度利用できる場合に、カウント漏れが起こる。。ここでコンテストが終了しました。

学んだこと

• 全ての場合の数を考える際は、動的計画法を考慮に入れる。
• 動的計画法を考える際は、場合の数が少ない通りから検証し、法則を導き出す。今回ならある文字列Sが与えられてabの場合の数、ある文字列Sが与えられてabcの場合の数など。

abの場合

abcの場合

解答

1# 検証用文字列
2# 番兵用に先頭文字列へ空白を挿入する。 ⏩ リストのエラー防止にもつながる。
3# 番兵とは? : https://www.weblio.jp/content/%E7%95%AA%E5%85%B5
4inspectionStr = ' chokudai'
5
6# 標準入力を受け付ける。
7S = input()
8# 番兵用に先頭文字列へ空白を挿入する。 ⏩ リストのエラー防止にもつながる。
9# 番兵とは? : https://www.weblio.jp/content/%E7%95%AA%E5%85%B5
10S = ' ' + S
11
12Slen = len(S)
13inspectionStrLen = len(inspectionStr)
14
15# 動的計画法を利用するための、配列の初期化を行う。
16# 動的計画法とは? : https://www.momoyama-usagi.com/entry/info-algo-dp
17dp = [[0 for _ in range(0, Slen)] for _ in range(0, inspectionStrLen)]
18for j in range(0, Slen):
19    # 番兵行の値を設定する。
20    dp[0][j] = 1
21
22# 参考 : https://www.youtube.com/watch?v=Zu9S_kJ-7tk
23for i in range(0, inspectionStrLen):
24    for j in range(0, Slen):
25        if S[j] == inspectionStr[i]:
26            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]
27        else:
28            dp[i][j] = dp[i][j - 1]
29
30# 10の9乗 + 7で割ることを忘れない。
31# 10の9乗 + 7以上の数値を答えとして扱わない。
32# 10の9乗 + 7は素数である。 ⏩ 10の9乗 + 7は、1と10の9乗 + 7以外で割り切れることのない値。 ⏩ 0 ~ 10の9乗 + 7以内に関して、あまりを計算しても答えに影響しない。
33print(dp[inspectionStrLen - 1][Slen - 1] % (10 ** 9 + 7))

D -> Number of Shortest paths

問題文

AtCoder国には1からNの番号がついたN個の都市と、1からMの番号がついたM個の道路があります。道路iを通ると都市Aiと都市Biの間を双方向に1時間で移動することができます。

都市1から都市Nへ最も早く移動することができる経路は何通りありますか？答えは非常に大きくなる可能性があるので(10の9乗 + 7)で割ったあまりを求めてください。

制約

• 2 ≤ N ≤ 2 × 10の5乗
• 0 ≤ M ≤ 2 × 10の5乗
• 1 ≤ Ai < Bi ≤ N
• (Ai, Bi)は相異なる
• 入力に含まれる値は全て整数である

入力

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

1N M
2A1 B1
3​⋮
4AM BM

出力

答えを出力せよ。都市1から都市Nへ移動することが出来ない場合は0と出力せよ。

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

学んだこと

• 無向グラフを考える場合、BFS(幅優先探索)が利用できるか考慮する。
• BFS(幅優先探索)する際に、一つ前の都市へ最短で行ける、道路数を動的計画法を用いて、参照できるようにする。

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3
4# 都市から都市への移動の情報を格納する。
5G = [[] for _ in range(N)]
6for _ in range(M):
7    # 標準入力を受け付ける。
8    A, B = map(int,input().split())
9    # 配列のindexが0から始めることに合わせて、都市の番号を-1する。
10    A -= 1
11    B -= 1
12    G[A].append(B)
13    G[B].append(A)
14
15# 初期化
16# 次に移動する都市の情報を格納する。
17que = [0]
18# 0番目の都市からある都市へ移動する時間を格納する。
19dist = [None] * N
20# 0番目の都市からある都市へ移動する最短経路の道路数を格納する。
21cnt = [0] * N
22# 0番目の都市の移動時間を0とする。
23dist[0] = 0
24cnt[0] = 1
25
26for v in que:
27    for vv in G[v]:
28        # まだ行ったことのない都市に関する計算
29        if dist[vv] is None:
30            # 初めて訪れた都市に、+1の時間を設定する。
31            dist[vv] = dist[v] + 1
32            # 初めて訪れた都市から、次の都市へ移動するための情報を格納する。
33            que.append(vv)
34            # 初めて訪れた都市へ移動できる道路の本数をメモしておく。一つ前の都市へ最短で行ける、道路数を参照できるようにするため。(動的計画法)
35            cnt[vv] = cnt[v]
36        # 都市と都市の間が1時間の時、常に最短経路であるため、その道路の本数を数える。
37        # 1 -> 0のような方向に向かう経路は演算しない。
38        elif dist[vv] == dist[v] + 1:
39            cnt[vv] += cnt[v]
40            # 10の9乗 + 7で割ることを忘れない。
41            # 10の9乗 + 7以上の数値を答えとして扱わない。
42            # 10の9乗 + 7は素数である。 ⏩ 10の9乗 + 7は、1と10の9乗 + 7以外で割り切れることのない値。 ⏩ 0 ~ 10の9乗 + 7以内に関して、あまりを計算しても答えに影響しない。
43            cnt[vv] %= 10 ** 9 + 7
44
45print(cnt[N - 1])

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 収縮期血圧, 拡張期血圧とは?
• 絶対誤差, 相対誤差とは?
• 動的計画法とは?
• 番兵とは?
• 無向グラフとは?
• BFS(幅優先探索)とは?
• Atcoder 211に関するコードまとめ