EDPCを3周して掴んできた勘所

後半のT以降はまだ1回も解けてないのですが、Sまでは3周したのでメモです。

ひたすら「メモ化再帰」と思い込む

いきなりdpの配列を想像すると脳がパンクするので、まずはメモ化再帰を書いてみてください。メモ化再帰から始める利点としては以下が挙げられます。

• 求めたい値がわかる
• ループ方向がわかる

たとえばEDPCのFrog 2ですが、以下のようなdfsが考えられます(※ネタバレ注意)。

int dfs(int n) {
  // 今足場n+1にいる
  if (n == N-1) return 0; // ゴールにいるなら当然コストは0
  if (dp[n] != -1) return dp[n]; // メモがあれば使う
  int ans = INF;
  rep(i, K) {
    if (n+i+1 >= N)
      break;
    ans = min(ans, abs(h[n] - h[n+i+1]) + dfs(n+i+1));
  }
  return dp[n] = ans;
}

求めたい値はdp[0]？dp[N]？

このdfsは「足場n+1からNまでにかかるコスト」を求めています。そのため求める答えはdfs(0)です。さらに言えばこれはdp[0]の値でもあります。

dpを配列でいきなり書こうとすると「あれ？求める答えってdp[0]？dp[N]？それともdp[N-1]？」と混乱してしまいますが、「これはメモ化再帰なんだ」と思い込めばdp[0] = dfs(0)と分かるので混乱が起きにくいです。

逆に言えば、dfs(n) != dp[n]となるようなdpの設計は基本的には避けたほうが良いです。ひたすらdpは部分問題の解を表すように気をつける、これだけでも大分書きやすくなるはずです。

ループの方向がわかる

徐々にdpになれて来ても、forを逆順で回すか順に回すかわからなくなることがあります(これは添字の設計にも関わります)。しかし、一度dfsを頭のなかでイメージすれば、「どこが真っ先に計算されるか？」がわかります。上の例ではdfs(0)の計算 dfs(1)、dfs(2)…dfs(K)が計算されたあとにされます。そのため、上のdfsをforループで書く場合は添字が大きいほうから埋まっていくように書けば良いとわかります。

ちなみに、添字が小さいほうからループを回したいときはdfsの引数を「あとn個段差がある」としてやれば良いです。この場合は求める答えがdfs(N)となります。

小手先のテクがわかってないと解けないことがある

dpには累積和を使うことでO(N³)がO(N²)になるといった方法があります。しかし、これは知っていないとなかなか出てきません。結局EDPCを何度もやるなど、量をこなさなければこういった知見は身につきません。

また、bitDPは比較的有名でも、それを使ってグループ分けができることなどは一度考察したことがないとなかなか発想として出てこないです。

結論

こんな記事を読んだところで結局はEDPCやらないと勘所を掴めないよ