作成日 : 2021-11-03
更新日 : 2021-11-05
10 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 209」

コンテスト情報

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

配点

ルール

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

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

A -> Counting

問題文

A以上かつB以下の整数はいくつありますか？

制約

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

入力

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

1A B

出力

A以上かつB以下の整数の個数を出力せよ。

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

Contest中に考えたこと

• A > Bの時、A以上かつB以下の整数は存在しないので、0とする。
• A <= Bの時、B - A + 1の結果を出力する。

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# A > Bの時、A以上かつB以下の整数は存在しないので、0とする。
5# A <= Bの時、B - A + 1の結果を出力する。
6if A > B:
7    print(0)
8else:
9    print(B - A + 1)

B -> Can you buy them all?

問題文

高橋商店ではN個の商品が売られています。i(1 ≤ i ≤ N)番目の商品の定価はAi円です。今日はセールが行われており、偶数番目の商品は定価の1円引きの値段で買うことができます。奇数番目の商品は定価で売られています。あなたの所持金はX円です。これらN個の商品を全て買うことができますか？

制約

• 1 ≤ N ≤ 100
• 1 ≤ X ≤ 10000
• 1 ≤ Ai ≤ 100
• 入力は全て整数

入力

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

1N X
2A1 A2 … AN

出力

N個の商品を全て買うことができるならYes、できないならNoと出力せよ。

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

Contest中に考えたこと

• なるべくN個の商品を安く買いたい。
• 偶数番目の商品に関しては、定価 - 1で購入する。
• セール中のN個の商品の合計金額 > 所持金の場合、Noを出力する。そうでない場合、Yesを出力する。

解答

1# 標準入力を受け付ける。
2N, X = map(int, input().split())
3
4A = list(map(int, input().split()))
5
6# セール中のN個の商品の合計金額を格納する。
7a_sum_money = 0
8for i in range(len(A)):
9    # 偶数番目の商品に関しては、定価 - 1で購入する。
10    if (i + 1) % 2 == 0:
11        a_sum_money += (A[i] - 1)
12    # 奇数番目の商品に関しては、定価で購入する。
13    else:
14        a_sum_money += A[i]
15
16    # 途中でセール中のN個の商品の合計金額 > 所持金になった場合、`No`を出力する。
17    if a_sum_money > X:
18        print('No')
19        exit()
20
21print('Yes')

C -> Not Equal

問題文

長さNの整数列Cが与えられます。以下の条件を全て満たす長さNの整数列Aの個数を求めてください。

• 1 ≤ Ai ≤ Ci(1 ≤ i ≤ N)
• Ai ≠ Aj(1 ≤ i < j ≤ N)

ただし、答えは非常に大きくなる可能性があるので、(10の9乗 + 7)で割った余りを出力してください。

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Ci ≤ 10の9乗
• 入力は全て整数

入力

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

1N
2C1 C2 … CN

出力

条件を全て満たす整数列Aの個数を (10の9乗 + 7)で割った余りを出力せよ。

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4C = list(map(int, input().split()))
5
6# 1 ≤ Ai ≤ Ciを満たすAiを取得するだけで、Aiを並べて生成される整数列Aに順序は必要ない。 ⏩ Cの整数列の順番をソートしても問題ない。
7C.sort()
8
9ans = 1
10for i in range(len(C)):
11    # ソートしたCの整数列の値が大きくなるにつれて、その分Aの整数列が生成できることを利用する。
12    ans = (ans * (C[i] - i)) % (10 ** 9 + 7)
13
14print(ans)

D -> Collision

問題文

高橋王国はN個の街とN − 1本の道路からなり、街には1からNの番号がついています。また、i(1 ≤ i ≤ N − 1)本目の道路は街aiと街biを双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。

Q個のクエリが与えられます。i(1 ≤ i ≤ Q)番目のクエリでは整数ci, diが与えられるので、以下の問題を解いてください。

