Home / Python /

AtCoder Beginner Contest 213をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

AtCoder Beginner Contest 213 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Bitwise Exclusive Or

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

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

\begin{align} A \, \mathrm{XOR} \, A \, \mathrm{XOR} \, C &= A \, \mathrm{XOR} \, B , \\ 0 \, \mathrm{XOR} \, C &= A \, \mathrm{XOR} \, B , \\ C &= A \, \mathrm{XOR} \, B , \\ \end{align}

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

B - Booby Prize

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

C - Reorder Cards

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

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

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

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

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

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

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

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

D - Takahashi Tour

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

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

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

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

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

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

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

import sys
sys.setrecursionlimit(10**6)

E以降

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

参考にしたサイト等