Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
7
Help us understand the problem. What are the problem?

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

ABC217A,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()
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
7
Help us understand the problem. What are the problem?