作成日 : 2021-08-27
更新日 : 2021-11-01
13 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 216」

コンテスト情報

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

配点

ルール

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

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

A -> Signed Difficulty

問題文

実数X.Yが与えられます。ただしYはちょうど1桁です。

• 0 ≤ Y ≤ 2ならば、X-
• 3 ≤ Y ≤ 6ならば、X
• 7 ≤ Y ≤ 9ならば、X+

と出力してください。

制約

• 1 ≤ X ≤ 15
• 0 ≤ Y ≤ 9
• XとYは整数

入力

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

1X.Y

出力

答えを出力せよ。

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

Contest中に考えたこと

• 与えられる数値を文字列として捉える。
• .区切りでX.Yの値の分離を行う。
• Yの値のif分岐を行う。
• Xの値とYの条件に当てはまる文字(-, '', +)を連結する。

解答

1# 標準入力を受け付ける。
2# 与えられる数値を文字列として捉える。
3S = str(input())
4
5# .区切りでX.Yの値の分離を行う。
6# front = X
7# back = Y
8front, back = S.split('.')
9
10# 型変換を行う。
11back = int(back)
12
13# Yの値のif分岐を行う。
14if back >= 0 and back <= 2:
15    repStr = '-'
16elif back >= 3 and back <= 6:
17    repStr = ''
18else:
19    repStr = '+'
20
21# Xの値とYの条件に当てはまる文字(-, '', +)を連結する。
22print(front + repStr)

B -> Same Name

問題文

N人の人がいます。i(1 ≤ i ≤ N)人目の人の姓はSi、名はTiです。

同姓同名であるような人の組が存在するか、すなわち1 ≤ i < j ≤ NかつSi = SjかつTi = Tjを満たすような整数対(i, j)が存在するか判定してください。

制約

• 2 ≤ N ≤ 1000
• Nは整数
• Si, Tiは英小文字のみからなる長さ1以上10以下の文字列

入力

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

1N
2S1 T1
3​S2 T2
4​⋮
5SN TN

出力

同姓同名であるような人の組が存在するならYesを、存在しないならNoを出力せよ。

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

Contest中に考えたこと

• スペース区切りで姓名が入力されるが、分離して考えず姓 名をひと組として考える。
• 姓 名の重複削除を行う。
• Nと姓 名の数が同数の場合、同姓同名は存在しない。
• Nと姓 名の数が同数でない場合、同姓同名は存在する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4A = []
5for _ in range(N):
6    # スペース区切りで姓名が入力されるが、分離して考えず姓 名をひと組として考える。
7    A.append(str(input()))
8
9# 姓 名の重複削除を行う。
10# set : https://note.nkmk.me/python-set/
11A = set(A)
12
13# Nと姓 名の数が同数でない場合、同姓同名は存在する。
14if N != len(A):
15    print('Yes')
16# Nと姓 名の数が同数の場合、同姓同名は存在しない。
17else:
18    print('No')

C -> Many Balls

問題文

空の箱があります。

髙橋君は以下の2種類の魔法を好きな順番で好きな回数使えます。

• 魔法A：箱の中にボールを1つ増やす
• 魔法B：箱の中のボールの数を2倍にする

合計120回以内の魔法で、箱の中のボールの数をちょうどN個にする方法を1つ教えてください。

なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

• 1 ≤ N ≤ 10の18乗
• 入力は全て整数

入力

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

1N

出力

A, Bのみからなる文字列Sを出力せよ。Sのi文字目がAならば、髙橋君がi回目に使う魔法が魔法Aであることを表し、Bならば魔法Bであることを表す。

Sの長さは120以下でなければならない。

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

Contest中に考えたこと

• Nを素因数分解して素数を洗い出し、魔法A, Bでどのように表せるか考えた。 ⏩ 最短になるイメージが持てなかった。
• Bの魔法(2の1乗, 2乗...)と続けていくと、最短でNに近づくのではと考えた。 ⏩ 47の値で(ABBBBBA(x15))よりも(ABBBAAABABA)があると思い、間違っていると思った。
• 全通りを試しながら、探索先を優先すれば最短でNに近づくのではと考えた。 ⏩ 最短になるイメージが持てなかった。ここで終了しました。

学んだこと

• 倍数を掛け合わせてある値に近づけていく問題は、ある値から約数で割っていき、0になるまで続けると良い。
• 120回以内の魔法箇所を強調している理由 : Nの最大値は10の18乗(10 ** 18)。これは2進数で表すと60桁(1 << 60)以内に収まることを意味します。2進数の1桁あたりに、魔法(A or B)を2回以内実行しなければならないので、120回以内と強調されている。
• できる限り魔法Bを使って、試行回数を少なくしたい。 ⏩ 2で割り切れる場合にBの魔法を利用する。そうでない場合はAの魔法を挟む。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4ans = []
5# Nが0になるまで継続する。
6while N > 0:
7    # 現在のNの値が奇数の場合、Aの魔法を挟む。
8    if not N % 2 == 0:
9        ans.append('A')
10        N = N - 1
11    # Aの魔法を最後にN=0になることを考慮する。
12    if N == 0:
13        break
14    # 偶数のNに対してBの魔法を利用する。
15    ans.append('B')
16    # // : 小数点以下を切り捨てるため。
17    # 参考 : https://www.tohoho-web.com/python/operators.html
18    N = N // 2
19
20# 後ろから魔法を利用しているので、反転処理を行う。
21# reverse : https://note.nkmk.me/python-reverse-reversed/
22ans.reverse()
23# join : https://note.nkmk.me/python-split-strip-list-join/
24print(''.join(ans))

