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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 213」

コンテスト情報

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

配点

ルール

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

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

A -> Bitwise Exclusive Or

問題文

0以上255以下の整数A, Bが与えられます。A xor C = Bとなる0以上の整数Cを求めてください。

なお、そのようなCはただ1つ存在し、0以上255以下であることが証明されます。

xorとは : 整数a, bのビットごとの排他的論理和 a xor bは、以下のように定義されます。a xor bを二進表記した際の2のk乗(k ≥ 0)の位の数は、a, bを二進表記した際の2のk乗の位の数のうち一方のみが1であれば1、そうでなければ0である。例えば、3 xor 5 = 6となります(二進表記すると: 011 xor 101 = 110)。

制約

• 0 ≤ A, B ≤ 255
• 入力に含まれる値は全て整数である

入力

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

1A B

出力

答えを出力せよ。

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

Contest中に考えたこと

• 整数(10進数)A, Bの値を二進表記に変更する。
• A, Bの値を二進表記に変換する際に、ビットの桁数を合わせるように調整する。
• 二進表記したA, Bの各ビット単位で以下の確認を行う。
• 各ビットの値がA = 1, B = 1の場合、Cを0とする。
• 各ビットの値がA = 1, B = 0の場合、Cを1とする。
• 各ビットの値がA = 0, B = 1の場合、Cを1とする。
• 各ビットの値がA = 0, B = 0の場合、Cを0とする。

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# 整数(10進数)を二進表記へ変更する。
5# 参考 : https://note.nkmk.me/python-bin-oct-hex-int-format/
6A = list(format(A, 'b'))
7B = list(format(B, 'b'))
8
9lenA = len(A)
10lenB = len(B)
11
12# A, Bの値を二進表記に変換する際に、ビットの桁数を合わせるように調整する。
13# insert関数参考 : https://note.mokuzine.net/python-list-append-extend-insert/#insert%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E8%A6%81%E7%B4%A0%E3%82%92%E6%8C%BF%E5%85%A5%E3%81%99%E3%82%8B
14if lenA > lenB:
15    N = lenA
16    for j in range(0, lenA - lenB):
17        B.insert(0, '0')
18else:
19    N = lenB
20    for j in range(0, lenB - lenA):
21        A.insert(0, '0')
22
23C = []
24for i in range(0, N):
25    # 二進表記したA, Bの各ビット単位で以下の確認を行う。
26    # 各ビットの値がA = 1, B = 1の場合、Cを0とする。
27    # 各ビットの値がA = 1, B = 0の場合、Cを1とする。
28    # 各ビットの値がA = 0, B = 1の場合、Cを1とする。
29    # 各ビットの値がA = 0, B = 0の場合、Cを0とする。
30    if A[i] == B[i]:
31        C.append('0')
32    else:
33        C.append('1')
34
35print(int("".join(C), 2))

B -> Booby Prize

問題文

1, …, Nの番号のついたN人の選手がゲームを行いました。選手iのスコアはAiであり、スコアが小さい方が上位になります。

ブービー賞に該当する選手、すなわち、下位から2番目の選手の番号を求めてください。

制約

• 2 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Ai ≤ 10の9乗
• Aiは相異なる
• 入力に含まれる値は全て整数である

入力

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

1N
2A1 … AN

出力

答えを出力せよ。

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

Contest中に考えたこと

• 問題文にAiは相異なると書かれているので、必ず1人のブービーが選ばれることを理解しました。
• 初期の選手の順番を記憶に残しつつ、スコアの順序を並び替える。
• スコアが下位から2番目の人を洗い出し、選手の番号を表示する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3A = list(map(int, input().split()))
4
5# 選手の番号情報を格納する。
6indices = [*range(len(A))]
7
8# 初期の選手の順番を記憶に残しつつ、スコアの順序を並び替える(降順)。
9# 降順とは? : https://www.weblio.jp/content/%E9%99%8D%E9%A0%86
10# key optionについて : https://note.nkmk.me/python-key-sort-sorted-max-min/
11sorted_indices = sorted(indices, key=lambda i: -A[i])
12# sorted関数によって、スコアを降順に並べ替えたので、前から2番目の選手の番号を取得する。
13# 最後に+1しているのは、配列の要素の都合上。
14print(sorted_indices[1] + 1)

C -> Reorder Cards

問題文

H行W列の格子状にHW枚のカードが並べられています。i = 1, …, Nについて、上からAi行目、左からBi列目にあるカードには数iが書かれており、それ以外のHW − N枚のカードには何も書かれていません。

これらのカードに対し、以下の2種類の操作を可能な限り繰り返します。

• 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
• 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

• 1 ≤ H, W ≤ 10の9乗
• 1 ≤ N ≤ min(10の5乗, HW)
• 1 ≤ Ai ≤ H
• 1 ≤ Bi ≤ W
• (Ai ,Bi)は相異なる
• 入力に含まれる値は全て整数である

入力

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

1H W N
2A1 B1
3​⋮
4AN BN

出力

N行出力せよ。操作終了後に数iが書かれたカードが上からCi行目、左からDi列目に存在するとき、i行目にはCi ,Diをこの順に空白区切りで出力せよ。

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

要点

