作成日 : 2021-11-20
更新日 : 2021-11-22
9 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 204」

コンテスト情報

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

配点

ルール

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

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

A -> Rock-paper-scissors

問題文

サーバル、フェネック、アライグマの3人がじゃんけんをして、あいこになりました。フェネックが出した手を表す文字xとアライグマが出した手を表す文字yが与えられます。それぞれ、0はグー、1はチョキを、2はパーを表します。

サーバルが出した手を表す文字を出力してください。なお、答えは一意に定まります。

制約

• x, yは0, 1, 2のいずれか

入力

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

1x y

出力

答えを出力せよ。出力についても、0はグー、1はチョキを、2はパーを表すものとする。

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

Contest中に考えたこと

• あいこになる方法を考える。 ⏩3人が同じ手を出す or 3人が違う手を出す。

解答

1# 標準入力を受け付ける。
2x, y = map(int, input().split())
3
4# 3人が同じ手の場合
5if x == y:
6    print(x)
7# 3人が異なる手の場合
8elif (x == 0 and y == 1) or (x == 1 and y == 0):
9    print(2)
10# 3人が異なる手の場合
11elif (x == 0 and y == 2) or (x == 2 and y == 0):
12    print(1)
13# 3人が異なる手の場合
14else:
15    print(0)

B -> Nuts

問題文

N本の木があり、i番目の木にはAi個の木の実が実っています。シマリスは、次のルールで全ての木から木の実を収穫します。

• 実っている木の実が10個以下の木からは木の実を収穫しない
• 実っている木の実が10個より多い木からは、10個を残して残りの全てを収穫する

シマリスが収穫する木の実の個数の合計を求めてください。

制約

• 1 ≤ N ≤ 1000
• 0 ≤ Ai ≤ 1000
• 入力に含まれる値は全て整数である

入力

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

1N
2A1 … AN

出力

答えを出力せよ。

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

Contest中に考えたこと

• 各木の実に関して考える。各木の実の数をxとおくと、x <= 10の時、木の実を収穫しない。x > 10の時x - 10個木の実を収穫する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4A = list(map(int, input().split()))
5
6# 木の実の合計数
7sum_nuts = 0
8for i in range(N):
9    # x > 10の時x - 10個木の実を収穫する。
10    if A[i] > 10:
11        sum_nuts += A[i] - 10
12
13print(sum_nuts)

C -> Tour

問題文

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

ピューマは、どこかの都市からスタートし、0本以上の道路を使い移動して、どこかの都市をゴールとするような旅行の計画を立てようとしています。

スタート地点とゴール地点の都市の組として考えられるものは何通りありますか？

制約

• 2 ≤ N ≤ 2000
• 0 ≤ M ≤ min(2000, N(N−1))
• 1 ≤ Ai, Bi ≤ N
• Ai ≠ Bi
• (Ai, Bi)は相異なる
• 入力に含まれる値は全て整数である

入力

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

1N M
2A1 B1
3⋮
4AM BM

出力

答えを出力せよ。

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

解答

1import sys
2
3# 再帰の上限数を設定する。
4# 参考 : https://note.nkmk.me/python-sys-recursionlimit/
5sys.setrecursionlimit(10000)
6
7# 標準入力を受け付ける。
8N, M = map(int, input().split())
9
10def dfs(temp, i):
11    # 一度ゴールとして認めたものを再度更新しない。
12    if temp[i]:
13        return
14    temp[i] = True
15
16    # ゴールとして認めることのできる都市を探す。
17    for to in edges[i]:
18        dfs(temp, to)
19
20# 都市間の移動情報を格納する。
21# edges[0]は利用しない。
22edges = []
23for _ in range(N + 1):
24    edges.append([])
25
26for _ in range(M):
27    a, b = map(int, input().split())
28    edges[a].append(b)
29
30# スタート地点とゴール地点の都市の組数の合計値を格納する。
31cnt = 0
32# スタート地点になる都市として、1~Nが考えられるのでrange(1, N + 1)とする。
33for i in range(1, N + 1):
34    # ゴール地点として認めたものか判断する変数。
35    # temp[0]は利用しない。
36    temp = [False] * (N + 1)
37    dfs(temp, i)
38
39    # ゴール地点と認めた数だけ足し合わせる。
40    cnt += sum(temp)
41
42print(cnt)

D -> Cooking

問題文

高橋君は料理1からNのN品の料理を作ろうとしています。料理iはオーブンを連続したTi分間使うことで作れます。1つのオーブンを2つ以上の料理のために同時に使うことはできません。

2つのオーブンを使えるとき、N品の料理を全て作るまでに最短で何分かかりますか？　なお、オーブンを使う時間以外は無視できるものとします。

制約

• 1 ≤ N ≤ 100
• 1 ≤ Ti ≤ 10の3乗
• 入力に含まれる値は全て整数である

入力

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

1N
2T1 … TN

出力

答えを出力せよ。

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

解答

1# <方針>
2# 1つのオーブンのみを稼働された場合に、かかる時間を求める。
3# 料理の組み合わせを考えて、かかる時間を、動的計画法(dp)を利用してそれぞれ列挙する。
4# max(1つのオーブンでかかる時間 - 料理の組み合わせによりかかる時間, 料理の組み合わせによりかかる時間)の、一番小さい時間を求める。
5# 参考 : https://qiita.com/u2dayo/items/1ed77ef0ac2cf3de7c15#d%E5%95%8F%E9%A1%8Ccooking
6
7# 標準入力を受け付ける。
8N = int(input())
9
10T = list(map(int, input().split()))
11
12# オーブンを1つで稼働させた場合にかかる時間
13S = sum(T)
14
15# dp[0][i] : 0個の料理を最短i分で調理することが可能かどうか?
16# dp[1][i] : 1個(T0)の料理を最短i分で調理することが可能かどうか?
17# dp[2][i] : 2個(T0, T1)の料理を最短i分で調理することが可能かどうか?
18# dp[3][i] : 3個(T0, T1, T2)の料理を最短i分で調理することが可能かどうか?
19dp = []
20for i in range(N + 1):
21    dp.append([False] * (S + 1))
22# 0個の料理に関しては0分で調理できるためdp[0][0]はTrueになる。
23dp[0][0] = True
24
25for i in range(N):
26    t = T[i]
27    for j in range(S + 1):
28        # 一つ前の動的計画法(dp)でok出したものは、okとする。
29        if dp[i][j]:
30            dp[i + 1][j] = True
31
32        # 一つ前の動的計画法(dp)でokを出した時間 + 今回検証するT[i]の時間に関してokを出す。
33        if j - t >= 0 and dp[i][j - t]:
34            dp[i + 1][j] = True
35
36ans = 100000000000000
37for s in range(S + 1):
38    if dp[N][s]:
39        # max(1つのオーブンでかかる時間 - 料理の組み合わせによりかかる時間, 料理の組み合わせによりかかる時間)の、一番小さい時間を求める。
40        score = max(s, S - s)
41        ans = min(ans, score)
42
43print(ans)

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• Atcoder 204に関するコードまとめ