.lazyload-placeholder { display: none; }

作成日 : 2021-11-05
更新日 : 2021-11-07
13 min readAtCoder

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

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

そもそもAtCoderとは?
「AtCoder Beginner Contest 208」
A -> Rolling Dice
B -> Factorial Yen Coin
C -> Fair Candy Distribution
D -> Shortest Path Queries 2
参考文献

目次を開く⬇︎

執筆者 - おすすめの記事3選

この記事も読まれています

.lazyload-placeholder { display: none; }

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

AtCoder Beginner Contest 209のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

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

AtCoder Beginner Contest 210のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

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

AtCoder Beginner Contest 211のA~D問題に関して、問題文からContest中に考えたこと、解...

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 208」

コンテスト情報

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

配点

問題	点数
A	100
B	200
C	300
D	400
E	500
F	600

ルール

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

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

A -> Rolling Dice

問題文

1, 2, …, 6の出目がある6面サイコロをA回振ったとき、出た目の合計がBになることはありますか？

制約

1 ≤ A ≤ 100
1 ≤ B ≤ 1000
A, Bは整数である。

入力

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

1A B

出力

出た目の合計がBになり得る場合はYesを、そうでない場合はNoを出力せよ。

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

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# A回サイコロを振って得られる、最小値、最大値を求める。
5min_val = A
6max_val = A * 6
7
8# min_val <= B, B <= max_valの場合、`Yes`, そうでなければ`No`を出力する。
9if min_val <= B and B <= max_val:
10    print('Yes')
11else:
12    print('No')

B -> Factorial Yen Coin

問題文

高橋王国では1!円硬貨, 2!円硬貨, …,10!円硬貨が流通しています。ここで、N! = 1 × 2 × ⋯ × Nです。高橋君は全ての種類の硬貨を100枚ずつ持っており、P円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。

問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。

最小で何枚の硬貨を使えば支払うことができますか？

制約

1 ≤ P ≤ 10の7乗
Pは整数である。

入力

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

1P

出力

必要となる硬貨の最小枚数を出力せよ。

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

解答

1# 標準入力を受け付ける。
2P = int(input())
3
4# 問題の制約下で条件を満たす支払い方は必ず存在する = いくつかの硬貨を組み合わせれば必ず支払いはできる。
5
6# ちょうどの金額を支払った場合の、最小の硬貨数を求める。以下を繰り返すことと同じである。
7# 1. 支払い金額をぎりぎり超えない、○!円の硬貨を探す。
8# 2. 支払い金額 - 1で見つけた硬貨(○!円)を実行する。
9# 3. 使った硬貨の数を+1する。
10# 4. 2の結果(支払い金額 - 1で見つけた硬貨(○!円))を支払い金額とする。
11# 5. 支払い金額が0の場合、終了する。
12# 6. 1に戻る。
13
14amari = P
15# 硬貨数
16cnt = 0
17# 5. 支払い金額が0の場合、終了する。
18while amari != 0:
19    coin = 1
20    i = 1
21
22    # 1. 支払い金額をぎりぎり超えない、○!円の硬貨を探す。
23    while amari >= coin:
24        coin = coin * i
25        i += 1
26
27    # 4. 2の結果(支払い金額 - 1で見つけた硬貨(○!円))を支払い金額とする。
28    amari -= (coin / (i - 1))
29    # 3. 使った硬貨の数を+1する。
30    cnt += 1
31
32print(cnt)

C -> Fair Candy Distribution

問題文

高橋王国にはN人の国民がいます。全ての国民には国民番号が割り振られており、i人目の国民の国民番号はaiです。ここで、aiは互いに異なります。

高橋君はK個のお菓子を持っています。高橋君は次のルールに従って、持っているお菓子が無くなるまで国民にお菓子を配ることにしました。

持っているお菓子がN個以上ある場合、全員に1個ずつお菓子を配る。
そうでない場合、その時点で高橋くんが持っているお菓子の個数をK′として、国民番号が小さい方からK′人に1個ずつ配る。より厳密には、aiの値が小さい方からK′人を選び、選んだ人に1個ずつお菓子を配る。

全てのお菓子を配り終えたとき、i人目の国民は何個のお菓子を持っていますか？

制約

1 ≤ N ≤ 2 × 10の5乗
1 ≤ K ≤ 10の18乗
1 ≤ ai ≤ 10の9乗
aiは互いに異なる。
入力は全て整数である。

入力

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

1N K
2a1 a2 … aN

出力

N行出力せよ。i行目にはi人目の国民がもらったお菓子の個数を出力せよ。

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

解答

1import copy
2
3# 標準入力を受け付ける。
4N, K = map(int, input().split())
5
6A = list(map(int, input().split()))
7
8# 全員に配るお菓子の数を求める。
9all_snack_num = K // N
10# 全員に均等にお菓子を配った場合に、残るお菓子の数を求める。
11amari_snack_num = K - (all_snack_num * N)
12
13# 参考 : https://qiita.com/Kaz_K/items/a3d619b9e670e689b6db
14sortedA = copy.copy(A)
15# 国民番号をソートする。
16sortedA.sort()
17
18# 残りのお菓子を配る際に、最後にお菓子を配る国民番号を取得する。
19# amari_snack_numが0の場合もエラーにならない。 ⏩ 1 <= Nのため。
20last_user_for_distribute_snack = sortedA[amari_snack_num - 1]
21
22for a in A:
23    # 残りのお菓子がある && 最後に残りのお菓子を配る国民番号 >= 国民番号の場合、全員に配るお菓子 + 1となる。
24    # そうでない場合、全員に配るお菓子のみとなる。
25    if amari_snack_num > 0 and last_user_for_distribute_snack >= a:
26        print(all_snack_num + 1)
27    else:
28        print(all_snack_num)

