ABC213参戦記

1日前に実施されたAHC005は、全然スコアが伸びませんでした。ABCは、前回はA1完だったし、前々回もAB2完と最近の成績はよろしくないです。
今回のABC213こそ、スムーズにC問題まで解き、D問題に落ち着いて取り組みたいです。

この記事は、茶色コーダーの私がABC213を振り返る記事です。使用言語はPython3です。

A – Bitwise Exclusive Or

標準入出力と、xorの計算をする問題。
・・・xorがABCのA問題に出てくるの！？となった問題。

私は、for文で全探索しました。

# AtCoder Beginner Contest 213
# A - Bitwise Exclusive Or

A, B=map(int,input().split())

for i in range (0,256):
    if A^i==B:
        print(i)
        exit()

全探索しなくとも、答えは求まるようです。
AxorA=0より、AxorC=Bから両辺をAをxorして、C=BxorAで答えが求まるようですね。

A, B=map(int,input().split())
print(A^B)

B – Booby Prize

二次元配列のソートが出来るかを問われる問題。

少し前に同様の問題がありましたね。(ABC201-B:Do you know the second highest mountain?)

今回の問題は、自分で選手番号を加えなくてはいけません。
一度、リストを受け取って、スコアと選手番号をセットにしたものをリストで保持して、スコアでソートしてから、後ろから2つ目にある選手番号を出力すればOKです。

リストの後ろから2つ目の2つ目の要素は、list[-2][1] で取得できますね。
私は pop() を2回利用しました。

# AtCoder Beginner Contest 213
# B - Booby Prize

N=int(input())
A=list(map(int,input().split()))

ls=[]

for i in range (N):
    # スコアでソートできるように[スコア,選手番号]の状態でリストに追加。
    ls.append([A[i],i+1])

ls.sort()

ls.pop() # 最下位意をリストから取り出す
ans=ls.pop() # ブービー賞をリストから取り出す
print(ans[1])

他にも、2番目に高いスコアを求めてから、そのスコアに該当するインデックスを探して出力する方法でもAC出来ます。

N=int(input())
A=list(map(int,input().split()))

sortedA=sorted(A)
target_index=sortedA[-2]

print(A.index(target_index)+1)

C – Reorder Cards

座標圧縮の問題。

各行列を確認して、愚直に取り除いていったのでは、実行時間エラーになります。

対象の数字が書かれているカードは縦、横それぞれ、残っている行(または列)番号のうち何番目にいるかを答えられるようにしたいです。

数字が書かれている行/列の番号だけで構成した配列を用意して、そこでの順番を調べられれば良いですね。

以下、この問題を解く方針を書いていきます。

1. 必要な行番号/列番号をメモしておく用のデータを行番号用と列番号用でそれぞれ持つ。
2. 数字が書かれているカードの行番号を列番号をそれぞれ別の配列で持つ。
3. 数字が書かれている行番号と列番号を1.で準備したデータに入れる。
4. 全てのカードの情報を受け取ったら、1で準備したデータを配列にして、ソートする。
5. 2.で持っている配列を前から順に、行番号・列番号が4.で用意した配列の前から何番目かを調べる。

5.の際には、bisect.bisect() を利用すると、素早く見つかります。

# AtCoder Beginner Contest 213
# C - Reorder Cards

import bisect

H,W,N=map(int,input().split())

order_h=[]
order_w=[]

# 数字が書かれている行/列の番号だけを準備するためのデータ。
bisect_order_h=set()
bisect_order_w=set()

for i in range (N):
    A,B=map(int,input().split())
    order_h.append(A)
    order_w.append(B)
    bisect_order_h.add(A)
    bisect_order_w.add(B)

# 数字が書かれている行/列の番号を配列にしてソートする。
bisect_order_h=list(bisect_order_h)
bisect_order_h.sort()
bisect_order_w=list(bisect_order_w)
bisect_order_w.sort()

for i in range (N):
    ans_h=bisect.bisect(bisect_order_h,order_h[i])
    ans_w=bisect.bisect(bisect_order_w,order_w[i])
    print(ans_h,ans_w)