====== AtCoder ====== * [[https://gist.github.com/rigibun/7905920|競技プログラミングでのC++]] * [[https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0|全てのテストケースはここに]] === 有用な外部サービス === * [[https://kenkoooo.com/atcoder/#/table/|AtCoder Problems]] : 問題の一覧 * [[https://atcoderapps.herokuapp.com/atcoderperformances/|AdCoder Performances]] : 各コンテストでのパフォーマンスをグラフ表示 * [[https://atcoder-scores.herokuapp.com|AtCoder Scores]] : 精進グラフ(重み付き解いた問題数とレートのグラフ)表示 === 精進 === * LeetCodeの Explore-> Featured -> Top Interview Questions を全て解く？ * LeetCodeのProblems (1368個ある)を全部解く？ * [[.:leetcode|LeetCode一言感想]] ===== AtCoderの仕様 ===== 書いたコードは''Main.cpp''として保存され，コンパイルされる． * 標準入出力の扱いについて再確認すること * 実行のされ方：コマンドライン引数ではなく標準入力から値を得る．標準出力へと値を返す． * インタラクティブ問題はscanfとprintを使う．\\ scanfで標準入力から値を取り出し，printfで標準入力へと書き出す．flushして標準出力をいい感じにしたら，標準入力へと新たな値がやってくる．これを繰り返してやる． 出題される問題は，必ずしもすべての状況に対応しなければいけないというわけでもないっぽい？\\ 当然か？標準入力がバグっている場合なども考慮しなくて良いし(あたりまえかも)，想定範囲内の入力であっても必ず正しい出力である必要があるわけでもない(テストケースさえクリアすれば良い)．そのためテストケースは公開されない．そもそも決められた制約内で解けない問題もあるが，確率的に最も良さそうな感じの出力が得られるコードを書けば良いという暗黙の取り決めのよう．\\ 例えばN回以内の操作でM個をソートしろという問題は$N<(M-1)M/2$なら解けないが，答えとして正しいであろう確率が最大となるようにすればそれが出題者側の想定した答え． 競プロ対策を一切していない通常のプログラマ(業務経験あり or 情報系大学生・大学院生)はABCのC問題までなら普通に解ける。 早解きの訓練をしていないはずなので(傾向や答え方，AtCoder特有のルールを知らないはずなので)茶色ぐらいのスコアに落ち着く． * 一般的なレベルは * 使用する言語の文法を知っている = (for文,if文が書けて標準入出力が扱える) * 配列や辞書などのデータ構造を扱える * バブルソートや再帰関数などがすぐに書ける * スタック・キューやリンクリスト、木構造を知っている * 早解きの訓練をすれば緑や青色のパフォーマンスがでる． D問題以降は有名なアルゴリズムを言われて直ぐ書ける用に訓練しておく必要がある． === ファイルから標準入力 === #include 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++データ構造再確認 ==== 普段書かない言語は直ぐに仕様を忘れるのでチートシートを作るべき * vectorの操作方法 * コンストラクタ * コピー * insert * erase * イテレータのさす場所が変わるのでbegin()やsize()を覚える * stringの操作方法 * length * queue ^ 構造 ^ 最初 ^ 終わり ^ 長さ ^ 参照 ^ | ''std::vector'' | ''.begin()'' | ''.end()'' | ''.size()'' | ''.at(i)'' | | ''std::string'' | ''.begin()'' | ''.end()'' | ''.size()'' or ''.length()'' | ''[i]'' | === vector === sizeは戻り値が ''size_t'' である．メモリ領域を変更しないで扱うときは size_t i=0;i 別の書き方として， vector::iterator i=arr.begin();i!=arr.end();i++ があるっぽい． ''auto''で''vector::iterator''を書くのをやめられる． 値の参照，代入には ''arr[i]'' と ''arr.at(i)'' がある． メモリ領域に変更があるばあいは後者でないと動かない． * 参考：[[https://qiita.com/ysuzuki19/items/df872d91c9c89cc31aee|C++のvectorまとめ]] * 参考：[[http://vivi.dyndns.org/tech/cpp/string.html|string]] vectorの初期化 // 1次元 vector arr(N, 0); // 2次元 vector< vector > DP(N, vector(M, 0)); // 3次元 vector< vector< vector > > DP(N, vector< vector >(M, vector(L,0))); === map === pythonでいうdict * include: \\ #include * 作成: keyの型とvalの型を指定。\\ 宣言が波括弧なのに注意！丸括弧では意味不明なコンパイルエラーが出る\\ std::map 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'' 存在する === pair === tupleの要素数が2のケース。 mapのキーとして利用できる。 標準の記号だけで作れるので書くのが楽。 map< pair, pair > data{}; data[{0,1}] = {0,0}; data[{0,1}] = { data[{0,1}].first+1, data[{0,1}].second }; 最初の記号には ''.first'' でアクセス。２つめの記号には ''.second'' でアクセス。 === tuple === pythonでいうtuple． 関数の戻り値を複数にするのにも使える． * include: \\#include std::tuple hoge(){ return std::forward_as_tuple(fuga, piyo); } int main(){ int a,b; std::tie(a,b) = hoge(); } mapのハッシュに使うときは以下のように ''make_tuple'' 関数を使うと楽。 std::tuple foo = std::make_tuple( hoge, fuga, piyo ); === queue === * empty() で存在確認 * front() で最初のやつを参照 * pop() で最初のやつを捨てる、戻り値は変なやつなので front() -> pop() で使うのが普通。 * push() で最後に追加。 queue q; q.push(i); long x = q.front(); q.pop(); ==== 便利関数について ==== === sort()でソートされる範囲(vectorの例) === | ''vector 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())'' で昇順になる．ソートは書かなくて良い． | * partition_point は二分探索？ === c++の標準入出力再確認 === cin,cout,endlなど これでファイルから入力できる. #include 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)$」 ===== 競技プログラミング特有のテクニック ===== ==== 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 での逆元を求めて利用する。逆元は以下の実装で求めることができる。 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) なぜそうなるのかの導出について書く。 * [[https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a|参考]] === その他 === [[https://noshi91.hatenablog.com/entry/2019/03/31/174006|ライブラリ化してくれている人]] もいる。 === 補足: 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} $$ * ABC153E 各サンプルの使用回数が0以上， ==== 桁DP ==== ある数 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 ^ 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 \}$ === 具体的な実装とイメージ === * 二分探索では Left と Right が隣り合ったとき( ''Right-Left=1'' )となったときに終了とする． * プログラム中で mid がある条件 c を満たすとき ''Left = mid'' ，満たさないとき ''Right = mid'' とするとLeftはcを満たすギリギリの値，Rightはcを満たさないギリギリの値となる． * 数え上げる際は，Left=init_leftのままでも問題ないか， Right=init_rightのままでも問題ないかを確認する． TODO) ABC162用のメモに詳しく書いておいたのでそれをこっちに書く {{:tips:atcoder:img_0038.jpeg?400|}} {{:tips:atcoder:img_0039.jpeg?400|}} {{:tips:atcoder:img_0040.jpeg?400|}} ''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 を参照 ==== union-find ==== グループを見つける． N人いて，PiとPjは友達であるという情報がM個与えられる． 友達の輪で繋がっているグループを探す． 愚直に Mのループ内でグループとグループを統合していくと重いっぽい？ 統合処理でNをループさせるのがいけないっぽい？ ルートへの参照をするよりも親の参照をするほうが速いのか？ * [[https://www.slideshare.net/chokudai/union-find-49066733|chokudai解説]] * やはりグループの統合処理にO(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 | つまり * 関係性の違う仕切りが $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)$ は自明である。 つまり、貪欲法で前から詰め込めるだけ詰めるとき、 あまった文字列については最小の回数で区切ることができ、詰め込めるだけ詰めるのを抑えめにするとき最小回数以上の区切り回数が必要となる。 複数レーンで考えるときも同様である。 ==== 連続整数からN個選ぶときの和の種類数 ==== 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$ の内部でも二分探索が必要． === combination === 組み合わせを全列挙して全て探索する場合、再帰関数で組み合わせを作る。\\ たとえば，H個の玉の間に区切りを好きなだけ入れられるとき、 各隙間に区切りが(あるとき/ないとき)あって $(H-1)^2$ のパターンが作れる。\\ この場合，組み合わせを作成する再帰関数で組み合わせを作りつつ、最後の部分でその組み合わせの場合のスコアを計算し、返すように設計する。 ABC159 E問題 これはめちゃくちゃな計算量な気がするけどHが10以下という制約が付いているので解ける。 === map === ABC160 D\\ mapの使い方わからんくてコンパイルエラー出しまくってた。最終的にvectorでやった。 read-onlyがどうとかでる。そのまま値をインクリメントはできない？\\ -> 簡単でした。mapの宣言を''{}'' でやるか''()'' でやるかで全然変わってくる。 === longから数字の列に === vector toarr(long v){ // 0のときだけ例外的に 1桁 if(v==0){ vector 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 arr(ketasuu,0); for(size_t i=0;i 最初からstringで受け取るほうが良いのでは === floor(床関数)の計算における諸々 === 難しいことを考えず色々と例を試して法則を見つけてみればよかった。 前の問題が解けてなかったので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ではないからそれほど単純ではない。 === modの計算 === 負になっていたら脳死で ''(hoge+mod)%mod'' するべき。 減算の処理でミスりがち。 === 累積和は最初に0あれ === ABC172C\\ 累積和データを作るとき最初の部分に0を入れておかないと条件分岐が無限に増えて実装で死ぬ。