【Python】AtCoder Beginner Contest213 A,B,C問題 解答・解説

この記事は約2分で読めます。

A問題 Bitwise Exclusive Or

XORの演算をする問題でした。

XOR演算については問題文で説明されています。

10進数である3は2進数では011

10進数である6は2進数では101

XOR演算は一方だけが1の場合に1、それ以外は0になる演算と捉えています。(かなり大雑把ですが)

011

101

110

それぞれの桁を縦に見ると110となります。

2進数である110は10進数では6となります。

pythonではXOR演算を行うには ^ を用いればよく、これで解答できました。

B問題 Booby Prize

C問題 Reorder Cards

方針

座標圧縮を用います。

座標圧縮とは、大小関係はそのままに不要なデータを取り除くことでデータの数を減らす操作です。

具体的な手順としては以下の通りです。

  • 重複を排除する
  • 昇順(小さい方から順番)にソートする
  • 小さい方から新たに0(もしくは1)から番号を加える

今回の問題に当てはめてみると、座標圧縮を行うとそれぞれの数字の最終的な座標はどうなるかを考えることになります。

入力例1では、3行2列目の1と、2行5列目の2があります。

・・・・・

・・・・2

・1・・・

・・・・・

1行目,4行目、1列目,3列目,4列目は数字がない(「・」のみ)なので、これらの行と列を削除します。

すると、2行1列目に1、1行2列目に2となりました。座標が圧縮されています。

・2

1・

また、[3行,2列]→[2行,1列]、[2行,5列]→[1行,2列]とそれぞれ見比べてみると、

座標圧縮によって大小関係は変わっていません。

行と列はそれぞれ別個で操作してもOKとなります。

解答

 

類題

座標圧縮の類題はこちらです。

カテゴリの座標圧縮からも一覧で確認できます。

AtCoder Beginner Contest 036 A,C問題 解答・解説

コメント