A問題 Bitwise Exclusive Or
1 2 |
a,b=map(int,input().split()) print(a^b) |
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
1 2 3 4 5 6 7 |
import numpy as np n = int(input()) list = list(map(int, input().split())) list2 = sorted(list) array = np.array(list) print(list.index(list2[-2])+1) |
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となります。
解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
h,w,n = map(int, input().split()) A = [] B = [] for i in range(n): a,b = map(int, input().split()) A.append(a) B.append(b) #重複排除+昇順ソート A_ = sorted(set(A)) B_ = sorted(set(B)) #辞書を準備 dict_A = {} dict_B = {} #重複排除し、昇順に並べたA_,B_の各要素が何番目に小さいかを記録 #キーをA_,B_の各要素、値を何番目に小さいかで設定 for i in range(len(A_)): dict_A[A_[i]] = i+1 #今回の出力結果は1からスタートするため+1 for i in range(len(B_)): dict_B[B_[i]] = i+1 #今回の出力結果は1からスタートするため+1 for j in range(n): print(dict_A[A[j]], dict_B[B[j]]) |
類題
座標圧縮の類題はこちらです。
カテゴリの座標圧縮からも一覧で確認できます。
コメント