AtCoder Beginner Contest 213をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 213を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Bitwise Exclusive Or
2B - Booby Prize
3C - Reorder Cards
4D - Takahashi Tour
5E以降
6参考にしたサイト等

A - Bitwise Exclusive Or

答えは $0$ から $255$ までの整数であることが分かっているので, それを全探索すればよいです. Pythonにおいて, $XOR$ は^で求められます.

	# 入力
	A, B = [int(x) for x in input().split()]

	# Cを0から255まで試す
	for C in range(256):
	if A^C == B:
	break

	# 出力
	print(C)

view raw atcoder-abc-213-a.py hosted with ❤ by GitHub

あるいは, $A XOR C = B$ の両辺に $A$ を $XOR$ することで,

\begin{aligned} (1) & A XOR A XOR C & = A XOR B, \\ (2) & 0 XOR C & = A XOR B, \\ (3) & C & = A XOR B, \end{aligned}

となります(任意の非負整数 $A$ に対して $A XOR A$ , また $0 XOR A = A$ となることを利用). ゆえに, $A XOR B$ を求めてもよいです.

	# 入力
	A, B = [int(x) for x in input().split()]

	# 出力
	print(A^B)

view raw atcoder-abc-213-a-2.py hosted with ❤ by GitHub

B - Booby Prize

$A_{i}$ をソートして後ろから2番目の数字の元のインデックスが答えです. インデックスを保存しておくために, $[A_{i}, i]$ のリストを作成した上で保存し, ソートします.

	# 入力
	N = int(input())
	A = []
	temp = 1
	for x in input().split():
	A.append([int(x), temp])
	temp += 1

	# Aにはインデックス情報も明示的に入れている(各項2番目)
	# 1番目に合わせてソート
	A_sorted = sorted(A)

	# 出力
	print(A_sorted[-2][1])

view raw atcoder-abc-213-b.py hosted with ❤ by GitHub

C - Reorder Cards

行に関する操作と列に関する操作は互いに独立なので, 行と列に関しては別に考えることができます.

数の書かれたカードを含まない行を消去するという操作を繰り返すことによって,

もともと最も上にあった数の書かれたカード→操作後の1行目に移動
もともと上から2番目にあった数の書かれたカード→操作後の2行目に移動
……

のようにカードが移動されます. ゆえに, リスト $A_{i}$ の各要素を, それらの大小関係(イコールも含む)を維持したまま値を小さくすることが求められます.

以上の話は, 列に関しても同様に考えることができます.

これはいわゆる座標圧縮(coordinate compression)と呼ばれる操作になります. 以下ではソートを利用し, 「元の値」と「その順位」の関連付けの辞書(dict型)を作成することで記述しています.

辞書型はX_dict = {key: value}のように作成します. 特定のkeyに対するvalueを得たい場合には, X_dict[key]のようにします.

	# 入力
	H, W, N = [int(x) for x in input().split()]
	A = []
	B = []
	for i in range(N):
	A_temp, B_temp = [int(x) for x in input().split()]
	A.append(A_temp)
	B.append(B_temp)

	# Aのセット(setで重複を消す)の要素をRankに変える
	A_sorted = sorted(list(set(A)))
	A_dict = {A_sorted[i]:i for i in range(len(A_sorted))}

	# Bのセット(setで重複を消す)の要素をRankに変える
	B_sorted = sorted(list(set(B)))
	B_dict = {B_sorted[i]:i for i in range(len(B_sorted))}

	# 出力 Indexに注意
	for i in range(N):
	print(A_dict[A[i]] + 1, B_dict[B[i]] + 1)

view raw atcoder-abc-213-c.py hosted with ❤ by GitHub

上のコードでは, 要素のランク(順番)を得るためにインデックス番号を取得することが重要となります. 上のコードではfor文などで取得していますが, Pythonにはenumerate()関数があり, リストやタプルなどの要素と同時にインデックス番号を取得することができます. 「インデックス番号, 要素」の順に得られることに注意してください.

	# 入力
	H, W, N = [int(x) for x in input().split()]
	A = []
	B = []
	for i in range(N):
	A_temp, B_temp = [int(x) for x in input().split()]
	A.append(A_temp)
	B.append(B_temp)

	# Aのセット(setで重複を消す)の要素をRankに変える
	A_dict = {i:j for j, i in enumerate(sorted(list(set(A))))}

	# Bのセット(setで重複を消す)の要素をRankに変える
	B_dict = {i:j for j, i in enumerate(sorted(list(set(B))))}

	# 出力 Indexに注意
	for i in range(N):
	print(A_dict[A[i]] + 1, B_dict[B[i]] + 1)

view raw atcoder-abc-213-c-2.py hosted with ❤ by GitHub

D - Takahashi Tour

この問題では, 都市を頂点, 道路を辺としたグラフを考えることができます. 例えば, 「入力例 1」の場合であれば, 下図のようになります.

