• 競技プログラミングでのC++
• 全てのテストケースはここに

• AtCoder Problems : 問題の一覧
• AdCoder Performances : 各コンテストでのパフォーマンスをグラフ表示
• AtCoder Scores : 精進グラフ(重み付き解いた問題数とレートのグラフ)表示

• LeetCodeの Explore→ Featured → Top Interview Questions を全て解く？
• LeetCodeのProblems (1368個ある)を全部解く？
  • LeetCode一言感想

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

• 標準入出力の扱いについて再確認すること
• 実行のされ方：コマンドライン引数ではなく標準入力から値を得る．標準出力へと値を返す．
• インタラクティブ問題はscanfとprintを使う．
  scanfで標準入力から値を取り出し，printfで標準入力へと書き出す．flushして標準出力をいい感じにしたら，標準入力へと新たな値がやってくる．これを繰り返してやる．

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

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

• 一般的なレベルは
  • 使用する言語の文法を知っている = (for文,if文が書けて標準入出力が扱える)
  • 配列や辞書などのデータ構造を扱える
  • バブルソートや再帰関数などがすぐに書ける
  • スタック・キューやリンクリスト、木構造を知っている

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

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

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

cat hoge.txt | ./a.out

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

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

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

PIはベタ書きが良さげ

const double PI=3.14159265358979323846;

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

• vectorの操作方法
  • コンストラクタ
  • コピー
  • insert
  • erase
  • イテレータのさす場所が変わるのでbegin()やsize()を覚える
• stringの操作方法
  • length
• queue

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) がある． メモリ領域に変更があるばあいは後者でないと動かない．

• 参考：C++のvectorまとめ
• 参考：string

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)));

pythonでいうdict

• include:
  

  #include <map>

• 作成: keyの型とvalの型を指定。
  宣言が波括弧なのに注意！丸括弧では意味不明なコンパイルエラーが出る
  

  std::map<std::string, int> dict{};

• 挿入: 無いkeyは自動で追加してくれる
  

  dict["hoge"] = 7

• for文: secondとfirstでアクセス．
  

  for(auto itr = kosuu.begin(); itr != kosuu.end(); ++itr){
      key = itr->first;
      value = itr->second;
  }

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

キーの存在判定

• m.find(key)==m.end() 存在しない
• m.find(key)!=m.end() 存在する
• m.count(key)==0 存在しない
• m.count(key)==1 存在する

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 でアクセス。

pythonでいうtuple．

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

• include: \\

  #include <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 );

• empty() で存在確認
• front() で最初のやつを参照
• pop() で最初のやつを捨てる、戻り値は変なやつなので front() → pop() で使うのが普通。
• push() で最後に追加。

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

• partition_point は二分探索？

cin,cout,endlなど

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

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

• mac/ubuntuでは g++ a.cpp のようにしてコンパイルする．
  • apt install build-essential

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

例

• 11を法として3の逆元は4である。
  • $3\times 4=12 \equiv 1 ({\rm mod} 11)$
  • ただし、逆源としてありうるのは -18, -7, 4, 15, 26, など数多く存在することに注意

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

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

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

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

• ある正の整数Xがあって、$X\times 10 \equiv 0 ({\rm mod} 2019)$ だったならば $X\equiv 0 ({\rm mod} 2019)$
  • 40359810 が 2019 の倍数なので 4035981 は2019の倍数
• ある正の整数Xがあって、$X\times 10 \equiv 0 ({\rm mod} 2020)$ であったとしても $X\equiv 0 ({\rm mod} 2020)$ とは限らない
  • 40383840 は 2020の倍数だけど 4038384 は 2020の倍数ではない

つまり

• 2019法
  • 真) 「$X \equiv 0 ({\rm mod} 2019)$」 ⇒ 「$10X\equiv 0 ({\rm mod} 2019)$」∧「$10X\equiv 0 ({\rm mod} 10)$」
  • 真) 「$10X\equiv 0 ({\rm mod} 2019)$」∧「$10X\equiv 0 ({\rm mod} 10)$」⇒ 「$X \equiv 0 ({\rm mod} 2019)$」
