目次

AtCoder

有用な外部サービス

精進

AtCoderの仕様

書いたコードはMain.cppとして保存され，コンパイルされる．

出題される問題は，必ずしもすべての状況に対応しなければいけないというわけでもないっぽい？
当然か？標準入力がバグっている場合なども考慮しなくて良いし(あたりまえかも)，想定範囲内の入力であっても必ず正しい出力である必要があるわけでもない(テストケースさえクリアすれば良い)．そのためテストケースは公開されない．そもそも決められた制約内で解けない問題もあるが，確率的に最も良さそうな感じの出力が得られるコードを書けば良いという暗黙の取り決めのよう．
例えばN回以内の操作でM個をソートしろという問題は$N<(M-1)M/2$なら解けないが，答えとして正しいであろう確率が最大となるようにすればそれが出題者側の想定した答え．

競プロ対策を一切していない通常のプログラマ(業務経験あり or 情報系大学生・大学院生)はABCのC問題までなら普通に解ける。 早解きの訓練をしていないはずなので(傾向や答え方，AtCoder特有のルールを知らないはずなので)茶色ぐらいのスコアに落ち着く．

早解きの訓練をすれば緑や青色のパフォーマンスがでる．

D問題以降は有名なアルゴリズムを言われて直ぐ書ける用に訓練しておく必要がある．

ファイルから標準入力

#include <fstream>
 
std::ifstream in("input.txt");
std::cin.rdbuf(in.rdbuf());

パイプから標準入力

cat hoge.txt | ./a.out

C++再確認

数値最大値

AtCoderでは Linux x86_64 を使っているので int 32bit, long 64bit, long long 64bit である。

型 最大値 値
int 21億 = $2 \times 10^9$ 2,147,483,647
long = long long 922京 = $9 \times 10^{18}$ 9,223,372,036,854,775,807

最大値/最小値は基本的にベタ書きが良さげ。わかりやすいので。 

const int MYINTMAX=2147483647;
const int MYINTMIN=-2147483648;
const long MYLONGMAX=9223372036854775807;
const long MYLONGMIN=-9223372036854775808;

PIはベタ書きが良さげ 

const double PI=3.14159265358979323846;

c++データ構造再確認

普段書かない言語は直ぐに仕様を忘れるのでチートシートを作るべき

構造 最初 終わり 長さ 参照
std::vector .begin() .end() .size() .at(i)
std::string .begin() .end() .size() or .length() [i]

vector

sizeは戻り値が size_t である．メモリ領域を変更しないで扱うときは 

size_t i=0;i<arr.size();i++

別の書き方として， 

vector<int>::iterator i=arr.begin();i!=arr.end();i++

があるっぽい．

autoでvector<T>::iteratorを書くのをやめられる．

値の参照，代入には arr[i] と arr.at(i) がある． メモリ領域に変更があるばあいは後者でないと動かない．

vectorの初期化 

// 1次元
vector<int> arr(N, 0);
 
// 2次元
vector< vector<int> > DP(N, vector<int>(M, 0));
 
// 3次元
vector< vector< vector<int> > > DP(N, vector< vector<int> >(M, vector<int>(L,0)));

map

pythonでいうdict

valはmutable? atと[]はどう違う？ 舐めるとどうなる？ 舐めたときどんな順番になっている？

キーの存在判定

pair

tupleの要素数が2のケース。 mapのキーとして利用できる。

標準の記号だけで作れるので書くのが楽。 

map< pair<long,long>, pair<long,long> > data{};
data[{0,1}] = {0,0};
data[{0,1}] = { data[{0,1}].first+1, data[{0,1}].second   };

最初の記号には .first でアクセス。２つめの記号には .second でアクセス。

tuple

pythonでいうtuple．

関数の戻り値を複数にするのにも使える． 

std::tuple<int,int> hoge(){
    return std::forward_as_tuple(fuga, piyo);
}
 
int main(){
    int a,b;
    std::tie(a,b) = hoge();
}

mapのハッシュに使うときは以下のように make_tuple 関数を使うと楽。 

std::tuple<int,int,int> foo = std::make_tuple( hoge, fuga, piyo );

queue

queue<long> q;
q.push(i);
long x = q.front(); q.pop();

便利関数について

sort()でソートされる範囲(vectorの例)

vector<int> arr = {6, 4, 9, 2, 0, 3, 1};
　
begin
0 		　

