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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 207」

コンテスト情報

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

配点

ルール

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

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

A -> Repression

問題文

机の上に、正整数が書かれた3枚のカードがあります。 3枚のカードにはそれぞれ整数A, B, Cが書き込まれています。いま、この中からちょうど2枚のカードを選んで手に持ちました。

手に持ったカードに書き込まれた整数の和として考えられる最大値を求めてください。

制約

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

入力

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

1A B C

出力

答えを整数として出力せよ。

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

Contest中に考えたこと

• 3枚のカードの中から2枚のカードを選ぶ場合を、全て洗い出す。
• max関数を利用して、2枚のカードを選ぶ場合の最大値を求める。

解答

1# 標準入力を受け付ける。
2A, B, C = map(int, input().split())
3
4# 3枚のカードの中から2枚のカードを選ぶ場合を、全て洗い出す。
5pattern1 = A + B
6pattern2 = A + C
7pattern3 = B + C
8
9# max関数を利用して、2枚のカードを選ぶ場合の最大値を求める。
10print(max(pattern1, pattern2, pattern3))

B -> Hydrate

問題文

水色のボールがA個容器に入っています。高橋くんはこの容器に対し、以下の操作を0回以上好きなだけ繰り返します。

• 水色のボールB個と赤色のボールC個を容器に追加する。

高橋くんの目標は、容器に入っている水色のボールの個数が赤色のボールの個数のD倍以下になるようにすることです。

目標が達成可能かを判定し、可能なら必要な操作回数の最小値を求めてください。

制約

• 1 ≤ A, B, C, D ≤ 10の5乗
• 入力は全て整数である。

入力

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

1A B C D

出力

高橋くんの目標が達成可能なら、操作回数の最小値を出力せよ。そうでなければ、-1を出力せよ。

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

解答

1# 標準入力を受け付ける。
2A, B, C, D = map(int, input().split())
3
4# 操作の回数を格納する。
5ans = 0
6
7# 以前の計算結果を代入する。
8# 初期値が-100000000000000000000なのは、previous_valへ代入される値が、徐々にプラスの方向へ変化するため。
9previous_val = -100000000000000000000
10
11while True:
12    # (A + (B * ans)) / (C * ans) <= D ⏩ 0 <= D * (C * ans) - ((A + (B * ans))) ⏩ 0 <= (D * C * ans) - A - (B * ans)
13    val = (D * C * ans) - A - (B * ans)
14    if 0 <= val:
15        print(ans)
16        exit()
17    ans += 1
18
19    # 以前の計算結果よりも0に近づいていないと、永遠にD倍以下になることはないので、以下の条件式が成り立つ。
20    if previous_val >= val:
21        print(-1)
22        exit()
23
24    previous_val = val

C -> Many Segments

問題文

1からNまでの番号が付いたN個の区間が与えられます。区間iは、

• ti = 1なら[li, ri]
• ti = 2なら[li, ri)
• ti = 3なら(li, ri]
• ti = 4なら(li, ri)

です。

1 ≤ i < j ≤ Nを満たす整数の組(i, j)のうち、区間iと区間jが共通部分を持つようなものは幾つありますか？

区間 [X, Y], [X, Y), (X, Y], (X, Y)とは？ : 閉区間[X, Y]は、X以上Y以下の全ての実数からなる区間。半開区間[X, Y)は、X以上Y未満の全ての実数からなる区間。半開区間(X, Y]は、Xより大きくY以下の全ての実数からなる区間。開区間(X, Y)は、Xより大きくY未満の全ての実数からなる区間を表します。一言で言うと、角括弧[]を使っている側は端点を含み、丸括弧()を使っている側は端点を含みません。

制約

• 2 ≤ N ≤ 2000
• 1 ≤ ti ≤ 4
• 1 ≤ li < ri ≤ 10の9乗
• 入力は全て整数

入力

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

1N
2t1 l1 r1
3​t2 l2 r2
4⋮
5tN lN rN

出力

区間iと区間jが共通部分を持つような整数の組(i, j)の個数を出力せよ。

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4sample_list = []
5for _ in range(N):
6    t, l, r = map(int, input().split())
7    sample_list.append((t, l, r))
8
9cnt = 0
10# <計算量>
11# A2 = 1, An+1 = An + Nの漸化式である。
12# A2000 = A1999 + 1999 = 1997001 + 1999 = 1999000回ループなので問題ない。
13for i in range(N):
14    for j in range(i + 1, N):
15        i_val = sample_list[i]
16        i_left, i_right = i_val[1:]
17
18        j_val = sample_list[j]
19        j_left, j_right = j_val[1:]
20
21        # 区間の条件に入らない場合に、continueを行う。
22        if (j_right < i_left or i_right < j_left):
23            continue
24
25        # 区間の条件に入らない場合に、continueを行う。
26        if (i_right < j_left or j_right < i_left):
27            continue
28
29        # 区間の条件に入らない場合に、continueを行う。
30        if i_val[0] == 2 and i_right == j_left:
31            continue
32
33        # 区間の条件に入らない場合に、continueを行う。
34        if j_val[0] == 2 and j_right == i_left:
35            continue
36
37        # 区間の条件に入らない場合に、continueを行う。
38        if i_val[0] == 3 and j_right == i_left:
39            continue
40
41        # 区間の条件に入らない場合に、continueを行う。
42        if j_val[0] == 3 and i_right == j_left:
43            continue
44
45        # 区間の条件に入らない場合に、continueを行う。
46        if i_val[0] == 4 and (j_right == i_left or i_right == j_left):
47            continue
48
49        # 区間の条件に入らない場合に、continueを行う。
50        if j_val[0] == 4 and (i_right == j_left or j_right == i_left):
51            continue
52
53        cnt += 1
54
55print(cnt)

