差分

このページの2つのバージョン間の差分を表示します。

--- tips:atcoder:start [2020/05/18 14:36] – [mod] yuuho
+++ tips:atcoder:start [2020/09/13 11:36] (現在) – [c++データ構造再確認] yuuho
@@ 行 3: / 行 3: @@
   * [[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]] : 精進グラフ(重み付き解いた問題数とレートのグラフ)表示
 === 精進 ===
@@ 行 50: / 行 55: @@
 ==== 数値最大値 ====
 AtCoderでは Linux x86_64 を使っているので int 32bit, long 64bit, long long 64bit である。
-^ 型 ^ 最大値 ^
+^ 型 ^ 最大値 ^ 値 ^
-| int | 21億 = $2 \times 10^5$ |
+| int | 21億 = $2 \times 10^9$ |  ''2,147,483,647'' |
-| long = long long | 922京 = $9 \times 10^{18}$ |
+| long = long long | 922京 = $9 \times 10^{18}$ |  ''9,223,372,036,854,775,807'' |
 最大値/最小値は基本的にベタ書きが良さげ。わかりやすいので。
@@ 行 98: / 行 103: @@
 vectorの初期化
 <code c++>
+// 1次元
+vector<int> arr(N, 0);
 // 2次元
 vector< vector<int> > DP(N, vector<int>(M, 0));
@@ 行 114: / 行 122: @@
   * for文: secondとfirstでアクセス．\\ <code c++>for(auto itr = kosuu.begin(); itr != kosuu.end(); ++itr){
-        key = itr->first;
+    key = itr->first;
-        value = itr->second;</code>
+    value = itr->second;
+}
+</code>
 valはmutable? atと[]はどう違う？ 舐めるとどうなる？ 舐めたときどんな順番になっている？
@@ 行 126: / 行 136: @@
 === pair ===
-tupleの要素数が2のケース。使わなくても良いので解説しない。
+tupleの要素数が2のケース。
+mapのキーとして利用できる。
+標準の記号だけで作れるので書くのが楽。
+<code c++>
+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   };
+</code>
+最初の記号には ''.first'' でアクセス。２つめの記号には ''.second'' でアクセス。
 === tuple ===
@@ 行 157: / 行 177: @@
   * push() で最後に追加。
+<code c++>
+queue<long> q;
+q.push(i);
+long x = q.front(); q.pop();
+</code>
 ==== 便利関数について ====
@@ 行 254: / 行 279: @@
 ^ 通常 ^ modバージョン ^
 | 和 ''A=B+C'' | ''A = ( (B % mod) + (C % mod) ) % 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'' |
@@ 行 284: / 行 309: @@
 最大公約数、最小公倍数が必要な場面がかなり多いので覚えておく。
-<code>
+<code c++>
 long gcd(long a, long b){
     if(a < b) return gcd(b, a);
@@ 行 370: / 行 395: @@
 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 ====
@@ 行 581: / 行 627: @@
 ハッシュで得られるようにして、90度でペアにできるものはそのうちひとつを選ぶみたいな？
 ただし180度は内積0ではないからそれほど単純ではない。
+=== modの計算 ===
+負になっていたら脳死で ''(hoge+mod)%mod'' するべき。
+減算の処理でミスりがち。
+=== 累積和は最初に0あれ ===
+ABC172C\\
+累積和データを作るとき最初の部分に0を入れておかないと条件分岐が無限に増えて実装で死ぬ。