【AtCoder】ABC217をPython3で解説（ABCDE）

ABC217のA-E問題の解説。

https://atcoder.jp/contests/abc217

## 目次
[A - Lexicographic Order](#a---lexicographic-order)
[B - AtCoder Quiz](#b--0atcoder-quiz)
[C - Inverse of Permutation](#c---inverse-of-permutation)
[D - Cutting Woods](#d---cutting-woods)
[E - Sorting Queries](#e---sorting-queries)

## A - Lexicographic Order

https://atcoder.jp/contests/abc217/tasks/abc217_a

### 解説

sがtより辞書順で小さいときに`Yes`を出力する問題。

Pythonには、英字自体を比較することで、辞書順の比較をできるので、そのまま書いてあげることで`AC`。

### コード
```python
def main():
    s, t = input().split()

    if s < t:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()
```

## B - AtCoder Quiz

https://atcoder.jp/contests/abc217/tasks/abc217_b

### 解説

リストの中で入力値以外の値を出力する問題。
いろいろな解き方があるが、今回は`remove`を用いる。

`input()`したものをリストから取り除いて、残ったものが答えとなる。

### コード
```python

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

https://atcoder.jp/contests/abc217/tasks/abc217_c

### 解説

逆置換を使用する問題。

pの`i`番目の値をqのインデックスにして、そこに`i`を入れると逆置換ができる。

### コード
```python
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

https://atcoder.jp/contests/abc217/tasks/abc217_d

### 解説

長さ$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`が返ってくるはずである。このリストのインデックスの両端の値は、切り取られた位置になるので、これらの差をとってあげることで答えを出力することができる。

二分探索についてより深く知りたい方は、以下の記事を参考にしていただきたい。

https://qiita.com/uniTM/items/2f2a38f225f04154df9a

### コード1（`AC`だが非推奨）
```python

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

```python
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

https://atcoder.jp/contests/abc217/tasks/abc217_e

### 解説

空の列$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`についてもっと勉強したい方は、以下の記事もご覧頂きたい。

https://qiita.com/uniTM/items/9630ed9d51f62b3e35ab

### コード

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


## 編集後記

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

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