Skip to content

memo.md

Latest commit

 

History

History
1221 lines (994 loc) · 55 KB

memo.md

File metadata and controls

1221 lines (994 loc) · 55 KB
Raw

競技プログラミングのメモ
基本的に蟻本(Amazonのリンク)に書かれているアルゴリズムの実装や関連問題(主にAtCoder)をメモしている。

ここでは主にPythonでメモをする

コンテストサイト

Chrome拡張について

Tampermonkeyを使うと、いろんな便利機能を追加できる

  • ac-predictor
    • 順位表にパフォーマンス・レート変化を追記してくれるやつ
  • AtCoderPerformanceColorizer
    • 成績表ページでパフォーマンスとレートに色をつけてくれるやつ
  • AtCoder Submission Status
    • SubmissionページでテストケースのAC/WAの統計情報を表示してくれるやつ

入出力

基本的に競技プログラミングは標準入力から特定のフォーマットの入力を受け取り、 標準出力 から特定のフォーマットに従って出力をする。

標準入力からの入力の受け取りには、組み込み関数のinput()を使う。

input([prompt]) （略）この関数は入力から 1 行を読み込み、文字列に変換して (末尾の改行を除いて) 返します

# 文字列
s = input()

# 整数１つ
n = int(input())
# 整数複数
a, b = map(int, input().split())
# 整数をリストで
x = list(map(int, input().split()))

# m行の入力
m = int(input())
table = [list(map(int, input().split())) for _ in range(m)]

多くの行から読み込みが必要な場合、input()は遅いらしい。そのような時には以下のように代わりにsys.stdin.readlineを使うようにしておくと早くなる。

import sys
input = sys.stdin.readline

標準出力は当然print()

  • １行に複数の数を空白区切で出力する時、ans=[1, 2, 3, 4, 5]として、 
    print(' '.join([str(ansi) for ansi in ans]))
    としても良いが、 
    print(*ans)
    の方がスマートな気がする。

リダイレクト

毎回テストデータを手入力していると面倒。適宜リダイレクトすると良い。
test.txtというファイルにテストデータを保存しておいて、

$ python hoge.py < test.txt

とすると、test.txtの内容を標準入力として入力しファイルを実行することができる。

基本的なデータ構造

文字列

pythonのstringはimmutableだぞっ。 https://qiita.com/Amtkxa/items/a03dabe050d8c648f098

char <-> ascii

print(ord('a')) # 97
print(chr(98))  # b

string <-> int

print(int('123'))
print(str(123))

配列

sort

$O(N\log N)$でソート済み配列を取得する。

https://docs.python.org/ja/3.7/howto/sorting.html pythonのソートはsorted(a)とa.sort()がある。 共通点は、

  • ともにデフォルトでは昇順ソート。reverse=Trueとパラメーターすると降順になる。
  • keyパラメーターにlambda式などを入れると、比較の仕方を変えられる。

で、違いは

  • sorted(a)は新たにソートされたリストを返すが、a.sort()はaをインプレースにソート済みのものに変更しNoneを返す。
  • a.sort()はリストにのみ定義されている。
a = [5, 2, 3, 1, 4]
print(sorted(a)) # [1, 2, 3, 4, 5]
print(a)         # [5, 2, 3, 1, 4]

a.sort() # return None
print(a) # [1, 2, 3, 4, 5]

b = [5, 2, 3, 1, 4]
print(sorted(a, reverse=True)) # [5, 4, 3, 2, 1]

deque

double-ended queueのことで、stackとqueueを一般化したもの。
発音は「デック」らしい。内部的には双方向連結リストとして実装されているらしい(要出典)。

https://docs.python.org/ja/3/library/collections.html#collections.deque
append(i), appendleft(i), pop(), popleft(), が$O(1)$で出来る。

  • list オブジェクトでも(dequeと)同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

  • listでもlast要素のpop（つまりただの.pop()）であれば$O(1)$。https://wiki.python.org/moin/TimeComplexity 
from collections import deque
dq = deque([5, 6, 7, 8])
dq.pop() # 8
len(dq) # 3
dq # deque([5, 6, 7])

dq.appendleft(4)
dq # deque([4, 5, 6, 7])

# 一応添字のアクセスもできる
dq[1] # 5

問題

stack

LIFO(Last In First Out)なコンテナ。 DFSの実装などに使える。再帰関数でも同様な動作。