1 		　

2 		　

3 		　

4 		　

5 		　

6 		size
end
7
6 4 9 2 0 3 1
sort(arr.begin(), arr.begin()+1)
　
begin
0 		　

1 		　

2 		　

3 		　

4 		　

5 		　

6 		size
end
7
6 4 9 2 0 3 1
sort(arr.begin()+1, arr.begin()+4)
　
begin
0 		　

1 		　

2 		　

3 		　

4 		　

5 		　

6 		size
end
7
6 2 4 9 0 3 1

便利アルゴリズム

std::sort std::sort(arr.begin(), arr.end()) で昇順になる．ソートは書かなくて良い．

c++の標準入出力再確認

cin,cout,endlなど

これでファイルから入力できる. 

#include <fstream>
int main(){
    std::ifstream in("bin4.txt");
    std::cin.rdbuf(in.rdbuf());

手元でのコンパイル

数学

モジュラ逆数について

定義

「Zを法としてXの逆数はY」の意味は、 Xの逆数Y $X^{-1} \equiv Y ({\rm mod} Z)$ が次の性質を満たす。 $XY \equiv 1 ({\rm mod} Z)$

例

存在

「Zを法とするXの逆元が存在する」は「XとZが互いに素である」と同値である。

求め方

拡張ユークリッド互除法というアルゴリズムで逆元は求まる。

応用

2019を法とすると10には逆元が存在して、その値は202である。一方で 2020を法とすると10には逆元が存在しない。

この状況では以下のような現象が起きている

つまり

競技プログラミング特有のテクニック

mod

競技プログラミングでは、

を評価したい。その計算の解答自体に意味はなく、 過程さえあってれば良いので、オーバーフローするような計算の場合は剰余部分にだけ着目して計算結果の正しさを評価する。

基本的に 1000000007 = 10^9+7 のあまりを計算することが多い。 1000000007 は適切に大きな素数であるので多用される。

結果と導出

A,B,Cが正の整数であることが前提。負の数は余りを求めると負の値になるのでダメ。

通常 modバージョン
和 A=B+C A = ( (B % mod) + (C % mod) ) % mod
差 A=B-C A = ( (B % mod) + ( (mod - C) % mod) ) % mod
積 A=B*C A = ( (B % mod) * (C % mod) ) % mod
商 A=B/C A = ( (B % mod) * modinv( C % mod) ) % mod

商の計算だけ mod での逆元を求めて利用する。逆元は以下の実装で求めることができる。

modinv
long modinv(long a, long m) {
    long b = m, u = 1, v = 0;
    while (b) {
        long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

TODO) なぜそうなるのかの導出について書く。

その他

ライブラリ化してくれている人 もいる。

補足: GCD, LCM

最大公約数、最小公倍数が必要な場面がかなり多いので覚えておく。 

long gcd(long a, long b){
    if(a < b) return gcd(b, a);
    long r = a%b;
    while(r){
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}

アルゴリズム

動的計画法

ナップサック問題的なやつを解く方法．
一瞬で書けるように訓練しておくとスコアがかなり変わる．

問題設定

value, costのデータが与えられていて，selectを求める問題．

value ${\bf v} = \left( v_1, v_2, \cdots, v_N \right)$
cost ${\bf w} = \left( w_1, w_2, \cdots, w_N \right)$
select ${\bf s} = \left( s_1, s_2, \cdots, s_N \right)$

最も典型的な問題

条件 $s_i \in \{0,1 \}$
${\bf w} \cdot {\bf s} \leq W_{\rm max}$
求めるもの ${\bf s}^* = \arg \max_{\bf s} {\bf v} \cdot {\bf s}$

$${\bf s}^* = \arg \max_{\bf s} {\bf v} \cdot {\bf s}\\ {\rm s.t. } \; {\bf w} \cdot {\bf s} \leq W_{\rm max} $$

桁DP

ある数 N 以下の数の中で条件を満たす数の個数を探すための動的計画法．

つまり以下を保持する3次元配列が必要

特にN以下かどうかの判定のインデックスを「未満フラグ」と呼ぶ．

注意: 桁DPでは先頭に0がある状態も考慮する

二分探索

ある関数 $f$ があって $f(x+1)-f(x) \geq 0$ なら(広義単調増加なら)二分探索が使える． 通常の線形探索が $O(N)$ なのに比べて $O(\log N)$ で調べられるので高速．

例題

データ中でx以下であるものの個数を調べられる関数 $y=f(x)$ がある．
このデータの中で小さい方からK番目の値は何か？

K=4

index:x 0 1 2 3 4 answer
$f_1(x)$ 0 3 4 5 6 2
$f_2(x)$ 0 3 4 4 5 2
$f_3(x)$ 0 2 2 3 5 4

K以上を満たすxの中で最小のもの．

$x^* = \min \{ x | f(x) \geq K \}$

具体的な実装とイメージ

TODO) ABC162用のメモに詳しく書いておいたのでそれをこっちに書く

tmp==T のところ，書き方によって異なる状態に収束する．

欲しい答えに，「同じ値となる場合を含むか？」「大きい/小さい場合もあるが許容する？」というのをちゃんと判断して決めよう．

union-find

グループを見つける．

N人いて，PiとPjは友達であるという情報がM個与えられる．

友達の輪で繋がっているグループを探す．

愚直に Mのループ内でグループとグループを統合していくと重いっぽい？ 統合処理でNをループさせるのがいけないっぽい？

ルートへの参照をするよりも親の参照をするほうが速いのか？

反対の反対の法則

010101010001010101000101 みたいな数列を 区間を指定して0と1を反転させることができるとき、 全ての数字を0にするには最小で何回の操作が必要か？

区間を選ぶと、「数列の途中の区間を選択する場合」

「数列の先頭から区間を選択する場合」、「数列の最後から区間を選択する場合」は上記の一方だけが適用される。 したがって関係性の変化は一回の操作で高々2個である。

例題) 01010 のとき、数値の仕切りは4つあって隣同士の関係性が違うところは4つある。 一回の操作で関係性は2つ入れ替わるので、2回操作すればよい。

0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

例題) 00110 のとき、数値の仕切りは4つあって隣同士の関係性が違うところは2つある。 一回の操作で関係性は2つ入れ替わるので、1回操作すればよい。

