useful_standard_function.html

<title>競プロで使えそうな標準機能</title>

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


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

<h4 class="shadow">Java</h4>
<dl>
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/lang/Integer.html">Integer</a>, <a href="http://docs.oracle.com/javase/jp/8/docs/api/java/lang/Long.html">Long</a></dt>
    <dd>int,longに対する関数群。ひと通りあるので必見。<br/> Java8からはunsigned系の関数がふえてlong単体で2^64-1以下の整数を扱えるようになった。</dd>
    
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html">Arrays</a>, <a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/Collections.html">Collections</a></dt>
    <dd>配列, コレクションに対する関数群。</dd>
    
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/HashSet.html">HashSet</a>, <a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/HashMap.html">HashMap</a></dt>
    <dd>ハッシュマップ。挿入・削除・参照がO(1)でできる。</a></dd>

    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/TreeSet.html">TreeSet</a>, <a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/TreeMap.html">TreeMap</a></dt>
    <dd>赤黒木。Comparatorを自前で定義するとき0を返したものは同一と扱われ闇に葬られるので注意。</a></dd>
    
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/PriorityQueue.html">PriorityQueue</a></dt>
    <dd>優先度付きキュー</a></dd>

    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/math/BigInteger.html">BigInteger</a></dt>
    <dd>immutableな多倍長整数型クラス、isProbablePrimeやmodPowやmodInverse,gcdなどの便利メソッドもある。</dd>
    
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/BitSet.html">BitSet</a></dt>
    <dd>C++の節にもあるがビットベクトルを生成する。boolean配列よりメモリ効率がよい。</dd>
    
    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html">ArrayDeque</a></dt>
    <dd>Java7以降から使えるQueueの実装。ArrayListより速い。</dd>

    <dt><a href="http://docs.oracle.com/javase/jp/8/docs/api/java/awt/geom/Point2D.html">Point2D</a>, <a href="http://docs.oracle.com/javase/jp/8/docs/api/java/awt/geom/Line2D.html">Line2D</a></dt>
    <dd>2次元幾何用の関数群。基本的なものしかない。</dd>
</dl>