stackはない。dequeをよしなに使うとよい。
listのappend(hoge)とpop()を使うことでも実装可能(参考：リストをスタックとして使う)。

queue

FIFO(First In First Out)なコンテナ。待ち行列とも。 BFSの実装などに使える。

queueはない（queue.Queueは並行実行のためのmoduleで、純粋なデータ型ではない）。dequeをよしなに使うのが良さそう（参考：リストをキューとして使う）。

priority_queue

優先度付きキュー。挿入された順番通りにpopするのではなく(FIFOではなく)、優先度の高い要素から先に取り出すようになっているキュー。
二分ヒープを用いて実現している。

https://docs.python.org/ja/3/library/heapq.html
(実装は https://github.com/python/cpython/blob/master/Lib/heapq.py ) pythonのheapは二分min-heapなことに注意。つまり、

  • heap[k] <= heap[2*k+1] かつ heap[k] <= heap[2*k+2]
  • heap[0]が最小値
from heapq import heappush, heappop
h = []
heappush(h, (5, 'write code'))
heappush(h, (7, 'release product'))
heappush(h, (1, 'write spec'))
heappush(h, (3, 'create tests'))
print(h)
# [(1, 'write spec'), (3, 'create tests'), (5, 'write code'), (7, 'release product')]
heappop(h)
# (1, 'write spec')
print(h)
# [(3, 'create tests'), (7, 'release product'), (5, 'write code')]

問題

平行二分探索木

C++のset/mapに相当するもの。 Pythonにそんなものはない。対処法はいくつかある。

  1. Treapなどを自分で実装する

  2. BIT(+ 座標圧縮)で代用する

  3. priority_queueを２本使う（参考：【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】）

    class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

    def insert(self, x):
        heappush(self.s, x)

    def erase(self, x):
        heappush(self.e, x)

    def get_min(self):
        while self.e and self.e[0] == self.s[0]:
            _ = heappop(self.s)
            _ = heappop(self.e)
        return self.s[0] if len(self.s) > 0 else None

ハッシュテーブル

探索

全探索

競プロでは文字通りの全列挙で解ける問題もしばしば出題されるので、DFS・BFS・bit使って全列挙などパッと書けるようになるのが大事。 また完全な意味での全列挙でなくても、「ある変数$x$を固定するとそれ以外の変数については最適なパターンが決まるので、変数$x$について全探索する」的な解法もしばしばある。

問題

DFS - 深さ優先探索

実装方法

  • 再帰関数
  • stack

問題

BFS - 幅優先探索

実装方法

  • queue

問題

二分探索

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜

ソート済み配列を探索するタイプの二分探索

lower_boundやbisect_leftを使う

C++
https://cpprefjp.github.io/reference/algorithm/lower_bound.html
https://cpprefjp.github.io/reference/algorithm/upper_bound.html

python
https://docs.python.org/ja/3/library/bisect.html

  • bisect.bisect_left(a, x)
    • 昇順ソート済みlistaの中で、a[index] >= xという条件を満たす最小のindexを返す
  • bisect.bisect_right(a, x)
    • 昇順ソート済みlistaの中で、a[index] > xという条件を満たす最小のindexを返す
    • bisect.bisectのalias
from bisect import bisect_left, bisect_right
#    0 1 2 3 4 5 6 7 8 9
a = [1,1,1,3,3,3,3,4,4,4]

bisect_left(a, 0), bisect_right(a, 0) #  0,  0
bisect_left(a, 1), bisect_right(a, 1) #  0,  3
bisect_left(a, 2), bisect_right(a, 2) #  3,  3
bisect_left(a, 3), bisect_right(a, 3) #  3,  7
bisect_left(a, 4), bisect_right(a, 4) #  7, 10
bisect_left(a, 5), bisect_right(a, 5) # 10, 10

問題

答えを決め打つタイプの二分探索

https://betrue12.hateblo.jp/entry/2019/05/11/013403

「答えを決め打つ」タイプの二分探索で問題を解くために必要な条件は

  • 「ある値xに対して、ある条件を満たすことができるか」という判定問題が解きやすい
  • 上記の判定問題の答えに単調性があるか（Yes/Noの境界が一つか）

いくつか典型のパターンがある

  • 「〜〜を満たす最大(最小値)値を求めよ」
  • 「〜〜の最大値の最小化（最小値の最大化）」
    • 「〜〜の最大値をX以下にできるか」「任意の〜〜をX以下にできるか」などと言い換えて、二分探索に持ち込む
  • 「平均の最大化」
    • 「数列{x[i]}の平均値がa」は「数列{x[i]-a}の総和が0」
  • 「K番目の要素の値」
    • まず「K番目の要素の値がX以下である」という判定問題を考えると、Xを二分探索可能。
      • この判定問題はほぼ自明に単調生がある。
      • さらに以下のように言い換えが可能なので、解きやすい。
        • 「K番目の要素の値がX以下である」と「X以下の要素がK個以上ある」は同値
        • 「X以下の要素がK個以上ある」という判定問題を解く
  • 「方程式の解を一つだけ求めよ」
    • 条件(True/False)の切り替わる境界（方程式の解）が複数あっても、 それを一つ見つけるだけ で良いなら二分探索が使える。
    • こういう方程式の数値的な解析は「二分法」というっぽい？
def check(x):
    # xが条件を満たすか判定する関数
    pass

lb = -1    # False
ub = hoge  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid
# lbがFalseの最大、ubがTrueの最小

問題

半分全列挙

$O(2^N)$の全探索は間に合わないが、$O(2^{N/2})$の探索は間に合うときの解法。 半分に関しては全探索(全列挙)し、もう一方のグループについてはハッシュテーブル・二分探索・貪欲法などで高速に処理をする。 問題

アルゴリズム

貪欲

AtCoder 版！蟻本 (初級編) : 2-2 猪突猛進！ "貪欲法"

問題

累積和

数列$$a_0, a_1, ..., a_{N-1}$$がある時に、$$\sum_{i=l}^r a_i$$を計算する問題を考える。 ナイーブに足し算をすると$$O(N)$$かかりうる。 しかしあらかじめ$$b_0 = 0, ~~ b_{n+1} = \sum_{j=0}^{n} a_j = b_n + a_n$$という数列を用意しておくと、 $$\sum_{i=l}^r a_i = b_{r+1} - b_l$$と$$O(1)$$で計算できる。

pythonicに書くと、sum(a[l:r]) が b[r] - b[l] で計算できると言うこと。 そう考えると、b[r] = sum(a[:r]) と分かりやすくて良い。

#id  0  1  2  3  4   5   6   7   8   9
a = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
b = [0] * (len(a) + 1)
for i in range(len(a)):
    b[i+1] = b[i] + a[i]

print(b[:7]) # [0, 1, 4, 9, 16, 25, 36]

# sum(a[3:6])
print(b[6] - b[3]) # 27

二次元累積和

for i in range(n):
    for j in range(n):
        ds[i + 1][j + 1] = ds[i + 1][j] + ds[i][j + 1] - ds[i][j] + d[i][j]

問題

しゃくとり法

ある長さNの配列a[i]を考える。 任意のiに対し、条件を満たすindexの範囲([0, j)や[j, N))の境界jを求めたい。 もしjがiに対して単調な振る舞いをする場合、これを$O(N)$で求めることができる。

right = 1
for left in range(n):
    while right < n and (some conditions):
        # some process
        right += 1

    # Segment [left, right) satisfies conditions
    # someprocess

典型的な例

  • 正数からなる数列において、総和がK以上となっている連続する部分列の個数
    • 任意のiに対して初めてsum(a[i:j]) >= Kとなるjを知りたい
  • 正数からなる配列において、2つの要素の積がK以上となるペアの数
    • 昇順ソート済みとする
    • 任意のiに対して、a[j] >= K / a[i]となるjを知りたい
  • ある数列において、狭義単調増加となっている連続する部分列の個数
  • ある数列において重複する項がないような連続する部分列の列挙
  • スライド最小値

問題

いもす法

https://imoz.jp/algorithms/imos_method.html

問題

座標圧縮

def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=None, reverse=reverse)):
        zipped[xi] = i
        unzipped[i] = xi
    return zipped, unzipped

