競プロで使えそうな標準機能

Latest Author はむ吉🐹 /Date 2016-08-31 18:07:03 / Views 3175
1 (Favした一覧ページは作成中です。)

細かく説明すると大変なので、簡単な説明だけでも。(現在運営者のメモ中)

C++

next_permutation
言わずと知れた、順列を求める事ができる関数。
ソートしておかないと、全ての順列を列挙できないことに注意。
prev_permutaionなどもある。
max_element, min_element
最大値・最小値を求める。
vector<int>のときは、
int max_value = *max_element(v.begin(), v.end());
count
ある値の数を数える。
accumulate
総和を求める。和の型は要素の型でなく第3引数の型となるのでオーバーフローに注意。
文字列の連結などももちろん可能。
unique
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
というコードにより、v中の重複した要素を削除できる。
lower_bound, uppper_bound
ソート済みのコンテナaに対し、
lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置
を求める。
aがランダムアクセスできるコンテナでないと効率が悪くなってしまうことに注意する。 setやmapに対して適用したい場合は、それのメンバ関数の方を使うべきである。
bitset
ビットベクトルを格納し、基本的な操作ができる。もちろんワードサイズ分の定数倍が速いことが期待できる。 ビット演算 &,|,^,~ のほかシフト演算もでき、便利である。また、popcountもできる。
bitsetのサイズはコンパイル時定数である必要がある。 一方、vector<bool>は動的にサイズを決定・変更でき、メモリ効率もいいが、操作はできない。
swap
vectorやset,mapなどコンテナのうち動的なものにはv.swap(w)という形で使えるメンバ関数があり、$O(1)$時間で内容をswapできる。
例えばDPをメモリ節約する場合や、マージテクをする場合などに使える。
非メンバ関数のswapを呼んだ場合にも自動的にオーバーロードされた関数が呼ばれ、このメンバ関数が呼ばれる。
priority_queue
優先度付きキュー。
ダイクストラやプリム法の実装の際に便利。
「優先度」なので値の大きい方から取り出してくるので、ダイクストラなど小さいものから処理したい場合は符号を反転して突っ込むと良い。
また、ノード番号なども必要とあればpairなどでまとめて、(コスト,ノード番号)などの形で突っ込む。

Java

Integer, Long
int,longに対する関数群。ひと通りあるので必見。
Java8からはunsigned系の関数がふえてlong単体で2^64-1以下の整数を扱えるようになった。
Arrays, Collections
配列, コレクションに対する関数群。
HashSet, HashMap
ハッシュマップ。挿入・削除・参照がO(1)でできる。
TreeSet, TreeMap
赤黒木。Comparatorを自前で定義するとき0を返したものは同一と扱われ闇に葬られるので注意。
PriorityQueue
優先度付きキュー
BigInteger
immutableな多倍長整数型クラス、isProbablePrimeやmodPowやmodInverse,gcdなどの便利メソッドもある。
BitSet
C++の節にもあるがビットベクトルを生成する。boolean配列よりメモリ効率がよい。
ArrayDeque
Java7以降から使えるQueueの実装。ArrayListより速い。
Point2D, Line2D
2次元幾何用の関数群。基本的なものしかない。

Python