<h4 class="shadow">Python</h4>
<dl>
    <dt><a href="http://docs.python.jp/2/library/heapq.html">heapq</a></dt>
    <dd>優先度付きキュー 使い方としたら、専用のクラスがあるというわけでなく配列をヒープ化する。<br>
    
    <dt><a href="http://docs.python.jp/3/library/collections.html#collections.deque">collections.deque</a></dt>
    <dd>両端キュー。スタックやキューとして用いることができる。</dd>
    
    <dt><a href="http://docs.python.jp/3/library/collections.html#collections.namedtuple">collections.namedtuple</a></dt>
    <dd>名前付きタプル。構造体もどきを作るのに便利。</dd>

    <dt><a href="https://docs.python.org/ja/3/library/collections.html#collections.Counter">collections.Counter</a></dt>
    <dd>連想配列とカウンターを持ったクラス
    </dd>
    
    <dt><a href="http://docs.python.jp/3/library/itertools.html#itertools.permutations">itertools.permutations</a></dt>
    <dd>いわゆる順列、競プロによく出てくるあれです。組み合わせを列挙できる
    <a href="http://docs.python.jp/3/library/itertools.html#itertools.combinations">itertools.combinations</a>もある。<br>
    </dd>
    
    <dt><a href="http://docs.python.jp/3/library/itertools.html#itertools.product">itertools.product</a></dt>
    <dd>デカルト積。これを使うと多重ループを簡単に書ける。たとえばワーシャル・フロイド法で出てくる三重ループは<br>
    <pre>for i, j, k in itertools.product(range(n), repeat=3):</pre>
    のようになる。
    </dd>
    
    <dt>float('inf')</dt>
    <dd>無限大。最小値を求めるときの初期値などに。<br>
        負の無限大はfloat('-inf')あるいは-float('inf')。
    </dd>
    
    <dt>文字列と掛け算</dt>
    <dd>'1'を10個並べたかったら<br>
        <pre>'1' * 10</pre>
        と書くと'1111111111'になる。'10'にはならない。
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/collections.html?highlight=defaultdict#collections.defaultdict">defaultdict</a></dt>
    <dd>辞書にキーが存在しないときに自動的に呼ばれる関数を指定できる。例) <code>defaultdict(int)</code><br>
        <pre>from collections import defaultdict</pre>
    </dd>
    
    <dt>modpow(x, y, mod)</dt>
    <dd>
    <a href="http://docs.python.jp/2.7/library/functions.html?highlight=pow#pow">pow()</a>の3つめの引数で指定する。<br>
    <pre>x = pow(123456789, 987654321, int(1e9)+7)</pre>
        
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/copy.html#copy.copy">copy.copy(x)</a></dt>
    <dd>
    オブジェクトをシャロー（浅い）コピーする。
    </dd>
   
      <dt><a href="http://docs.python.jp/2.7/library/copy.html#copy.deepcopy">copy.deepcopy(x)</a></dt>
    <dd>
    オブジェクトをディープ（深い）コピーする。
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/math.html?highlight=hypot#math.hypot">hypot(x, y)</a></dt>
    <dd>
        幾何で出てくるユークリッド距離$\sqrt{x^2 + y^2}$のこと。<br>
        <pre>from math import hypot</pre>
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/fractions.html#fractions.gcd">gcd(x, y)</a></dt>
    <dd>
        最大公約数。<br>
        <pre>from fractions import gcd</pre>
        Python 3.5からは次でもよい。
        <pre>from math import gcd</pre>
        lcm(最小公倍数)は標準には含まれていないので自分で実装する必要がある。<br>
        <pre>lcm = lambda x, y: x * y / gcd(x, y)</pre>
        Python 3.9からlcmが使えるようになった。
        <pre>from math import lcm</pre>
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/fractions.html?highlight=fraction#fractions.Fraction">分数</a>(有理数）</dt>
    <dd>
        精度が欲しい場合に、なるべく分数(有理数）で計算して、最後に小数にするといった案が考えられる。<br>
        処理速度が小数で計算するときよりも遅くなるので、そこには注意すること。<br>
        <pre>from fractions import Fraction</pre>
    </dd>

    <dt>条件演算子</dt>
    <dd>
        '真のときの値' if 条件 else '偽のときの値'<br>
        と書く。<br>
        例)<br>
        <pre>a = 'Yes' if ok else 'No'</pre>
        また、<br>
        <pre>x = 789 if n%3==0 else 654 if n%3==1 else 123</pre>
        のように続けて書くこともできるといえばできるが、可読性が…。
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/string.html#formatspec">format関数</a></dt>
    <dd>
        右詰め、左詰め、0埋め、コンマ付与、小数点以下第何位まで出力など、いろいろできる。<br>
        <pre>s = '{0:,}'.format(9876543210) # 9,876,543,210</pre>

    </dd>
    
    <dt><a href="http://docs.python.jp/2/library/functions.html#enumerate">enumerate</a></dt>
    <dd>
        リストの位置と要素を一緒に取得したいときに使う。<br>
        <pre>for i, e in enumerate([2, 3, 5, 7, 11]):<br>&nbsp;&nbsp;&nbsp;&nbsp;print('{0}: {1}'.format(i, e))</pre>
    </dd>
    
    <dt><a href="http://docs.python.jp/2.7/library/bisect.html">bisect</a></dt>
    <dd>
        二分探索。自分で1から書かなくても用意されている。<br>
        <pre>import bisect</pre>
    </dd>

    <dt>転置行列</dt>
    <dd>
        リストのリストarrに対して、<code>zip(*arr)</code>とすればいい。<br>
        <pre>arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]<br>print zip(*arr) # [(1, 2, 3), (4, 5, 6), (7, 8, 9)]<br>print map(list, zip(*arr)) # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]</pre>
    </dd>
    
    <dt><a href="http://docs.python.jp/3/library/sys.html#sys.setrecursionlimit">sys.setrecursionlimit</a></dt>
    <dd>スタックの深さの最大値を設定できる。深さ優先探索などで再帰が深くなるときに便利。あまり大きくするとクラッシュするので注意。</dd>
    
    <dt><a href="http://docs.python.jp/3/library/array.html">array</a></dt>
    <dd>整数や浮動小数点数など、決まった型の値だけを格納できる配列。リストの代わりに使うと、実行時間を改善できるかもしれない。
    リストと大体同じだが、sortなどのメソッドはないので注意。</dd>

</dl>

<h4 class="shadow">Go</h4>
<dl>
    <dt><a href="http://golang.org/pkg/container/heap/">heap</a></dt>
    <dd>優先度付きキュー。使い方としたら、専用のクラスがあるというわけでなく配列をヒープ化する。</dd>
</dl>