D -> Shortest Path Queries 2

問題文

https://atcoder.jp/contests/abc208/tasks/abc208_d

制約

1 ≤ N ≤ 400
0 ≤ M ≤ N(N − 1)
1 ≤ Ai ≤ N(1 ≤ i ≤ M)
1 ≤ Bi ≤ N(1 ≤ i ≤ M)
Ai ≠ Bi(1 ≤ i ≤ M)
1 ≤ Ci ≤ 10の6乗(1 ≤ i ≤ M)
i ≠ jならばAi ≠ AjまたはBi ≠ Bjである。
入力は全て整数である。

入力

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

1N M
2A1 B1 C1
3⋮
4AM BM CM

出力

https://atcoder.jp/contests/abc208/tasks/abc208_d

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

学んだこと

ワーシャルフロイド法を利用すると、解くことができる。

ワーシャルフロイド法の考え方

入力例が以下の場合を考えます。

まず入力例をもとに、都市間の移動時間を表で表します。以下のようになります。

.lazyload-placeholder { display: none; }

各数字は都市番号を、オレンジ色の箇所はスタート地点の都市番号を、青色の箇所はゴール地点の都市番号を、×マークは都市間の移動ができないことを表しています。

例えば2の都市番号から4の都市番号へ移動するためには、1の移動時間がかかりますが、表のオレンジ色の箇所が2, 青色の箇所が4の箇所を確認すると、同じように1だと確認できますね。

次にk = 1、すなわち都市番号1のみ通って良い場合の、各都市間の移動時間を考えます。具体的にどのような場合を考えるかというと、

直接移動する場合(Start ⏩ Goal)
都市1を経由して移動する場合(Start ⏩ 都市1 ⏩ Goal)
どちらか小さい方を採用。

を行います。

たとえば都市番号5(Start)から都市番号2(Goal)に関して、上記の表を確認しながら計算しましょう。

直接移動する場合(都市番号5 ⏩ 都市番号2) : x
都市番号1を経由して移動する場合(都市番号5 ⏩ 都市番号1 + 都市番号1 → 都市番号2)：5 + 3 = 8
都市に到着できないよりも、到着できた方がいいので、都市番号1を経由して移動する場合のほうが、早く着くことになります。

k = 1の場合に各都市番号に関して、同様に計算し、表を埋めると以下のようになります。

【k = 1(都市番号が1以下の都市のみ通った場合の最短時間)】

.lazyload-placeholder { display: none; }

この表はs = Start, t = Goalとしたときのf(s, t, 1)を表しています。例えばf(5, 2, 1) = 8ということが表を見るとわかります。

ゆえに表のx以外の箇所を全て足せば、k = 1の場合の、任意のs, tの組についてfを合計したものを計算することができます。

次にk = 2、すなわち都市番号が2以下の都市のみ通って良い場合に、各都市間の移動時間を考えます。

すでにk = 1(都市番号が1以下の都市のみ通った場合の最短時間)の各都市間時間は表にしました。この表を使い、同じ手順で今度は都市番号2を経由する場合を考えます。

つまり各Start、Goalについて、

直接移動する場合(Start ⏩ Goal)
都市2を経由して移動する場合(Start ⏩ 都市番号2 ⏩ Goal)
どちらか小さい方を採用。

を行います。

Start ⏩ 都市番号1 ⏩ 都市番号2 ⏩ Goal, Start ⏩ 都市番号2 ⏩ 都市番号1 ⏩ Goalの場合を考える必要はないのかと感じる方もいるかも知れません。結論から説明すると、考える必要はありません。なぜならStart ⏩ 都市番号1 ⏩ 都市番号2 ⏩ Goalの場合、Start ⏩ 都市番号2の最短経路の中にStart ⏩ 都市番号1 ⏩ 都市番号2の場合が含まれているから。Start ⏩ 都市番号2 ⏩ 都市番号1 ⏩ Goalの場合、Start ⏩ 都市番号2がxだったら、同じくStart ⏩ 都市番号2 ⏩ 都市番号1 ⏩ Goalもxになる。また都市番号2 ⏩ 都市番号1ぶん移動時間がかかるため、考える必要はない。

【k = 2(都市番号が2以下の都市のみ通った場合の最短時間)】

.lazyload-placeholder { display: none; }

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3
4# 都市間の移動ができない、移動時間を表す
5INF = 1000000000000000000
6
7# 都市間の移動時間情報を格納する。
8time = []
9for i in range(N):
10    time.append([INF] * N)
11    time[i][i] = 0
12
13for _ in range(M):
14    A, B, C = map(int, input().split())
15    # 配列の都合上、-1idxを行う。
16    A -= 1
17    B -= 1
18    time[A][B] = C
19
20ans = 0
21for k in range(N):
22    for i in range(N):
23        for j in range(N):
24            # Start ⏩ Goal or Start ⏩ 都市x ⏩ Goalの最小移動時間を求める。
25            time[i][j] = min(time[i][j], time[i][k] + time[k][j])
26            # 都市間の移動ができない、移動時間の場合、答えに含まない。
27            if time[i][j] == INF:
28                continue
29            ans += time[i][j]
30
31print(ans)