0 0 1 1 0
0 0 0 0 0

例題) 01011 のとき、数値の仕切りは4つあって隣同士の関係性が違うところは3つある。 一回の操作で関係性は2つ入れ替わるので、2回操作すればよい。

0 1 0 1 1
0 0 1 0 0
0 0 0 0 0

例題) 10101 のとき、数値の仕切りは4つあって隣同士の関係性が違うところは4つある。 一回の操作で関係性は2つ入れ替わるので、2回操作すればよいと思えるが、両端が1の場合は追加で1回反転が必要である。

1 0 1 0 1
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

つまり

自明な貪欲法

【命題】 0または1のみを使って構成される数列をいくつかの断片に区切りたい。 各断片は数列の総和がK以下となるようにしなければいけないとき、最小の区切り回数はいくつか？

これは貪欲法で前から詰めていった場合の数と同じになる。
【証明】
数列全体の総和を $S$ とする。 貪欲法で区切られた各区間内での数列の総和を $A_1, A_2, \dots A_{N-1}, A_N$ とすると、 貪欲法の場合、 $A_1 = A_2 = \cdots = A_{N-1} = K$ である。 さらに $1 \leq A_N \leq K$ であり、 $A_N = S-K\times (N-1)$ である。 現在の区切り回数は $N-1$ であり、これを $N-2$ に以下にしたいが、$A_1,A_2,A_3,\dots,A_{N-1} \leq K$ を満たして $ \sum_{i=1}^{N-1} A_i = S$ とすることは不可能である。

【命題】 0か1か2を使うとき

【証明】 ある数列 $X$ があって、それを区切る最小回数が $f(X)$ で求まるとき、 $X$ の前にいくつかの数列 $v$ を足した数列 $vX$ については、 $f(vX)$ で最小回数が求まる。 $f(X) \leq f(vX)$ は自明である。 つまり、貪欲法で前から詰め込めるだけ詰めるとき、 あまった文字列については最小の回数で区切ることができ、詰め込めるだけ詰めるのを抑えめにするとき最小回数以上の区切り回数が必要となる。

複数レーンで考えるときも同様である。

連続整数からN個選ぶときの和の種類数

0,1,2,…,N から i 個選んで和を計算するとき、和のパターンは何個ある？

i個で作れる最大の和 - i個で作れる最小の和 + 1

