E - Union

Quiz

https://atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e

Submit

https://atcoder.jp/contests/code-thanks-festival-2018-open/submissions/4722141

解法

  • dp[i][j]
  • 整数 i まで見て、iがj個余る場合の数

  • dp[2][3]
  • 222を作るにはどんなパターンがあるか?書いた整数が、
    • 222
    • 11 + 22
    • 1111 + 2
    • 111111 + なし
    • 11111111 + なし
    • ...

dpのサイズ

  • iはN=300で縛られる
  • jは下からの繰り上がりもあるので300は確実に超える。indexを2倍する箇所もあるので余裕をもたせる
  • dp[300][2000]

DP

  • 二次元DPだけど3重ループ
  • 下からかき集める感じ