<h4 class="shadow">C#</h4>
<dl>
    <dt><a href="https://msdn.microsoft.com/ja-jp/library/system.int32%28v=vs.110%29.aspx">Int32(int)</a>, <a href="https://msdn.microsoft.com/ja-jp/library/system.int64%28v=vs.110%29.aspx">Int64(long)</a>, <a href="https://msdn.microsoft.com/ja-jp/library/system.decimal%28v=vs.110%29.aspx">Decimal(decimal)</a></dt>
    <dd>int,long,decimalに対する関数群。intやlong、decimalはそれぞれInt32、Int64、Decimalのエイリアス。decimalはdoubleよりも扱える範囲は狭いものの精度が高いため、確率問題の精度落ちによるWA対策として使うことができる。</dd>
    
    <dt><a href="https://msdn.microsoft.com/ja-jp/library/system.math%28v=vs.110%29.aspx">Math</a></dt>
    <dd>基本的な数学関数群。最低限必要なものは揃っている。</dd>

    <dt><a href="https://msdn.microsoft.com/ja-jp/library/system.array%28v=vs.110%29.aspx">Array</a>, <a href="https://msdn.microsoft.com/ja-jp/library/system.linq.enumerable%28v=vs.110%29.aspx">Enumerable</a></dt>
    <dd>配列, コレクションに対する関数群。Linq(language integrated query)と呼ばれる定数倍が重いものの強力な関数群が存在する。</dd>
    
    <dt><a href="https://msdn.microsoft.com/ja-jp/library/xfhwa508%28v=vs.110%29.aspx">Dictionary</a>, <a href="https://www.google.co.jp/search?q=hashset&ie=utf-8&oe=utf-8&hl=ja">HashSet</a></dt>
    <dd>ハッシュマップ。挿入・削除・参照がO(1)でできる。</a></dd>

    <dt><a href="https://msdn.microsoft.com/ja-jp/library/f7fta44c%28v=vs.110%29.aspx">SortedDictionary</a>, <a href="https://msdn.microsoft.com/ja-jp/library/dd412070%28v=vs.110%29.aspx">SortedSet</a></dt>
    <dd>赤黒木。比較関数を自前で定義するとき0を返したものは同一と扱われ闇に葬られるので注意。C++のsetに存在するlower_boundやupper_boundを行うことができないため、非常に使いにくい。C#には優先度付キューが存在しないため、代わりに使用することもある。その際は比較関数を適切に設定する必要がある。</a></dd>

    <dt><a href="https://msdn.microsoft.com/ja-jp/library/system.numerics.biginteger%28v=vs.110%29.aspx">BigInteger</a></dt>
    <dd>多倍長整数型構造体。System.Numerics.dllに存在するため、ジャッジの環境によっては使えないこともある。</dd>
    
     <dt><a href="https://msdn.microsoft.com/ja-jp/library/system.string%28v=vs.110%29.aspx">String(string)</a>, <a href="https://msdn.microsoft.com/ja-jp/library/system.text.stringbuilder%28v=vs.110%29.aspx">StringBuilder</a>, <a href="https://msdn.microsoft.com/ja-jp/library/system.stringcomparer%28v=vs.110%29.aspx">StringComparer</a></dt>
    <dd>文字列、及び文字列操作、比較。stringはimmutableな文字列型、変更したい場合はchar[]を使う。文字列の連結を複数回行う場合はStringBuilderを使う。StringComparerは文字列の比較関数を提供する。</dd>
    
</dl>

<h4 class="shadow">Ruby</h4>
<dl>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Array.html#I_COMBINATION">Array#combination</a></dt>
    <dd>組み合わせ。<code>[1,2,3].combination(2){|l| p l}</code> は <code>[1, 2] [1, 3] [2, 3]</code>を列挙する。</dd>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Array.html#I_PERMUTATION">Array#permutation</a></dt>
    <dd>順列。<code>[1,2].combination(2){|l| p l}</code> は <code>[1, 2] [2, 1]</code>を列挙する。</dd>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Array.html#I_REPEATED_COMBINATION">Array#repeated_combination</a></dt>
    <dd>重複あり組み合わせ。<code>[0,1].repeated_combination(2){|l| p l}</code> は <code>[0, 0] [0, 1] [1, 1]</code>を列挙する。</dd>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Array.html#I_REPEATED_PERMUTATION">Array#repeated_permutation</a></dt>
    <dd>重複あり順列。<code>[0, 1].repeated_combination(2){|l| p l}</code> は <code>[0, 0] [0, 1] [1, 0] [1, 1]</code>を列挙する。</dd>
    <dt>Array#[]=(配列アクセス)</a></dt>
    <dd>負の値を指定した時、配列の後ろから数えた要素にアクセスする。<code>arr=[1,2,3]; p arr[-1]</code> で3を出力する。</dd>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Array.html#I_BSEARCH">Array#bsearch</a>, <a href="https://docs.ruby-lang.org/ja/latest/class/Range.html#I_BSEARCH">Range#bsearch</a></dt>
    <dd>二分探索</dd>
    <dt>Enumerable#each_cons</dt>
    <dd>要素を重複ありで n 要素ずつに区切り、 ブロックに渡して繰り返します。</dd>
    <dt>Enumerable#each_slice</dt>
    <dd>n 要素ずつブロックに渡して繰り返します。</dd>
    <dt><a href="https://docs.ruby-lang.org/ja/latest/class/Prime.html">Prime</a></dt>
    <dd>素数全体を表すクラス。Enumerableなので、<code>Prime.take_while{|x|x<10}</code>等の書き方が出来る。</dd>
</dl>