• (Ai, Bi)は相異なると書かれているので、(Ai, Bi)座標に複数カードは存在しない。
• A, B座標をそれぞれソートする。
• Ai, Bi座標の転移先を考える際に、過去に同じ座標にカードへ数が書かれているものがあるかどうか調べる。

解答

1# 標準入力を受け付ける。
2H, W, N = input().split()
3# 型変換を行う。
4N = int(N)
5# 参考 : https://qiita.com/jamjamjam/items/e066b8c7bc85487c0785#%E5%88%97%E3%81%AB%E5%A4%89%E6%95%B0%E3%81%8C%E4%B8%A6%E3%81%B6%E3%81%A8%E3%81%8D
6AB = [map(int, input().split()) for _ in range(N)]
7A, B = [list(i) for i in zip(*AB)]
8
9# Nの値分のindexをリスト化する。
10indices = [*range(N)]
11# ソートする前のA, Bのindexを記憶しておく。
12# key optionについて : https://note.nkmk.me/python-key-sort-sorted-max-min/
13sorted_indicesA = sorted(indices, key=lambda i: A[i])
14sorted_indicesB = sorted(indices, key=lambda i: B[i])
15
16# ソート済みのAi, Bi座標が、ひとつ以上前のAi, Biの座標と等しいか、確認するために利用する。
17tmpA = -1
18tmpB = -1
19
20# Ai, Biの転移する座標情報
21Aposition = 0
22Bposition = 0
23
24# A, Bの転移する座標情報
25Ainfo = []
26Binfo = []
27
28# A, Bの座標情報をソートする。
29A.sort()
30B.sort()
31
32for i in range(0, N):
33    # 過去に座標Aiが存在する場合、転移する座標Aiを更新しない。
34    if not tmpA == A[i]:
35        Aposition = Aposition + 1
36        tmpA = A[i]
37
38    # 過去に座標Biが存在する場合、転移する座標Biを更新しない。
39    if not tmpB == B[i]:
40        Bposition = Bposition + 1
41        tmpB = B[i]
42
43    # ソートする前のA[i], B[i]のindexを、index keyへ追加する。
44    # 転移するA[i], B[i]の座標をpostion keyへ追加する。
45    Ainfo.append({
46        'index': sorted_indicesA[i],
47        'position': Aposition,
48    })
49    Binfo.append({
50        'index': sorted_indicesB[i],
51        'position': Bposition,
52    })
53
54# ソートする前のA, Bのindex順に並べ替える。
55# key optionについて : https://note.nkmk.me/python-key-sort-sorted-max-min/
56Ainfo = sorted(Ainfo, key=lambda x:x['index'])
57Binfo = sorted(Binfo, key=lambda x:x['index'])
58
59# 出力
60for i in range(0, N):
61    print(str(Ainfo[i]['position']) + ' ' + str(Binfo[i]['position']))

D -> Takahashi Tour

問題文

AtCoder国には1からNの番号がついたN個の都市と、1からN − 1の番号がついたN − 1個の道路があります。道路iを通ると都市Aiと都市Biの間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。

高橋くんは都市1を出発し、次のルールで旅をします。

1. いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
2. そのような都市が存在しないとき
3. いまいる都市が都市1なら旅を終了する
4. そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する

高橋くんが旅の過程で訪れる都市を順に答えてください。

制約

• 2 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Ai, Bi ≤ N
• 全ての都市は道路を使って互いに行き来できる

入力

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

1N
2A1 B1
3​⋮
4AN−1 BN−1

出力

高橋くんが訪れる都市を、旅の開始時及び終了時の都市1も含めて順に空白区切りで出力せよ。

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

要点

• 各都市が次の都市へ移動可能な番号を記録する。
• 都市を訪れた時に、次の都市となる対象を探す。
• 次の都市を探す際に、ひとつ前の都市を選んでしまい、無限ループしないようにプログラムを書く。

解答

1import sys
2
3# 再起の上限をつけるために利用する。
4# 参考 : https://note.nkmk.me/python-sys-recursionlimit/
5sys.setrecursionlimit(10**6)
6
7# 標準入力を受け付ける。
8N = int(input())
9
10# 都市の番号情報を格納する。
11edge = [[] for _ in range(N + 1)]
12
13# 標準入力を受け付ける。
14for _ in range(N - 1):
15    a, b = map(int, input().split())
16    # 都市の番号情報と次の都市の番号情報を紐付ける。
17    edge[a].append(b)
18    edge[b].append(a)
19
20# 答えを格納する。
21ans = []
22
23def dfs(now, last=-1):
24    # 再起を利用して、番号が最も小さい都市を出力する。
25    ans.append(now)
26    # 次の都市の番号情報をソートする。
27    edge[now].sort()
28    for to in edge[now]:
29        # 前の都市の番号を次の都市の番号として、選ばれないようにする。
30        if to == last:
31            continue
32        dfs(to, now)
33        # 再起から戻ってきた時の都市の番号を出力する。
34        ans.append(now)
35
36dfs(1)
37
38print(*ans)

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 排他的論理和とは?
• ビットとは?
• 二進表記とは?
• 10進数とは?
• ブービー賞とは?
• catupperさん動画
• Atcoder 213に関するコードまとめ