途中の和が全て存在することを証明できるか？

ABC163Dより

組み合わせ全探索

bit全探索でやる方法と nCi を深さ優先探索で生成する方法がある。

反省

浮動小数点数を出力するときの誤差

ABC154 D問題

期待値を各サンプルに対して計算し，連続するK個のサンプルの期待値の和の最大値を求める． 累積和を計算していくが，浮動小数点数のままでは誤差が大きく，WAになったのでlongで保持しておき， 最後に割り算をする方式に変更． しかし，longを2で割っても何故かWA．

小数点以下は.0か.5にしかならないので2で割ったあまりを見て場合分けするのが正しい解法だった．

二分探索

ABC155 D問題

二分探索して二分探索する問題． ある関数 $f$ は単調増加な関数であり，定義域はなんとか求まる． 定義域内で二分探索して $y$ が指定した値を超えるギリギリの $x$ を求める問題．

ただし，関数 $f$ の内部でも二分探索が必要．

combination

組み合わせを全列挙して全て探索する場合、再帰関数で組み合わせを作る。
たとえば，H個の玉の間に区切りを好きなだけ入れられるとき、 各隙間に区切りが(あるとき/ないとき)あって $(H-1)^2$ のパターンが作れる。
この場合，組み合わせを作成する再帰関数で組み合わせを作りつつ、最後の部分でその組み合わせの場合のスコアを計算し、返すように設計する。

ABC159 E問題

これはめちゃくちゃな計算量な気がするけどHが10以下という制約が付いているので解ける。

map

ABC160 D
mapの使い方わからんくてコンパイルエラー出しまくってた。最終的にvectorでやった。 read-onlyがどうとかでる。そのまま値をインクリメントはできない？
→ 簡単でした。mapの宣言を{} でやるか() でやるかで全然変わってくる。

longから数字の列に

vector<int> toarr(long v){
    // 0のときだけ例外的に 1桁
    if(v==0){
        vector<int> arr(1,0);
        return arr;
    }
 
    // 桁数を調べる
    int ketasuu = 0;
    long tmp = v;
    while(tmp!=0){
        tmp = tmp/10;
        ketasuu++;
    }
 
    // 1桁のとき1, 2桁のとき10, ... N桁のとき 10^(N-1)
    long divider = 1; for(int i=0;i<ketasuu-1;i++){ divider *= 10; }
 
    vector<int> arr(ketasuu,0);
    for(size_t i=0;i<arr.size();i++,divider/=10){
        arr[i] = (int) (v/divider%10);
    }
    return arr;
}

最初からstringで受け取るほうが良いのでは

floor(床関数)の計算における諸々

難しいことを考えず色々と例を試して法則を見つけてみればよかった。 前の問題が解けてなかったので5分で撤退 & 前の問題が解けると思って実装していたが方針が間違ってて解けず で冷えた。 わかる問題を的確に判別することが大切。

組み合わせにおける計算量の見積もり

nCr の計算をどれぐらいならやれるか？

計算可能。 だいたい 1000万以内とかであれば可能。これは900万なので怪しさある

組み合わせの列挙

バグらせずにできるようになりたい。

無駄に難しく考えてしまって実装ができないことが本当に多い。

テストケース使用ミス

前回のコンテストのテストケースを保存したファイルに上書きしてしまって一生テストケース通らないミスをやらかしがち。

対策:
先にD問題くらいまではテストケースのファイルを開いておく。 左paneはA,B,C,D,Eまで開いておいて、 右は上下に分けて右上pane:A1,..A4,B1,…B4とし、右下pane:C1,…C4,D1,…D4としておく。

過去に書いた自分のコードを参照する際などにやらかしが発生しがち。

内積から傾きを連想

ABC168E

二次元ベクトルが大量にあって、内積0になるペアが含まれないように部分集合を何個作れるか？

すべてのベクトルをまずただの傾き表記にする。 ハッシュで得られるようにして、90度でペアにできるものはそのうちひとつを選ぶみたいな？ ただし180度は内積0ではないからそれほど単純ではない。

modの計算

負になっていたら脳死で (hoge+mod)%mod するべき。 減算の処理でミスりがち。

累積和は最初に0あれ

ABC172C
累積和データを作るとき最初の部分に0を入れておかないと条件分岐が無限に増えて実装で死ぬ。