立ち回り
問題考察
- 小規模な場合で実験してみる
- 考えた必要条件が十分条件にならないか？
- 0,1,2,...は0,1以上(あるない)にできないか？ (これ)
- 操作の前後で変わらないものはないか？
- 操作回数の上限が最悪ケースでの回数より遥かに大きくないか？ (これ)
- 逆操作を操作で表現できるか？
- 文字列の連続するn文字について操作するものはmodnで考える (これ)
- A xor B <= A + B
- 和の期待値 = 期待値の和
- 個々の要素が寄与する分を考える
- グリッド上の問題は行/列に対応する頂点を持ってきて二部グラフみたいにする、(i,j)は行iと列jに対応する頂点を結ぶ辺としてとらえる
- 操作の最適化は操作によって得られる状態の条件を考える
- 最小全域木でN^2辺ある設定の時、クラスカル(マトロイド)や分割統治的な方法で辺の数を削れないかを考える(両端を迂回して作る場合のほうがコストが小さくならないか？)
- 区間に対する操作は端点での変化を利用できないか？
- N以下の全てに対する総和を求めるとき、Nを固定してNのみについて考える
- 同一視して数え上げしたいとき、代表元の存在について気づけないか？
- オイラーグラフなら次数列の議論 これ
- ランダムウォークは x か y のどっちかを inc の後に何もしない or 両方 dec と同じ これ
実装
- 値が一定以上になるかを調べるdpでは一定以上になったらmin関数などを使ってオーバーフローを防ぐ
- 掛け算をFFTで行うとき、底をできるだけ大きくした方がいい(100とか1000とか)
- bool x,y に対して
x != yは ACLの two_sat でts.add_clause(x,true,y,true),ts.add_clause(x,false,y,false);としてx == yはts.add_clause(x,true,y,false),ts.add_clause(x,false,y,true);として実現できる mod2で値を割り当てたいとき使う - mod を取った値で 2 を割った「商」を求めたい時は mint を使ったり余りの可能性に気をつける
- DFSとかで手元で動かないときはスタックオーバーフローの可能性があるので
-Wl,-stack,10485760をつけてコンパイルしてみる
不正解になったとき
- オーバーフロー/配列外参照はないか？(intで二分探索するとき上限を2e9にするとオーバーフローすることがある)
- (REの場合)ゼロ除算をしていないか？
- (TLEの場合)定数倍と計算量のどっちでひっかかってるか
- 探索回数が少なすぎることはないか？
- A*B<CはA<C/Bとするとオーバーフローを避けれる
- 二分探索の境界は本当に正しいか？ngとした値で実は可能だったりしないか？
- mod 関係は TLE したら mint 使うか mod 取る回数を減らす