D -> Congruence Points

問題文

要素数が共にNであるような二次元平面上の点の集合S = {(a1, b1), (a2, b2), …, (aN, bN)}とT = {(c1, d1), (c2, d2), …, (cN, dN)}が与えられます。

Sに対して以下の操作を0回以上任意の順に好きなだけ繰り返すことで、SとTを一致させられるかを判定してください。

• 実数p(0 < p < 360)を定め、Sに含まれる全ての点を、原点を中心に時計回りにp度回転させる。
• 実数q, rを定める。Sに含まれる全ての点を、x軸方向にq, y軸方向にr移動させる。q, rの値域に制約はなく、特に正 / 負 / 零のいずれになってもよい。

制約

• 1 ≤ N ≤ 100
• −10 ≤ ai, bi, ci, di ≤ 10
• i ≠ jなら(ai, bi) ≠ (aj, bj)
• i ≠ jなら(ci, di) ≠ (cj, dj)
• 入力は全て整数

入力

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

1N
2a1 b1
3a2 b2
4⋮
5aN bN
6c1 d1
7c2 d2 
8⋮
9cN dN

出力

問題文中の操作によってSとTを一致させられるならYesを、一致させられないならNoを出力せよ。

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

解答

1import math
2
3# 標準入力を受け付ける。
4N = int(input())
5
6# N == 1の時、平行移動するだけでTの点と一致させられるので、必ず`Yes`となる。
7if N == 1:
8    print('Yes')
9    exit()
10
11S = []
12for _ in range(N):
13    a, b = map(int, input().split())
14    S.append((a, b))
15
16T = []
17for _ in range(N):
18    c, d = map(int, input().split())
19    T.append((c, d))
20
21# 重心を演算する関数
22def get_center_point(arr):
23    x = 0
24    y = 0
25    for i in range(N):
26        x += arr[i][0]
27        y += arr[i][1]
28
29    return (x / N, y / N)
30
31# S集合の重心を求める。
32(sx1, sy1) = get_center_point(S)
33# T集合の重心を求める。
34(tx1, ty1) = get_center_point(T)
35
36# 各座標を重心からの相対座標に変換(平行移動)する。
37for i in range(N):
38    S[i] = (S[i][0] - sx1, S[i][1] - sy1)
39    T[i] = (T[i][0] - tx1, T[i][1] - ty1)
40
41# 回転角の計算に使うS[z]が重心と一致してしまう場合(S[z][0] == 0, S[z][1] == 0)の場合の回避処理
42# math.atan2(S[z][1], S[z][0])が0になると計算が合わない。
43z = 0
44for i in range(N):
45    if S[i][0] == 0 and S[i][1] == 0:
46        continue
47    z = i
48    break
49
50# 1*10^-6
51DICT_MIN = 1e-6
52
53# 回転角を計算し、あるSの点を回転させる。総当たりであるTの点に一致するか確認する。
54for i in range(N):
55    # 回転角を求める。
56    # 参考 : https://note.nkmk.me/python-math-sin-cos-tan/
57    # 参考 : https://atarimae.biz/archives/18041
58    angle = math.atan2(T[i][1], T[i][0]) - math.atan2(S[z][1], S[z][0])
59
60    count = 0
61    for j in range(N):
62        # 先ほど求めた回転角を元に、あるSの座標を回転させる。
63        # 参考 : http://www.geisya.or.jp/~mwm48961/kou2/linear_image3.html
64        x2 = S[j][0] * math.cos(angle) - S[j][1] * math.sin(angle)
65        y2 = S[j][0] * math.sin(angle) + S[j][1] * math.cos(angle)
66
67        # あるSの座標とあるTの座標が一致しているのか、確認する。
68        is_match = False
69        for k in range(N):
70            # 点の一致具合を調べる。
71            dx = abs(T[k][0] - x2)
72            dy = abs(T[k][1] - y2)
73            if dx <= DICT_MIN and dy <= DICT_MIN:
74                # あるSの回転後の点が、あるTの点に一致
75                is_match = True
76                break
77
78        if is_match == False:
79            break
80        else:
81            count += 1
82
83    if count == N:
84        print("Yes")
85        exit()
86
87print("No")

参考文献

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