ちょっとした解き方メモ色々

今まで見た問題の
SRM 300〜SRM 400 くらいのコメント部分から、適当にメモを見て、適当に書きだしてみる。
非常に雑多。

行列累乗

最後にベクターを掛けるのを、結合律によって先に掛けちゃえる、ということ。
v*A*B*C*... = v*(A*B*C*...)
ベクターをv[N]として、マトリクスをM[N][N]とすれば、v*Mは、v[i]*M[i][h]をv'[j]に足し込む感じ。

メモ化再帰＋経路復元

int rec(int x, int y, bool flag)
関数にフラグを持たせる。
フラグがtrueのときはメモを見ない。
再帰する場合はflagをfalseにする。
最適値の遷移を覚えておく。
辞書順最小なら、最適な遷移のうち最小のものを覚えておく。
そして、その遷移をグローバルなバッファに書き込む。
最後に、flagをtrueにして覚えておいた遷移で遷移して、
これを呼ぶ側は、flagをtrueにして呼ぶか、flagをfalseにして呼んだ後もう一度flagをtrueにして呼ぶと良い(後者の場合、最適かどうか？にその状態でのメモを用いることが出来る)
辞書順greedyの一部も同じような形で出来る。

//ナップサック
int dp[55][11111];
vector<int> buf;
int rec(int i, int sum, bool f) {
  if(sum > K) return -INF;
  if(i == n) return 0;
  if(!f && dp[i][sum] != -1) return dp[i][sum];
  int r = -INF;
  rep(j, 2) {
    r = max(r, j*p[i] + rec(i+1, sum+w[i], false));  //再帰のflagはfalseを忘れずに
    if(f && r == dp[i][sum]) {
      if(j) buf.push_back(i);  //バッファに書き込む
      return rec(i+1, sum+w[i], true);  //この時の引数に注意。引数が複雑なら一時変数に置いておこう
    }
  }
  return dp[i][sum] = r;
}
vector<int> knapsack(/* (入力略) */) {
  //(入力略)
  memset(dp, -1, sizeof dp);
  rec(0, 0, false);  //一回呼ぶ
  buf.clear();
  rec(0, 0, true);  //もう一回呼ぶ
  return buf;
}

スパースなら枝狩りできそう

値の取る感じ、スパース(薄い)場合、枝狩りできそう

木のDP

DAGの無向版なので、方向をどうにかして(簡単には(頂点, 親))持てばDPしやすい

収束するまで回すやつ

dpしたいけど状態がループになったりする時。
期待値などで、どんどん再帰の値に関する全体から見た倍率が少なくなっていくことは多い。
この時、何回回したか？をトポロジカル順序として、N回適当に回せば収束してる、というふうにできる。
ただし何回くらい回せばいいかを確認すること。計算量も考えながら。わからなくて、他のやりかたもわからないなら時間ギリギリにすること。ただし非正規化数は重いことに注意。
この時、何回回したか？に関しては、メモリを節約して、カレントとネクストだけを持ってswapしてやるやつでやれば良い。

回文

• 半分だけ生成する

最後が重なるやつと重ならないやつがあるが、それぞれ長さに対して一意であること(lengthが偶数<->重ならないやつ・奇数<->重なる)に注意

• 両端から狭めてく

範囲DPとかでできることがある。
単一の文字もしくは空文字で終了する

強連結成分分解(SCC)

(V,E)に対するSCCの集合をSとした時、
∀v u∈S, (v, u)∈E' <-> (∃(v'∈v) (u'∈u), (v', u')∈E) とすれば(S, E')でまたグラフができる。
これはDAG。
「頂点を複数選んで、全ての頂点がその頂点のどれかから到達できるようにする」というのは、このSCC後のDAGの根に対する集合の中のどれかに置く、というふうになる。

次数2以下ならマッチングはDPで。

線の形になっている場合・円の形になっている場合・孤立点
が考えられる。
円の形になっている場合、適当に順番を付け、
最初の点を使うかどうか？(<->最後の点を使えないかどうか)の二通り試せば良い。

(∀x, P(x)) <-> ¬(∃x, ¬P(x))

「どんなのでもPが成り立つ」<->「Pの否定が成り立つものは存在しない」ということ。
例えば、"SRM 301 DIV1 Medium EscapingJail"で(もっと単純に考えられるかもしれないが、考え方として)、
「どんなパスを通っても距離がx以上」という条件を
「距離がx未満であるパスは存在しない」と言い換えられる。
そして、これを満たす最大のxはその頂点間の最短距離である。
これは単純な言い換えであるが、考え方として良いと思う。
「どこを通っても」とか「全ての」などが難しい時、こう考えてみるのはいいだろう。

桁DPで

リーディングゼロが終わったか？のフラグに対して、リーディングゼロ中はゼロのみをできる、というふうにすると、長さを別に用意しなくてよく、綺麗になる