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()

編集後記

競技プログラミングあるある.

木材が出てくる問題、二分探索しがち.