今回の高橋くんのような移動の仕方は, 深さ優先探索(depth-first search, DFS)と呼ばれるものに対応します. 行き止まりの(最も末端の)ノードに行きつくまで, 経路を戻らずに隣接ノードを進んでいく探索方式のことを指します. 下図は, 深さ優先探索におけるグラフの探索順を示しています.

Wolfram Esser, CC BY-SA 3.0, via Wikimedia Commons.

この高橋くんの旅は, 以下の動作を繰り返すことで実現できます. 「now_city」は, 訪れた都市を順に格納していくリストです. 「visited」は, その都市を訪れたことがあるかどうかを表すフラグを格納したリストです.

now_cityに, 都市Aを格納する.
visitedに, 都市Aを訪れたことを記録する.
都市Aから訪れることができる都市を調べる(都市A-a, 都市A-b, ……)
都市A-a, 都市A-b, ……の全てにおいて, 上記(1,2,3,4)を繰り返す.
再度, 都市Aを訪れる.

このような動作は, 再帰関数を用いることで実現できます.

一部のテストケースにおいて, 「maximum recursion depth exceeded while calling a Python object」というエラーが出てくることがあります. これは再帰回数の上限に引っかかっていることによるものです. 以下のように, 再帰回数の上限を引き上げることで解決できます.

import sys
sys.setrecursionlimit(10**6)

	import sys
	sys.setrecursionlimit(10**6)

	# 入力
	N = int(input())

	# 各都市から行ける都市のリストを作成
	# 0番目は放棄
	can_go_city = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
	A_temp, B_temp = [int(x) for x in input().split()]
	can_go_city[A_temp].append(B_temp)
	can_go_city[B_temp].append(A_temp)

	# can_go_cityのソート
	for can_go_city_ele in can_go_city:
	can_go_city_ele.sort()

	# 訪れた都市のリストを作成
	now_city = []
	visited = [False]*(N+1)

	# 今は都市1にいる
	visited[1] = True

	# 都市candidate_cityから新たに訪れることができる都市を探し、
	# その都市番号をnow_cityに加える関数
	def survey(candidate_city):
	now_city.append(candidate_city)
	visited[candidate_city] = True
	for candidate_next_city in can_go_city[candidate_city]:
	if not(visited[candidate_next_city]):
	survey(candidate_next_city) # 再帰関数
	now_city.append(candidate_city) # 元の都市に戻る

	# 都市1からsurvey()を実行
	survey(1)

	# 出力
	print(" ".join([str(ele) for ele in now_city]))

view raw atcoder-abc-213-d.py hosted with ❤ by GitHub

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

「解説 - AtCoder Beginner Contest 213」
Editorial - AtCoder Beginner Contest 213
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonで辞書を作成するdict()と波括弧, 辞書内包表記」
Pythonで辞書を作成するdict()と波括弧, 辞書内包表記 | note.nkmk.me
Pythonで辞書（dict型オブジェクト）を作成するには様々な方法がある. キーkeyと値valueを一つずつ設定するだけでなく, リストから辞書を作成することも可能. ここでは以下の内容について説明する. 波括弧{}で辞書を作成キーと値を個別に指定複数の辞書を結合キーと値を個別に指定複数の辞書を結合 dict型のコンストラク...
nkmk様による「Pythonで辞書のキー・値の存在を確認, 取得（検索）」
Pythonで辞書のキー・値の存在を確認, 取得（検索） | note.nkmk.me
Pythonで, 辞書（dict型オブジェクト）に特定のキーkey, 値valueが含まれているかを判定する方法, および, その値を取得する方法を説明する. in演算子と辞書オブジェクトのvalues(), items()メソッドを使う. キーkeyの存在を確認, 取得（検索）: in演算子値valueの存在を確認, 取得（検索）: in演算子, values() キーkeyと...
nkmk様による「Python, enumerateの使い方: リストの要素とインデックスを取得」
Python, enumerateの使い方: リストの要素とインデックスを取得 | note.nkmk.me
Pythonのenumerate()関数を使うと, forループの中でリストやタプルなどのイテラブルオブジェクトの要素と同時にインデックス番号（カウント, 順番）を取得できる. 2. 組み込み関数 enumerate() — Python 3.6.5 ドキュメントこの記事ではenumerate()関数の基本について説明する. forループでインデックスを取得できるenume...
algorithm.joho.info様による「【Python】『maximum recursion depth exceeded while calling a Python object』エラーの対策」
【Python】「maximum recursion depth exceeded while calling a Python object」エラーの対策
Pythonの「maximum recursion depth exceeded while calling a Python object」エラーの対策についてまとめました. .

AtCoder Beginner Contest 213をPythonで解く

A - Bitwise Exclusive Or

B - Booby Prize

C - Reorder Cards

D - Takahashi Tour

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter