【AtCoder解説】PythonでABC217のA,B,C,D,E問題を制する！

ABC217のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

• シンプル：余計なことを考えずに済む
• 実装が楽：ミスやバグが減ってうれしい
• 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share

よかったらLGTMや拡散していただけると喜びます！

目次

ABC217 まとめ
A問題『Lexicographic Order』
B問題『AtCoder Quiz』
C問題『Inverse of Permutation』
D問題『Cutting Woods』
E問題『Sorting Queries』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

• レート別問題正解率
• パフォーマンス目安
• 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC217 まとめ

全提出人数: 8543人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	ABC-----	600	39分	6323(6054)位
400	ABC-----	600	20分	5200(4931)位
600	ABC-----	600	12分	4288(4020)位
800	ABCD----	1000	100分	3364(3097)位
1000	ABCD----	1000	20分	2516(2249)位
1200	ABCDE---	1500	84分	1817(1554)位
1400	ABCDE---	1500	48分	1282(1025)位
1600	ABCDE---	1500	31分	890(640)位
1800	ABCDE---	1500	17分	605(372)位
2000	ABCDEF--	2000	61分	391(199)位
2200	ABCDEFG-	2600	115分	260(99)位
2400	ABCDEFG-	2600	90分	182(47)位

色別の正解率

色	人数	A	B	C	D	E	F	G	H
灰	3701	93.3 %	93.1 %	82.3 %	12.2 %	4.0 %	0.1 %	0.1 %	0.0 %
茶	1488	99.1 %	99.1 %	98.8 %	39.2 %	22.0 %	0.4 %	0.3 %	0.0 %
緑	1166	99.5 %	99.5 %	99.1 %	62.1 %	53.2 %	1.1 %	0.6 %	0.0 %
水	745	99.7 %	99.6 %	99.6 %	81.6 %	87.0 %	10.2 %	7.1 %	0.0 %
青	390	100.0 %	100.0 %	99.7 %	98.2 %	97.2 %	36.9 %	27.7 %	0.5 %
黄	207	95.7 %	95.7 %	95.2 %	95.2 %	98.5 %	66.7 %	62.3 %	11.6 %
橙	39	97.4 %	97.4 %	97.4 %	94.9 %	97.4 %	87.2 %	94.9 %	33.3 %
赤	26	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	73.1 %

※表示レート、灰に初参加者は含めず

A問題『Lexicographic Order』

問題ページ：A - Lexicographic Order
灰コーダー正解率：93.3 %
茶コーダー正解率：99.1 %
緑コーダー正解率：99.5 %

入力

$S, T$: 文字列

実装

Pythonで文字列の辞書順比較をするときは、数字を比較するときと同様に<などの演算子を使えば良いです。

コード

S, T = input().split()
print("Yes" if S < T else "No")

B問題『AtCoder Quiz』

問題ページ：B - AtCoder Quiz
灰コーダー正解率：93.1 %
茶コーダー正解率：99.1 %
緑コーダー正解率：99.5 %

入力

$S_1,S_2,S_3$: コンテスト名

実装

リストL = ["ABC", "ARC", "AGC", "AHC"]を作って、$S_1$, $S_2$, $S_3$をリストからremoveで取り除き、最後に残った一つを出力すればいいです。

コード

L = ["ABC", "ARC", "AGC", "AHC"]

for _ in range(3):
    S = input()
    L.remove(S)
print(L[0])

C問題『Inverse of Permutation』

問題ページ：C - Inverse of Permutation
灰コーダー正解率：82.3 %
茶コーダー正解率：98.8 %
緑コーダー正解率：99.1 %

入力

$N$: 順列の長さ
$p_i$: $Q$ の $p_i$ 番目の要素が $i$

考察

問題文の通りにforループで順番に処理すればいいですが、リストが$0$スタートで、問題文は $1$ スタートなので、$1$ ずらすことに気をつけましょう。

コード

N = int(input())
P = list(map(int, input().split()))
Q = [0] * N

for i in range(N):
    p_i = P[i] - 1
    Q[p_i] = i + 1
print(*Q)

D問題『Cutting Woods』

問題ページ：D - Cutting Woods
灰コーダー正解率：12.2 %
茶コーダー正解率：39.2 %
緑コーダー正解率：62.1 %

入力

$L$: 木材の長さ
$Q$: クエリの数
$c_i$: $i$ 番目のクエリの種類
$x_i$:
$c_i=1$ の場合 線 $x_i$ の地点で木材を $2$ つに切る
$c_i=2$ の場合 線 $x_i$ を含む木材の長さを出力する

考察

はじめから木材が切られている場合を考えてみる

はじめから木材が切られていて、クエリ $2$ だけが来る問題を考えてみましょう。

まず、木材が切られている位置を昇順にソートした配列を用意します。このとき、木材の両端 $0$ と $L$ でも木材が切られていることに勝手にします。線 $x_i$ のすぐ左側の切られている位置 $l_i$ と、すぐ右側の切られている位置 $r_i$ がわかれば、答えは$r_i-l_i$になります。

例えば、$L=12$ で、木材が切られている位置が $0, 3, 5, 9, 12$ だとします。線 $2$の木材の長さは、$3-0=3$ です。線 $7$の木材の長さは、$9-5=4$です。*

基本的には二分探索で解ける

『線 $x_i$ のすぐ左側の切られている位置 $l_i$ と、すぐ右側の切られている位置 $r_i$』 は、二分探索を使えば、$1$ 回あたり $O(logM)$ で求めることができます。（$M$ は木材が切られた回数）

切られる位置がクエリで追加されるので、データ構造が必要

この問題のように、途中で木材の切る位置が増える場合でも、配列が常にソートさえされていれば、同様に二分探索で解くことができます。

配列がソートされている状態を維持するために、クエリ $1$ が来るたびに二分探索を利用して挿入すると $1$ 回につき $O(N)$、リストそのものをソートしても$O(NlogN)$ かかるので、これらの方法は使えません。

常に配列がソートされている状態を維持したいときは、平衡二分探索木というデータ構造を使えばいいです。挿入、削除、参照が $O(logN)$ で行え、要素は常にソートされた状態が維持されます。ただし、平衡二分探索木はPythonの標準ライブラリにはありません。

そのため、以下の方法を使う必要があります。

• Pythonで平衡二分探索木のライブラリを作って使う（かなり大変なので、実力がある人でないとコンテスト中に書けるものではありません）
• C++のstd::set を使う（平衡二分探索木です。Pythonのsetに対応するのはstd::unordered_setで、別物です）
• arrayで二分探索
• 座標圧縮してBinary Index Tree（この記事では書いていない）

平衡二分探索木を使う方法

Python、C++ともに、平衡二分探索木で挿入、二分探索をするだけです。

arrayで二分探索

クエリ $1$ で 要素 $x$ をリストに対して二分探索で挿入する位置を探して、挿入する位置を探す方法は、通常 リストに要素を $1$ つ挿入するときの計算量が $O(Q)$ なので全体では $O(Q^2)$ になりTLEになりますが、arrayモジュールを使って定数倍高速化をするとACできます。

arrayは型が固定の配列です。型をi（$4$ バイト符号付き整数）にすると通ります。q（$8$ バイト符号付き整数）では通りません。

コード

Pythonで平衡二分探索木のライブラリを作って使う

この Treap は自作ですが、大変低速なうえ、正常に動作する保証はないので、参考程度に見てください。

なお、Pythonでは通りませんでした。PyPyで950ms程度です。

コード（Treap部分が長いので折りたたみ）

class OrderedSet:
    """
    平衡二分探索木（Treap）
    """

    from typing import List, Optional, TypeVar

    class TreapNode:
        def __init__(self, key, priority):
            self.key = key
            self.left = None
            self.right = None
            self.priority = priority

        def __repr__(self):
            return str(self.key)

    T = TypeVar('T', int, float, str)
    Node = TreapNode

    def __init__(self):
        from random import randint
        self.rand_gen = randint
        self.root = self._create_node(None)
        self.length = 0
        self._none_node = self._create_node(None)

    def is_empty(self):
        if self.root is None:
            return True
        else:
            return False

    def _create_node(self, x) -> Node:
        priority = self.rand_gen(1, (1 << 32) - 1)
        new_node = self.TreapNode(x, priority)
        return new_node

    def add(self, x) -> None:
        """
        xを追加する
        既に含まれている場合は何もしない
        """
        if self._add(x):
            self.length += 1

    def _add(self, x) -> bool:
        """
        追加に成功した場合True、既に存在した場合Falseを返す(len管理用)
        """
        if self.root.key is None:
            self.root = self._create_node(x)
            return True

        cur = self.root
        par_stack = []
        while cur:
            par_stack.append(cur)
            if x < cur.key:
                cur = cur.left
            elif x > cur.key:
                cur = cur.right
            else:
                return False

        l = len(par_stack)
        child = self._create_node(x)

        for i in range(l):
            par = par_stack[-(i + 1)]
            if child.key < par.key:
                par.left = child
                if child.priority < par.priority:
                    child.right, par.left = par, child.right
                    par = child
            else:
                par.right = child
                if child.priority < par.priority:
                    child.left, par.right = par, child.left
                    par = child
            child = par
        self.root = child
        return True

    def discard(self, x) -> None:
        """
        xを削除
        なければ何もしない
        """
        if self._discard(x):
            self.length -= 1

    def _discard(self, x) -> bool:
        if self.root.key is None:
            return False

        cur = self.root
        node_stack = []
        is_left_stack = []

        while True:
            if cur is None:
                return False
            if x < cur.key:
                node_stack.append(cur)
                is_left_stack.append(True)
                cur = cur.left
            elif x > cur.key:
                node_stack.append(cur)
                is_left_stack.append(False)
                cur = cur.right
            else:
                if cur.left and cur.right:
                    if cur.left.priority < cur.right.priority:
                        node = cur.left
                        node.right, cur.left = cur, node.right
                        node_stack.append(node)
                        is_left_stack.append(False)
                    else:
                        node = cur.right
                        node.left, cur.right = cur, node.left
                        node_stack.append(node)
                        is_left_stack.append(True)
                else:
                    node_stack.append(cur.left or cur.right)  # Noneでないほうが追加される
                    is_left_stack.append(None)
                    break

        l = len(node_stack)
        cur = node_stack[-1]
        is_left = is_left_stack[-1]
        for i in range(1, l):
            par = node_stack[-(i + 1)]
            is_left = is_left_stack[-(i + 1)]
            if is_left:
                par.left = cur
            else:
                par.right = cur
            cur = par

        self.root = cur
        return True

    def find(self, x) -> bool:
        """
        xが含まれるか判定
        計算量: O(logN)
        """
        if self._find(x):
            return True
        else:
            return False

    def _find(self, x) -> Optional[Node]:
        if self.root.key is None:
            return None

        node = self.root
        while node:
            if x < node.key:
                node = node.left
            elif x == node.key:
                return node
            else:
                node = node.right
        return None

    def all_keys(self) -> List[T]:
        """
        全要素の昇順リスト
        Todo: 軽量化
        """

        def add_sub_tree(node):
            keys = []
            if node is not None:
                keys.extend(add_sub_tree(node.left))
                keys.append(node.key)
                keys.extend(add_sub_tree(node.right))
            return keys

        if self.length == 0:
            return []
        else:
            keys = add_sub_tree(self.root)
            return keys

    def min(self) -> T:
        node = self.root
        while node.left:
            node = node.left
        return node.key

    def max(self) -> T:
        node = self.root
        while node.right:
            node = node.right
        return node.key

    def prev(self, x) -> Optional[T]:
        """
        xのより真に小さい要素で最大のものを取得
        存在しなければNoneを返す
        計算量: O(logN)
        """
        if self.root.key is None:
            return None

        node_cur = self.root
        node_return = self._none_node
        while True:
            if node_cur.key < x:
                node_return = node_cur
                if node_cur.right:
                    node_cur = node_cur.right
                else:
                    return node_return.key
            else:
                if node_cur.left:
                    node_cur = node_cur.left
                else:
                    return node_return.key

    def next(self, x) -> Optional[T]:
        """
        xより真に大きい要素で最小のものを取得
        存在しなければNoneを返す
        計算量: O(logN)
        """
        if self.root.key is None:
            return None

        node_cur = self.root
        node_return = self._none_node
        while True:
            if x < node_cur.key:
                node_return = node_cur
                if node_cur.left:
                    node_cur = node_cur.left
                else:
                    return node_return.key
            else:
                if node_cur.right:
                    node_cur = node_cur.right
                else:
                    return node_return.key

    def __str__(self):
        return str(self.all_keys())

    def __repr__(self):
        return self.__str__()

    def __len__(self):
        return self.length

    def __contains__(self, x):
        return self.find(x)


def main():
    L, Q = map(int, input().split())
    ord_set = OrderedSet()
    ord_set.add(0)
    ord_set.add(L)

    for _ in range(Q):
        c, x = map(int, input().split())
        if c == 1:
            ord_set.add(x)
        else:
            l = ord_set.prev(x)
            r = ord_set.next(x)
            print(r - l)


if __name__ == '__main__':
    main()

C++のstd::set を使う