問題

適切な前計算による高速化

繰り返し行われる処理に関して事前に計算をしていくことで高速化することも大事。 累積和・Combinationの事前計算などもこのようなニュアンスでの高速化。

問題

よく考えると実は少ない計算量で済むなってやつ

うまく言えん... 問題

イベントソート

問題

Run-length圧縮

問題

繰り返し二乗法・ダブリング

冪乗の高速な計算

python

問題

動的計画法 - Dynamic Programming

DP

グラフ

graph

数学

math

幾何

geometry

構築系

https://www.hamayanhamayan.com/entry/2017/08/21/102212 「条件を満たす(数列|グラフ|操作列|その他)を一つ構成せよ」というタイプの問題。 難しい。

  • 条件によく注目する
  • まず特定の条件で解を構築してみる
  • 小さい具体例で構成してみる

といったことをして、解の構成方法の糸口を探すしかない(?)。

問題

ゲーム関係

game

文字列系

string

データ構造

Union-Find木

グループ分けを管理するためのデータ構造。以下の操作が「効率的」に行える。

  • 同じグループかどうかの確認
  • ２つのグループの併合

シンプルな実装

一番ナイーブな実装は以下。

struct UnionFind {
    vector<int> par;
    UnionFind(int N) : par(N) {
        for (int i = 0; i < N; i++) par[i] = i;
    }
    int find(int x) {
        if (par[x] != x) par[x] = find(par[x]); // contraction
        return par[x];
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        par[x] = y;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};

UnionFind uf(5); // uf.par [0, 1, 2, 3, 4]
uf.unite(0, 1)   // uf.par [1, 1, 2, 3, 4]
uf.unite(1, 2)   // uf.par [1, 2, 2, 3, 4]
uf.find(0)       // uf.par [2, 2, 2, 3, 4]
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) ==  self.find(y)

