はじめに
基本覚書です。読みやすさは保証しませんし、正確さも保証しません。
また、この記事を読んだことで競プロの実力が上がるなどといったことは一切ありません。
二分探索闇テクニック
相対誤差悪質利用編
AtCoderだと、こういう文章があります。「なお、想定解答との絶対誤差または相対誤差が10^-6 以下であれば正解として扱われる。」
つまり、答えが1の時は差が10^-6以下でないとだめだが、答えが10^6の時は誤差1まで許容されるということです。
そこで、こういうテクニックが使えます。
double ok=10^10, ng=0, mid;
double error=1e-7;
while(abs(ok-ng)>error){
mid=(ok+ng)/2;
if(check(mid)) ok=mid;
else {
ng=mid;
error=ng*1e-7; //これが大事
}
}
これは、答えの絶対値が必ずngより大になるから使えるテクです。ngが0より小さい場合にはもうちょい工夫しないと死にます。また、AtCoderの相対誤差が割と適当っぽいので、下手すると死にます。気を付けましょう。
運がよければ800msとか早くなります。
運が悪ければ（解が小さければ）ほぼ効果はありません。
例：https://atcoder.jp/contests/abc157/submissions/10472457 （ただしTLEはとれていません）
その二分探索、本当に必要？
二分探索は、尺取り法に置き換えることができる場合があります。
O(N log N)がO(N)になると流石にだいぶ早いです。
N=4000でも150msくらいは縮まります。
実装で頭が混乱する度合いが上がりますが、これでTLEが取れるのであれば試してみるのも手です。
例：https://atcoder.jp/contests/joisc2009/submissions/10944109
セグ木編
最大値を取るのが全体区間だけの場合
この場合、dat[0]を見るだけで十分なことがあります。
もしもこれで区間を渡すと、O(log N)で帰ってきますが、これをするとO(1)になります。
別の限界テクを使うこともできます。遅延セグ木を作るとき、遅延伝搬をする必要がなくなります。
evalという配列を作り、ここに区間全体に加算された値を持ちます。
int dat[200000],eval[200000];
void add(int i,int a,int b,int l,int r,int x){
if(r<=a||b<=l) return;
if(a<=l&&r<=b) {
eval[i]+=x;
return;
}
add(i*2+1,a,b,l,(l+r)/2,x);
add(i*2+2,a,b,(l+r)/2,r,x);
dat[i]=max(dat[i*2+1]+eval[i*2+1],dat[i*2+2]+eval[i*2+2]);
}//1-indexed
//最大値がdat[0]に入る。
こうすると、毎回伝搬をすることが無くなるので、だいぶ早くなります。
ただ、こんなことやってるくらいなら非再帰にする方が早くなります。多分。
例：https://atcoder.jp/contests/joisc2009/submissions/10944109
動的セグ木のメモリ使用量を少なくする一般的なテクニック
遅延セグ木を再帰で作っていると、eval関数とかで遅延評価をしないといけないのですが、これをしすぎると遅いです。また、動的セグ木でevalを呼びすぎるとメモリ使用量がかなり増えて、MLEがでます。
そこで、eval関数を呼び出さないように頑張ります。
そうすると、上手く行くケースだと20%くらいメモリ使用量が減少します。
実装例は省メモリも期待できる動的セグ木で、RAQ+RMQで書きます。
実装方法は、 遅延評価セグメント木をソラで書きたいあなたに を参考にしています。
struct Node{Node* left,right; int v,lazy;};//左、右、値、遅延する値（コンストラクタは省略）
void eval(Node* &node,int l,int r);//ここは良しなにやってください。
void add(Node* node,int a,int b,int l,int r,int x){
if(r<=a||b<=l) return;
eval(node,l,r); //ただ、この行を1行後ろにずらすためだけのテクです。
if(a<=l&&r<=b){
node->left->lazy+=x;eval(node,l,r);
return;
}//この行を①とする
if(!node->left) node->left=new Node();
if(!node->right) node->right=new Node();
add(node->left,a,b,l,(l+r)/2,x);
add(node->left,a,b,(l+r)/2,r,x);
//この行だけ変えている
node->v = max((node->left ? node->left->v + node->left->lazy : 0),
(node->right ? node->right->v + node->right->lazy : 0));
}
int query(Node* node,int a,int b,int l,int r);
//上っぽくやれば大丈夫です。queryは更新しないので、evalを①の行まで下すことができます。
ただずらしただけだとWAがでますが、最後の行のようにlazyを加算すると正しく動いてくれます。
これはすぐ思いつきそうですが、僕が思いつくのに10分くらいかかったので。
使用例：https://atcoder.jp/contests/joisc2011/submissions/10965976
pragma系
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
一番上は四則演算を早くする、2番目は計算を並列化する、3番目が条件分岐を減らす、4番目が浮動小数点数の演算を早くするpragmaらしいです。
これつけると若干早くなります。
#define int long long
これを外すと若干早くなりますが、結構な割合でWAを吐きます。
ライブラリにscanf依存していたりすると %lldで死ぬので、直す必要があります。
入力
cin,cout,endlは遅いので、scanf,printf,"\n"に置き換えましょう。
ただ、インタラクティブだとendl使わないと死ぬらしいです。
3/17追記 fflush()を使うとインタラクティブでも使えるらしいです。（きたむーさんから）
constexpr（これはゴミテクではない）
modとかの定数はconstexprにすると早くなるらしいです。これは結構効果が大きそうでした。
何故なのかは、コンパイル時によしなにしてくれるかららしいです。