• 現在高橋君は街ciに、青木君は街diにいる。二人が同時に街を出発し、それぞれ街di, ciを目指して同じ速さで移動するとき、二人が街で出会うか道路上(両端の街を除く)で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。

制約

• 2 ≤ N ≤ 10の5乗
• 1 ≤ Q ≤ 10の5乗
• 1 ≤ ai < bi ≤ N(1 ≤ i ≤ N − 1)
• 1 ≤ ci < di ≤ N(1 ≤ i ≤ Q)
• 入力は全て整数
• どの街からどの街へもいくつかの道路を通ることで移動できる

入力

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

1N Q
2a1 b1
3​a2 b2
4​⋮
5aN−1 bN−1
6c1 d1
7c2 d2
8​⋮
9cQ dQ

出力

Q行出力せよ。i(1 ≤ i ≤ Q)行目には、i番目のクエリにおいて二人が街で出会うならTown、道路上で出会うならRoadと出力せよ。

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

解答

1import sys
2
3################################
4# <方針>
5# 1の街からスタートして、2の街へ到着する, 1の街からスタートして、3の街へ到着する, 1の街からスタートして、4の街へ到着する ..., 1の街からスタートして、Nの街へ到着する場合について考える。
6# 上記の場合に対して、最短で何個の道路で移動できるのか記録する。
7# Qiのクエリを与えたときに、cの街から1の街, 1の街からdの街へ、最短で何個の道路で移動できるのか演算する。
8# 上記で求めた道路の個数が偶数なら、`Town`そうでないならば`Road`を出力する。
9# <なぜcの街~dの街間の最短経路を演算することなく、cの街から1の街, 1の街からdの街へ、最短で何個の道路で移動できるのかの演算を行うのか？>
10# 以下の記事を参照ください、すごく参考になります。🙇‍♂️
11# https://yunix-kyopro.hatenablog.com/entry/2021/07/11/020240?_ga=2.121161536.9506465.1625937519-1301098457.1625937519
12################################
13
14# 再起の上限をつけるために利用する。
15# 参考 : https://note.nkmk.me/python-sys-recursionlimit/
16sys.setrecursionlimit(10**6)
17
18def dfs(now):
19    # 一度訪れた街は再度訪れない。
20    if visited[now]:
21        return
22
23    # 訪れた街のフラグを変更する。
24    visited[now] = True
25
26    for to in edges[now]:
27        # 1の街から、次の街へ移動するためにかかる距離を演算する。
28        dep[to] = dep[now] + 1
29        dfs(to)
30
31# 標準入力を受け付ける。
32N, Q = map(int, input().split())
33
34# edges[0]は利用しない。
35edges = [[] for _ in range(N + 1)]
36for i in range(0, N - 1):
37    a, b = map(int, input().split())
38    edges[a].append(b)
39    edges[b].append(a)
40
41# 1の街からスタートして、2の街へ到着する, 1の街からスタートして、3の街へ到着する, 1の街からスタートして、4の街へ到着する ..., 1の街からスタートして、Nの街へ到着する場合について考える。
42# 上記の場合に対して、最短で何個の道路で移動できるのか記録する。
43# dep[0]は利用しない。
44dep = [0] * (N + 1)
45
46# 一度訪れた街へ移動しないためのフラグを用意する。
47# visited[0]は利用しない。
48visited = [False] * (N + 1)
49
50# 1の街から移動を行う。
51dfs(1)
52
53for _ in range(Q):
54    c, d = map(int, input().split())
55    # Qiのクエリを与えたときに、cの街から1の街, 1の街からdの街へ、最短で何個の道路で移動できるのか演算する。
56    # 上記で求めた道路の個数が偶数なら、`Town`そうでないならば`Road`を出力する。
57    if (dep[c] + dep[d]) % 2 == 0:
58        print('Town')
59    else:
60        print('Road')

参考文献

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