uf = UnionFind(5) # uf.par [0, 1, 2, 3, 4]
uf.unite(0, 1)    # uf.par [1, 1, 2, 3, 4]
uf.unite(1, 2)    # uf.par [1, 2, 2, 3, 4]
uf.find(0)        # uf.par [2, 2, 2, 3, 4]

ちょっと工夫した実装

更に上手に実装すると、

  • rank of union (蟻本はこっち)
  • size of union (今回はこっち)

を持つこともできる。(参考 : http://drken1215.hatenablog.com/entry/2019/03/03/224600)
ポイントとしては、parという配列を

  • 全て-1で初期化。
  • rootのnodeについては、-(size of union)を保持する。（逆に負の数であればroot。）
  • root以外のnodeについては、parentのidを保持する。（逆に正の数であればleaf。）
  • (size of union)に簡単にアクセスできるようになったので、merge techniqueとして、 サイズが大きなものに小さなものを結合する ようにする。
    • データ構造をマージする一般的なテク

      大きさに気をつけて小さい方を大きい方にくっつけるという考え方を応用することで，色々な普通のデータ構造にマージ機能を追加することができます．

という形で実装すること。

class UnionFind():
    def __init__(self, n):
        self.par = [-1] * n

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # contraction
            return self.par[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

問題

Segment Tree

長さ$N$の列に対して、

  • ある区間全体に対する演算
  • ある点の値の変更

を$O(\log N)$で可能なデータ構造。モノイドと関わりが深く、面白い。 構築は$O(N)$でできる。

具体的な実装の注意点

  • 二分木を0-indexedで持つか、1-indexedで持つか。
    • 0-indexedの場合、ノードkについて
      • left-child : 2*k+1
      • right-child : 2*k+2
      • parent : (k-1) // 2
    • 1-indexedの場合、ノードkについて
      • left-child : 2*k
      • right-child : 2*k+1
      • parent : k // 2
  • queryの書き方
    • アリ本的な再帰を用いた実装（こっちの方がわかりやすい）
    • 再帰を使わず、木を登りながら計算する実装（こっちの方がpythonでは早い）

抽象化セグメントツリー(0-indexed)

queryを再帰で書いたアリ本的な0-indexed Segment Tree。

class SegmentTree0():
    """
    0-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n - 1)  # binary tree (0-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n - 1]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]  # set data in leaf
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def query(self, a, b):
        # query for interval [a, b) (a, b : 0-indexed)
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            # [a, b) and [l, r) have no intersection
            return self.ele_id
        if a <= l and r <= b:
            # [a, b) includes [l, r)
            return self.data[k]
        else:
            # [a, b) and [l, r) have some overlap
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.op_func(child_l, child_r)

抽象化セグメントツリー(1-indexed)

queryを再帰ではなくループで書いた1-indexed Segment Tree 。

class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree (1-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]  # set data in leaf
        for i in reversed(range(self.n)):
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n
        self.data[i] = x
        while i > 1:
            i = i >> 1  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.op_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.op_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret

RMQ - Range Minimum Query

INF = (1 << 31) - 1
st_rmq = SegmentTree0(n, INF, lambda a, b: min(a, b))

RMQ with index

ある範囲の最小値の値とそのindexも必要なqueryに答えなければならない場合、 ただのRMQを改良し、セグ木に(値, index)を持たせるようにすれば良い。 operation_funcも最初の要素の大小を比較するように明記すればOK。

INF = (10**10, -1)
operation_func = lambda a, b: a if a[0] < b[0] else b
st_rmq = SegmentTree0(n, INF, operation_func)

RSQ - Range Sum Query

st_rsq = SegmentTree0(n, 0, lambda a, b: a + b)

Range GCD Query

GCDをユークリッドの互除法で適宜書く時、整数に対するGCDはモノイドをなす。単位元は0。

from fractions import gcd
st_gcd = SegmentTree0(n, 0, gcd)

Reference

問題

BIT (fenwick tree)

Fenwick Tree とも呼ばれる。数列に対し, ある要素に値を加える操作と, 区間和を求める操作をそれぞれ対数時間で行うことが出来るデータ構造。セグメント木や平衡二分探索木の機能を制限したものであるが, 実装が非常に単純で定数倍も軽いなどの利点がある。

BITはセグ木を制限したものなので、応用範囲は狭いが、実装が簡単で定数倍が軽いのが特徴らしい。 なので当然BITの問題はセグ木でも出来る。

$v_1, v_2, \cdots, v_N$という数列を考えた時に、

  • 前から$m$項分の和の計算: $~ {\rm sum}(m) = \sum_{i=1}^{m} v_i$
    • 特に${\rm sum}(0) = 0$
  • 第$i$項に加算: $~ v_i += x$

を$O(\log N)$で可能なデータ構造。 また特に、常に$v_i \geq 0$を満たす場合には

  • 二分探索: $~ {\rm sum}({\rm index}) \geq x$を満たす最小のindexを見つける

も$O(\log N)$で可能。

class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

値の範囲($1 \sim N$)が分かっている場合のstd::setライクな使い方ができる。具体的には

  • $v_i=~$(数$i$が集合に入っていれば1、そうでなければ0)

として、この数列にBITを適用することで、

  • 集合への要素の追加・削除 (add)
  • 指定された要素は何番目に小さいか (sum)
  • $x$番目に小さい要素は何か (bisect_left)

を全て$O(\log N)$で出来る。 （セグ木でも出来るが、bisect_leftが遅くなる or 実装が面倒）

Reference

区間加算の対応

頑張るとできる

問題

何とも言えないけど競プロっぽいやつ

うまく言語化できないけど、競プロっぽい問題はたくさんあるし、慣れないと解けない。 ちょっとずつこれらのまとめもしていきたい。

問題

Memo

python関連

  • python3でTLEする場合はPyPy3に変えてみると通ることもある。
    • ただし再帰使って書いたDFSなどはpython3の方が早かったりもする
  • python3でTLEする場合、多数行の読み込みが遅いだけのことがある。遅いinput()の代わりにsys.stdin.readlineを使おう。 
    import sys
input = sys.stdin.readline
input = lambda: sys.stdin.readline().rstrip() # sys.stdin.readlineは改行文字を含んでしまうので注意
    • sys.stdin.buffer.readline も最近見かける。こいつは一体...???
  • pythonでtupleのlistやlistのlistをソートするのはそもそも遅い。keyにitemgetterを指定すると速くなったりする。 
    from operator import itemgetter
x = [(1,2), (3, 4), (2, 5), (1, 0), (5, 2)]
x.sort(key=itemgetter(0))
  • pythonの謎のREについて。
    • 再帰関数を使っているならば可能性の一つとして、RecursionError: maximum recursion depth exceeded in comparison がある。
    • 対策は以下。 
      import sys
sys.setrecursionlimit(10**6)
  • PyPy3(2.4.0)ではmath.log2が使えない。
  • Pythonは割り算(/)するとdoubleの演算になって精度が64bitじゃなくなる
  • DPの配列の初期値にINFを入れたいときに、INF = float("inf")を使うと遅いっぽい
    • 問題に応じて適宜INF = 10**9とかにした方が良い
  • PythonのListのランダムアクセス（して代入するの）はかなり遅いっぽい。
    • DPなどで 
      dp[j | c] = min(dp[j] + a, dp[j | c])
      と書くのであれば、 
      if dp[j] + a < dp[j | c]:
    dp[j | c] = dp[j] + a
      と、if文を書いた方が早い。

Reference

Python関連

C++関連