C++で書いたほうが楽だと思います。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll L, Q;
    cin >> L >> Q;
    set<ll> S;
    S.insert(0);
    S.insert(L);
    ll c, x;
    for (int i = 0; i < Q; ++i) {
        cin >> c >> x;
        if (c == 1) {
            S.insert(x);
        } else {
            auto it = S.lower_bound(x);
            ll l = *prev(it);
            ll r = *it;
            cout << (r - l) << endl;
        }
    }
}

arrayで二分探索

def main():
    import sys
    readline = sys.stdin.readline
    """+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-:+:-+:-"""
    from array import array
    import bisect

    L, Q = map(int, readline().split())
    arr = array('i', [0, L])

    for _ in range(Q):
        c, x = map(int, readline().split())
        if c == 1:
            bisect.insort_left(arr, x)
        else:
            ind = bisect.bisect_left(arr, x)
            print(arr[ind] - arr[ind - 1])


if __name__ == '__main__':
    main()

E問題『Sorting Queries』

問題ページ：E - Sorting Queries
灰コーダー正解率：4.0 %
茶コーダー正解率：22.0 %
緑コーダー正解率：53.2 %

入力

$Q$: クエリの数
$query_i$: クエリの内容

$1\ \ x$: $A$ の最後尾に$x$を追加する
$2$: $A$ の最初の要素を出力して削除する
$3$: $A$ を昇順にソートする

考察

クエリ $1$ : $A$ の最後尾に $x$ を追加
クエリ $2$: $A$ の最初の要素を出力して削除
クエリ $3$: $A$ を昇順にソートする

もちろん、クエリ $3$ が来るたびに配列をソートするとTLEになります。

この問題の配列 $A$ は『クエリ $2$ で昇順にソートされた配列』の後ろに『クエリ $1$ で最後尾に追加された、まだソートされていない配列』が来る構造になっています。

『クエリ $2$ で昇順にソートされた配列』は優先度付きキュー（PriorityQueue）で管理します。優先度付きキューは、最小値を取り出し、要素の追加を$O(logN)$ で行えるデータ構造です。

『クエリ $1$ で最後尾に追加された、まだソートされていない配列』は、両端キュー（deque）で管理します。

そして、クエリごとに以下の操作を行えば良いです。

クエリ1

dequeの最後尾に $x$ を追加します。

クエリ2

PriorityQueueが空でなければ、PriorityQueueから最小値を取り出して出力します。

空ならば、dequeの先頭を取り出して出力します。

クエリ3

dequeの中身をすべて取り出して、PriorityQueueに移します。

計算量について

優先度付きキューに要素を追加・削除するときの計算量は $O(logQ)$ です。優先度付きキューに要素を追加する回数は、多くてもクエリ$1$ が来た回数と同じだけですから、全体で $O(QlogQ)$ですから、十分高速です。（削除も同じです）

コード

import heapq
from collections import deque


class PriorityQueue:
    """
    優先度付きキュー
    """

    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __str__(self):
            return str(self.val)

        def __repr__(self):
            return repr(self.val)

    def __init__(self, a=None, desc=False):
        self.__container = []
        if a:
            self.__container = a[:]

        if desc:
            for i, item in enumerate(self.__container):
                self.__container[i] = self.Reverse(item)
            self.pop = self.__pop_desc
            self.push = self.__push_desc
            self.top = self.__top_desc
        else:
            self.pop = self.__pop_asc
            self.push = self.__push_asc
            self.top = self.__top_asc
        heapq.heapify(self.__container)

    @property
    def is_empty(self):
        return not self.__container

    def __pop_asc(self):
        return heapq.heappop(self.__container)

    def __pop_desc(self):
        return heapq.heappop(self.__container).val

    def __push_asc(self, item):
        heapq.heappush(self.__container, item)

    def __push_desc(self, item):
        heapq.heappush(self.__container, self.Reverse(item))

    def __top_asc(self):
        return self.__container[0]

    def __top_desc(self):
        return self.__container[0].val

    def sum(self):
        return sum(self.__container)

    def __len__(self):
        return len(self.__container)

    def __str__(self):
        return str(sorted(self.__container))

    def __repr__(self):
        return self.__str__()


def main():
    Q = int(input())
    que = deque()
    pq = PriorityQueue()

    for _ in range(Q):
        query = input().split()
        q = int(query[0])
        if q == 1:
            # 最後尾にxを追加
            x = int(query[1])
            que.append(x)
        elif q == 2:
            # Aの最初の要素を出力して削除
            if pq:
                print(pq.pop())
            else:
                print(que.popleft())
        else:
            # Aを昇順にソート
            while que:
                pq.push(que.pop())


if __name__ == '__main__':
    main()