• 2020法
  • 真) 「$X \equiv 0 ({\rm mod} 2020)$」 ⇒ 「$10X\equiv 0 ({\rm mod} 2020)$」∧「$10X\equiv 0 ({\rm mod} 10)$」
  • 偽) 「$10X\equiv 0 ({\rm mod} 2020)$」∧「$10X\equiv 0 ({\rm mod} 10)$」⇒ 「$X \equiv 0 ({\rm mod} 2020)$」

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

• 非常に大きな数について計算しなければならない状況での速いプログラムが書けるか
• 正確にプログラムが書けるか

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

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

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

商の計算だけ 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) なぜそうなるのかの導出について書く。

• 参考

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

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

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を求める問題．

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

• ABC153E 各サンプルの使用回数が0以上，

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

• Nを上の桁から0桁目, 1桁目と走査していく．桁番号を行インデックスとする．
• N以下の数となりうるパターンの数の中で数えていく．N以下であることが確定/未確定の判定を列インデックスとする．
  • Nが34259だったとするとdp[0][確定]は0XXXX,1XXXX,2XXXXの3つ．dp[0][未確定]は3XXXXの1つ．4XXXX以降はN以下になりえないので数えない．
• 状態を深度インデックスとする．
  • 「数のいずれかの桁に3が含まれる」であれば「ある/ない」の2状態
  • 「数のいずれかの桁に3がちょうど1つ含まれる」であれば「0/1/2以上」の3状態

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

• DP[今見ている桁ID][N以下なのが確定/未確定][状態]

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

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

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

• 条件を満たすものの個数を出力する関数

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

K=4

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

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

• 二分探索では Left と Right が隣り合ったとき( Right-Left=1 )となったときに終了とする．
• プログラム中で mid がある条件 c を満たすとき Left = mid ，満たさないとき Right = mid とするとLeftはcを満たすギリギリの値，Rightはcを満たさないギリギリの値となる．
• 数え上げる際は，Left=init_leftのままでも問題ないか， Right=init_rightのままでも問題ないかを確認する．

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

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

• L==M としたら
  • Lは未満または同じ値
  • Rは大きい
• R==M としたら
  • Lは未満
  • Rは大きいまたは同じ値

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

• 出力が t 以上となる x の値が欲しいときは R==M で収束後 R を参照
• 出力が t より大きくなる x の値が欲しいときは L==M で収束後 R を参照
• 出力が t 以下となる x の値が欲しいときは L==M で収束後 L を参照
• 出力が t 未満となる x の値が欲しいときは R==M で収束後 L を参照

グループを見つける．

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

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

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

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

• chokudai解説
  • やはりグループの統合処理にO(n)かかるのがまずいっぽい

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

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

• 区間の最初と区間の前の関係性が変化する
• 区間の最後と区間の後の関係性が変化する

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

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

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

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

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

つまり

• 関係性の違う仕切りが $N$ 個あるとき、 $\lceil N/2 \rceil$ 回の操作で数列中の値を同じ値にすることができる。
• 初期条件で両端が同じ値なら収束する値はその値になる。(したがって両端が1なら0にしたいときは $+1$ 回操作が必要)
• 初期条件で両端が違う値なら好きな値に収束させることができる。

【命題】 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)$ は自明である。 つまり、貪欲法で前から詰め込めるだけ詰めるとき、 あまった文字列については最小の回数で区切ることができ、詰め込めるだけ詰めるのを抑えめにするとき最小回数以上の区切り回数が必要となる。

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

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

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

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

ABC163Dより

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

• ABC165C
• ABC167C bit全探索でやるべき。深さ優先再帰のコードを書いたので参照。TODO)

ABC154 D問題

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

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

ABC155 D問題

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

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

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

ABC159 E問題

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

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

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で受け取るほうが良いのでは

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

• ABC165D

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

• ABC165C: 全ての数列のパターンを求めて計算する方法ができる。 20C10 * 50 = 9,237,800

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

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

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

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

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

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

ABC168E

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

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

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

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