ABC217のA-E問題の解説。
目次
A - Lexicographic Order
B - AtCoder Quiz
C - Inverse of Permutation
D - Cutting Woods
E - Sorting Queries
A - Lexicographic Order
解説
sがtより辞書順で小さいときにYesを出力する問題。
Pythonには、英字自体を比較することで、辞書順の比較をできるので、そのまま書いてあげることでAC。
コード
def main():
s, t = input().split()
if s < t:
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
B - AtCoder Quiz
解説
リストの中で入力値以外の値を出力する問題。
いろいろな解き方があるが、今回はremoveを用いる。
input()したものをリストから取り除いて、残ったものが答えとなる。
コード
def main():
temp = ['ABC', 'ARC', 'AGC', 'AHC']
for _ in range(3):
s = input()
temp.remove(s)
print(temp[0])
if __name__ == '__main__':
main()
C - Inverse of Permutation
解説
逆置換を使用する問題。
pのi番目の値をqのインデックスにして、そこにiを入れると逆置換ができる。
コード
def main():
n = int(input())
plist = list(map(int, input().split()))
plist = [0] + plist
qlist = [0] * (n+1)
for i in range(1, n+1):
qlist[plist[i]] = i
print(*qlist[1:])
if __name__ == '__main__':
main()
D - Cutting Woods
解説
長さ$L$メートルの木材に線$1, 2, ..., L-1$が刻まれてある。
これを$c = 1$のとき、線$x_i$で2つに切り、$c = 2$のとき、線$x_i$を含む木材の長さを出力する問題。
制約が$L \leq 10^9$なので、単純に$L$を分けていく方法ではうまく行かない。
では、どうすればよいかというと、二分探索を用いる。二分探索のライブラリbisectには、insortとbisect_right, bisect_leftというメソッドがあるので、それらを用いる。詳しくは、以下の記事を見ていただきたいが、かんたんに説明するとこうだ。
insort: リストの順序を崩さずに値の代入ができる
bisect_right, _left: リストの値を探し出し、インデックスを返してくれる
まず、初期値としてリストに端の長さである[0, l]を入れておく。
次に、c == 1となれば、木材を2つに切る操作だが、代わりにリストに線x_iの値をinsortしてく。例えば、入力例1のように[0, 5]があり、c, x = 1, 3となっていれば、リストの中身は[0, 3, 5]となる。このように順序を揃えたままリストに追加することで、どこで切ったかわかりやすくなる。
最後に、c == 2となるときだが、これに関しても二分探索を用いる。bisect_leftで線$x_i$がリストのなかでどこに位置するかを知り、その両端の値の差を取ることで、木材の長さを出力できる。例えば、先程の続きでいうと、c, x = 2, 2が与えられると、[0, 3, 5]のなかで、2のインデックスとして1が返ってくるはずである。このリストのインデックスの両端の値は、切り取られた位置になるので、これらの差をとってあげることで答えを出力することができる。
二分探索についてより深く知りたい方は、以下の記事を参考にしていただきたい。
コード1（ACだが非推奨）
def main():
from bisect import bisect_left, insort
from array import array
l, q = map(int, input().split())
wood = array('i', [0, l]) # listでは間に合わないのでarray
for i in range(q):
c, x = map(int, input().split())
if c == 1:
insort(wood, x) # リストの順序を崩さず値を挿入
elif c == 2:
idx = bisect_left(wood, x) # xがリストに位置するインデックスを返す
print(wood[idx]-wood[idx-1]) # 両端の値の差が答え
if __name__ == '__main__':
main()
コード2（平方分割）<- 推奨
やってることは同じだが、使用するデータ構造が異なる
参照コード↓
https://atcoder.jp/contests/abc140/submissions/7482671
import bisect
class SqrtSet:
def __init__(self, block_limit=201):
self.key = []
self.child = [[]]
self.block_limit = block_limit
def search_lower(self, key):
if key is None:
return None
ret = None
i = bisect.bisect_left(self.key, key)
if i != 0:
ret = self.key[i - 1]
block = self.child[i]
i = bisect.bisect_left(block, key)
if i != 0:
ret = block[i - 1]
return ret
def search_higher(self, key):
if key is None:
return None
ret = None
i = bisect.bisect_right(self.key, key)
if i != len(self.key):
ret = self.key[i]
block = self.child[i]
i = bisect.bisect_right(block, key)
if i != len(block):
ret = block[i]
return ret
def insert(self, key):
i = bisect.bisect(self.key, key)
block = self.child[i]
bisect.insort(block, key)
if len(block) == self.block_limit:
sep = self.block_limit // 2
self.key.insert(i, block[sep])
self.child.insert(i + 1, block[sep + 1:])
self.child[i] = block[:sep]
def dump(self):
for b in self.child:
print(len(b), end=" ")
print("")
def main():
l, q = map(int, input().split())
ord_set = SqrtSet()
ord_set.insert(0)
ord_set.insert(l)
for _ in range(q):
c, x = map(int, input().split())
if c == 1:
ord_set.insert(x)
elif c == 2:
l = ord_set.search_lower(x)
r = ord_set.search_higher(x)
print(r-l)
if __name__ == '__main__':
main()
E - Sorting Queries
解説
空の列$A$に対して、3つの操作をする問題。
-
1 x: $A$の最後尾に$x$を追加 -
2: $A$の最初の要素を出力して、$A$から削除。 -
3: $A$を昇順にソート
リストの操作なので、query1とquery2は簡単にできるが、query3が難しい。どうやって実装するかというと、dequeとheapqを用いる。
まず、query1だが、最後尾への値の追加なので、作成したdequeに値を挿入する。
次に1つ飛ばして、query3だが、$A$の中身をソートするという操作だ。ここでheapqを用いる。今、dequeにquery1を行った状態で値が入っているので、これをheappushしながら、すべての値をソートする。
最後に、query2だが、$A$の最初の値を取り出して、削除するという操作だ。heapに値が存在したら、ソートされている最小値を取り出すことで答えとなるので、heappopする。
もし、heapに値がなければ、dequeから最初の値を取り出してあげれば良いので、deque().popleft()を行えばよい。
また、heapqについてもっと勉強したい方は、以下の記事もご覧頂きたい。
コード
def main():
from collections import deque
import heapq
q = int(input())
que = deque()
heap = []
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
que.append(query[1]) # queに値を追加
elif query[0] == 2:
if len(heap) > 0: # heapに値が存在したら
print(heapq.heappop(heap)) # heapの最小値を取り出す
else: # heapに値がなかったら
print(que.popleft()) # queから値を取り出す
else:
while que: # queの中身をすべてソートながらheapに挿入
heapq.heappush(heap, que.pop())
if __name__ == '__main__':
main()
編集後記
競技プログラミングあるある.
木材が出てくる問題、二分探索しがち.