- 競プロメモ
- 心得
- デバッグ
- Tips
- (特にmain内で)大きい2次元配列とか宣言するとスタックオーバーフロー起きがち
- べき乗はpow()，型変換に注意
- 2次元配列でx, y間違えないようにする
- string -> 数値の変換
- (bool) ? (process_1) : (process_2)
- 途中で成功条件満たして終わりたいときはexit(0)
- v.reserve() vs v.resize() vs constructor
- 連想コンテナ map / set
- 全頂点間の最短路 -> Warshall-FloydでO(V^3)
- 順列生成 -> next_permutation()
- きわっきわのoverflow -> 演算順序変えるのもあり
- lcm(a, b) = a * b / gcd(a, b)
- 2^k が絡む問題はbit演算使えると楽なこと多い
- bit全探索のやり方
- bit演算いろいろ
- 区間スケジューリング(端っこ(終わりも含む)から見てく貪欲はしばしば有効)
- N <= kで部分点の問題で部分点狙いに行くとき
- DPで情報足りないときは次元を1つ追加することを考える
- 2人で最適にとってくゲーム
- doubleの出力精度
- メモリ足りなくなる -> バケツソートかも?
- string(x, 'a')でaをx回反復した文字列
- 「最適な手数」といいつつどうやっても変わらないのもある
- 辺が最適経路に含まれるかどうかの判定
- 二部グラフあれこれ
- l以上r以下で条件を満たす数いくつあるか?とか -> 累積和
- 未解決な疑問
- まずは落ち着く
- 紙に書いて方針立ってから実装
- デバッグは以下(できるだけデバッガー使う)
- 制約とか添字の始まりとかルールをちゃんと読む
- 一定レベル以上の問題むやみに全探索しない．ちゃんと考えて解く．やり方決まってて計算にO(N)みたいなのけっこうある
- むやみにvector使わない．dpテーブルとか参照するだけのものなら大きめの配列宣言しといて必要なとこまで使えば良い．
- 配列の添字はできるだけ共通に使えるように書く
- 問題や操作を簡単に出来ないか考える(ABC085_Dとか)
- 最適にとり合ってくゲーム，O(1)解法も考える．片方が最大化，もう片方が最小化狙うゲームだと双対に考えたりできる(ABC078_D_ABSとか)
F5で実行
左側のウォッチ式で変数名入力してグローバル変数見る
- 添字0始まりか1始まりか
- 1, 2個のWA -> 極端なテストケース考える
- 変数に正しい値入ってるか確認
- 手計算でできるくらいの処理で確認
- intの範囲に(自分で置いたinfなど)おさまってる?(複数個のWAでありがち)
- とりあえずintをllにする
- 自分の手計算でわりあてたメモリ上限とか制約はあってる?超単純な計算でも見直す
- 二重に出力してない?(例外処理の return 0 忘れとか)
スタックオーバーフロー 関数 = サブルーチンではスタックを積んでいってそのたびにスタックメモリ領域を確保するので，必然と容量上限小さくなる． 解決策は
- staticをつけてstaticなローカル変数に(複数回呼び出す場合共用になってしまうので注意)
- グローバル変数にしてスタックオーバーフローなくす
- new, mallocでヒープ領域から動的にメモリ確保する
- vector使う(これはヒープからの確保と解法と勝手にやってくれる)
staticローカル変数とグローバル変数の違い:
どちらも静的でプログラムを通して保持されるものではあるが，スコープが違う．
// main関数内
int a[3002][3002];
// これでセグフォくらった
int** a = new int*[3002];
rep(i, 3002){
a[i] = new int[3002];
}
// こうやって真面目に確保すればいけた
グローバル変数で宣言すれば一番上の表現でも通る
^はbit演算子 pow()使うとなんか型がおかしくなってWAくらったりするので注意(ARC102_C)
// testpow1.cpp
ll N, K;
cin >> N >> K;
cout << pow((N/K), 1) << " " << pow((N/K), 2) << " " << pow((N/K), 3) << "\n";
(in) 200000 3
(out) 66666 4.44436e+09 2.96287e+14
floatの範囲で表示になってしまう
// testpow2.cpp
ll N, K;
cin >> N >> K;
cout << ll(pow((N/K), 1)) << " " << ll(pow((N/K), 2)) << " " << ll(pow((N/K), 3)) << "\n";
(in) 200000 3
(out) 66666 4444355556 296287407496296
表示できている
matrix[y][x] が正しい
stoi(string, int), stol(string long), stoll(string, ll)
これは if(bool) process_1; else process_2;
exit(0)でプログラム終了できる 成功してそれを出力すれば良い時は使える
- push_back関数などで要素を一つずつ挿入したい場合はreserve関数
- 添字アクセスにより任意の位置に要素を代入したい場合はresize関数 or vector( size_type size )コンストラクタ
- 特定の値を敷き詰めたい場合はresize関数+fill関数 or vector( size_type num, const TYPE &val )コンストラクタ
参考 http://d.hatena.ne.jp/ponkotuy/20111216/1324027752 https://qiita.com/amayaw9/items/6e55b91c28cdc8d32cf2
キーにより探索する 2分探索木で実装されているので要素アクセスがO(logN) map : キーと要素のペア abc091/b.cppを参照 set : 集合，ユニークな一要素自身をキーとしたコンテナ abc085/b.cppを参照
イテレータを使うときは itr->first，itr->secondでアクセスできる(ポインタなので)
for(auto i = m.begin(); i != m.end(); ++i){
cout << "key = " << m->first << ", value = " << m->second << "\n";
}
sort(v.begin(), v.end());
do{
//処理
}while(next_permutation(v.begin(), v.end()));
例 : abc070/c.cpp 答えが10^18(long long のギリギリ)におさまると保証されてるので割り算を先にやればいける
例 : TDPC_C_トーナメント
https://qiita.com/drken/items/7c6ff2#include<bits/stdc++.h> /* g++ -std=c++11 -Wall -g -fsanitize=undefined -D_GLIBCXX_DEBUG abc/abc117/c.cpp */ using namespace std; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define SZ(x) ((int)(x).size()) #define INF (1e16) typedef long long ll;
int main(){ cin.tie(0); ios::sync_with_stdio(false);//おまじないでcin, cout早くする int n, m; cin >> n >> m; vector x(m); rep(i, m){ cin >> x[i]; } if(n >= m){ cout << 0 << "\n"; return 0; }
sort(x.begin(), x.end());
vector<int> dist(m - 1);
rep(i, m - 1){
dist[i] = x[i + 1] - x[i];
}
sort(dist.begin(), dist.end());
ll ans = 0;
rep(i, m - n){
ans += dist[i];
}
cout << ans << "\n";
return 0;
}aa4d8fce1c9361
AND & OR | NOT ~ <- 注意(!じゃない) XOR ^
bit iのみ反転
bit ^= (1 << i);
端っこから終点をソートして貪欲 http://www.prefield.com/algorithm/misc/interval_scheduling.html 参考 : abc103/d.cpp
if(N > k) return 0;
すると採点が早くなる(完全解はとれない．確実にTLEする確信があるときならやると良い)
AGC030_Cの部分点を取るDPなら高橋くんがいま配列先頭のところにいるのかおしりのとこにいるのかを記録するために01の次元追加する．
初期の時点で単純な(O(1)とかの)必勝法がある場合(e.g. CADDi2018_D) DPで数が少ない方から計算していく場合(e.g. TDPC_B)など
cout << setprecision(a) << hoge << "\n";
でa桁精度の出力(doubleなら15が最大?)
e.g. ABC061_C
ARC063_C_「1次元リバーシ」とか
最適経路は1本ではないのでprevで保存してくの大変な場合もある．
Warshall-Floydなどで最適距離となっているdistを用いて
dist[s][t] == dist[s][i] + edge[i][j] + dist[j][t]
が成り立つ場合，i,j間をつなぐ辺は最適経路に含まれる．
- 木は二部グラフ
- 二部グラフ <-> 奇数長サイクルを含まない
- (そもそもサイクルのない連結グラフは木だから二部グラフ)
n以下でいくつ満たすかをDP的に全部最初に作っておいて，後からO(1)のクエリをかけていく
ceil(x) == floor(x)
整数変換の話なのか?