D -> Pair of Balls

問題文

2N個のボールがあります。各ボールには1以上N以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど2個ずつ存在します。

これらのボールが、底が地面と平行になるように置かれたM本の筒に入れられています。はじめ、i(1 ≤ i ≤ M)本目の筒にはki個のボールが入っており、上からj(1 ≤ j ≤ ki)番目のボールの色はai, jです。

あなたの目標は、以下の操作を繰り返すことでM本の筒全てを空にすることです。

• 異なる2本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた2つのボールは同じ色で塗られている必要がある。

目標が達成可能かを判定してください。

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 2 ≤ M ≤ 2 × 10の5乗
• 1 ≤ ki(1 ≤ i ≤ M)
• 1 ≤ ai, j ≤ N(1 ≤ i ≤ M, 1 ≤ j ≤ ki)
• k1 + k2 + ... + kn = 2N
• 全てのx(1 ≤ x ≤ N)について、1 ≤ i ≤ Mかつ1 ≤ j ≤ kiかつai, j = xなる整数の組(i, j)はちょうど2つ存在する
• 入力は全て整数

入力

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

1N M
2k1
3​a1,1 a1,2 … a1,k1
4​k2
5a2,1 a2,2 … a2,k2
6
7​⋮
8
9kM
10​aM,1 aM,2 … aM,kM

出力

目標が達成可能ならYesを、達成不可能ならNoを出力せよ。

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

要点

• 筒の一番上にあるボールに関して検討する。
• 筒の一番上にあるボールの色と筒のindex番号を紐づけておく。
• 筒の一番上に同じ色のボールが2つある場合に、ボールの色情報を記録する。
• ボールの色情報がなくなるまで、上の処理を繰り返す。

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3
4# onTopList[x] : 各筒の一番上にあるボールの色(番号)に対応する、筒のindex番号を格納する。
5onTopList = [[] for _ in range(N + 1)]
6
7# 筒の中に配置されるボールの色一覧
8A = []
9# 取り除くことができるボール一覧を格納する。
10stack = []
11
12for i in range(M):
13    k = int(input())
14
15    # [::-1] : 逆順にしているのは、pop関数を引数指定することなく、利用するため。
16    # del関数を利用して、筒の一番上のボールを取り除いているとTLEになってしまう。
17    # pop関数, del関数 : https://note.nkmk.me/python-list-clear-pop-remove-del/
18    A.append(list(map(int, input().split()))[::-1])
19
20    # 筒の一番上のボールの色を取得する。
21    color = A[i][-1]
22    # 筒の一番上のボールの色に対応する、筒のindex番号を格納する。
23    onTopList[color].append(i)
24
25    # 筒の一番上に同じ色のボールが2つ存在する場合、取り除くことができるのでstackへ格納する。
26    if len(onTopList[color]) == 2:
27        stack.append(color)
28
29# 取り除いたボールの数を格納する。
30doneCnt = 0
31# 取り除くことが可能なボールが存在する限りループを回す。
32while len(stack) != 0:
33    # 取り除くことが可能なボールの色を取得する。
34    # 複数stackが溜まっている場合でも順序に問題はない。
35    color = stack.pop()
36
37    # ボールを取り除いた数をカウントする。
38    doneCnt += 1
39
40    # ボールの色(番号)情報に紐づく、筒のindex番号を取得する。
41    x, y = onTopList[color]
42
43    # 筒の一番上に配置されるボールを取り除く。
44    # ここでdel関数を利用すると、TLEになる。
45    A[x].pop()
46
47    # 筒の中にボールが残っている場合、筒の一番上にあるボールの色(番号)に対応する、筒のindex番号を格納する。
48    if len(A[x]) != 0:
49        newColor = A[x][-1]
50        onTopList[newColor].append(x)
51        if len(onTopList[newColor]) == 2:
52            stack.append(newColor)
53
54    # 筒の一番上に配置されるボールを取り除く。
55    # ここでdel関数を利用すると、TLEになる。
56    A[y].pop()
57
58    # 筒の中にボールが残っている場合、筒の一番上にあるボールの色(番号)に対応する、筒のindex番号を格納する。
59    if len(A[y]) != 0:
60        newColor = A[y][-1]
61        onTopList[newColor].append(y)
62        if len(onTopList[newColor]) == 2:
63            stack.append(newColor)
64
65# 取り除いたボールの数が、Nに等しければYes、そうでなければNoを返す。
66if doneCnt == N:
67    print("Yes")
68else:
69    print("No")

2021年8月29日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• 実数とは?
• AtCoder株式会社について
• 素因数分解とは?
• 約数とは?
• catupperさん動画
• Atcoder 216に関するコードまとめ