heapq
優先度付きキュー 使い方としたら、専用のクラスがあるというわけでなく配列をヒープ化する。
collections.deque
両端キュー。スタックやキューとして用いることができる。
collections.namedtuple
名前付きタプル。構造体もどきを作るのに便利。
Counter
連想配列とカウンターを持ったクラス
itertools.permutations
いわゆる順列、競プロによく出てくるあれです。組み合わせを列挙できる itertools.combinationsもある。
itertools.product
デカルト積。これを使うと多重ループを簡単に書ける。たとえばワーシャル・フロイド法で出てくる三重ループは
for i, j, k in itertools.product(range(n), repeat=3):
のようになる。
float('inf')
無限大。最小値を求めるときの初期値などに。
負の無限大はfloat('-inf')あるいは-float('inf')。
文字列と掛け算
'1'を10個並べたかったら
'1' * 10
と書くと'1111111111'になる。'10'にはならない。
defaultdict
辞書にキーが存在しないときに自動的に呼ばれる関数を指定できる。例) defaultdict(int)
from collections import defaultdict
modpow(x, y, mod)
pow()の3つめの引数で指定する。
x = pow(123456789, 987654321, int(1e9)+7)
copy.copy(x)
オブジェクトをシャロー(浅い)コピーする。
copy.deepcopy(x)
オブジェクトをディープ(深い)コピーする。
hypot(x, y)
幾何で出てくるユークリッド距離$\sqrt{x^2 + y^2}$のこと。
from math import hypot
gcd(x, y)
最大公約数。
from fractions import gcd
Python 3.5からは次でもよい。
from math import gcd
lcm(最小公倍数)は標準には含まれていないので自分で実装する必要がある。
lcm = lambda x, y: x * y / gcd(x, y)
分数(有理数)
精度が欲しい場合に、なるべく分数(有理数)で計算して、最後に小数にするといった案が考えられる。
処理速度が小数で計算するときよりも遅くなるので、そこには注意すること。
from fractions import Fraction
条件演算子
'真のときの値' if 条件 else '偽のときの値'
と書く。
例)
a = 'Yes' if ok else 'No'
また、
x = 789 if n%3==0 else 654 if n%3==1 else 123
のように続けて書くこともできるといえばできるが、可読性が…。
format関数
右詰め、左詰め、0埋め、コンマ付与、小数点以下第何位まで出力など、いろいろできる。
s = '{0:,}'.format(9876543210) # 9,876,543,210
enumerate
リストの位置と要素を一緒に取得したいときに使う。
for i, e in enumerate([2, 3, 5, 7, 11]):
    print('{0}: {1}'.format(i, e))
bisect
二分探索。自分で1から書かなくても用意されている。
import bisect
転置行列
リストのリストarrに対して、zip(*arr)とすればいい。
arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print zip(*arr) # [(1, 2, 3), (4, 5, 6), (7, 8, 9)]
print map(list, zip(*arr)) # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
sys.setrecursionlimit
スタックの深さの最大値を設定できる。深さ優先探索などで再帰が深くなるときに便利。あまり大きくするとクラッシュするので注意。
array
整数や浮動小数点数など、決まった型の値だけを格納できる配列。リストの代わりに使うと、実行時間を改善できるかもしれない。 リストと大体同じだが、sortなどのメソッドはないので注意。

Go

heap
優先度付きキュー。使い方としたら、専用のクラスがあるというわけでなく配列をヒープ化する。

C#

Int32(int), Int64(long), Decimal(decimal)
int,long,decimalに対する関数群。intやlong、decimalはそれぞれInt32、Int64、Decimalのエイリアス。decimalはdoubleよりも扱える範囲は狭いものの精度が高いため、確率問題の精度落ちによるWA対策として使うことができる。
Math
基本的な数学関数群。最低限必要なものは揃っている。
Array, Enumerable
配列, コレクションに対する関数群。Linq(language integrated query)と呼ばれる定数倍が重いものの強力な関数群が存在する。
Dictionary, HashSet
ハッシュマップ。挿入・削除・参照がO(1)でできる。
SortedDictionary, SortedSet
赤黒木。比較関数を自前で定義するとき0を返したものは同一と扱われ闇に葬られるので注意。C++のsetに存在するlower_boundやupper_boundを行うことができないため、非常に使いにくい。C#には優先度付キューが存在しないため、代わりに使用することもある。その際は比較関数を適切に設定する必要がある。
BigInteger
多倍長整数型構造体。System.Numerics.dllに存在するため、ジャッジの環境によっては使えないこともある。
String(string), StringBuilder, StringComparer
文字列、及び文字列操作、比較。stringはimmutableな文字列型、変更したい場合はchar[]を使う。文字列の連結を複数回行う場合はStringBuilderを使う。StringComparerは文字列の比較関数を提供する。