なんか操作を同一視できる量はないかという視点から考えたらワンチャン思いつく可能性が出てくる気がする そう考えると 0 1 2 1 2 0 2 0 1 から 0 1 2 を引くと mod3で 0 0 0 1 1 1 2 2 2 になって、同じ数字が３つ連続しているときは好きに変えられる また …

長方形の張り方としては上の２パターンみたいな感じに分類できる 最初に １ の置き場所を決める １ は、上に長方形を接地しないことにする。 上に長方形を接地するようなパターンが最適だとしたら、 右側に、上に長方形が設置されていない長方形があることに…

そのままSとTをコンボリューションすると下図のようになる 図１ 図２ 配列の４番目には、S[3]*T[1] + S[2]*T[2]*S[1]*T[3] 配列の５番目には、S[4]*T[1] + S[3]*T[2]*S[2]*T[3] 配列の６番目には、S[5]*T[1] + S[4]*T[2]*S[3]*T[3] が入っている これが仮に …

(k-1)個のボールを(a-1)回挿入する。挿入した後、ボールの合計がNより大きくなってはいけないので、N-(k-1)(a-1)からa個選ぶパターンを考える。それぞれのパターンで、(1, 2, ...a)番目のボールの内、(2,...a)番目のボールの添字にk-1を加算する。これは全部…

公式解説とか正解コードとかブログとかいっぱい見た dp[i]= i日目に必要なコンピュータを手に入れるまでに必要な最小の金額 というdpテーブルを作ることを考える dp[0] = 0にしておく dp[i] = min(dp[j]+B[i] | B[i] <= ( Σ(0~j)A[k] - dp[j]) ) 後ろを全部…

グラフDPをする dp[i][j] = (i=0 なら、jが所属している連結成分はaのみで出来ていて、それ以外の連結成分はaとbで出来ている i=1なら、jが所属している連結成分はbのみで〜〜〜 i=2なら、jが所属している連結成分はaとbから〜〜〜 今見ているノードがaの時…

実験してると、nが奇数だと先手は必ず負ける。 これは、nが奇数で先手が約数pを選ぶとと、n=p^x * q^y * r^z => n-p = p( p^(x-1) * q^y * r^z - 1 ) n-pは 奇数＊偶数 のかたちにかける。 後手は奇数を選べば 奇数（偶数 - 1 )を先手に渡せる。これは奇数。…

まずKeshiのグラフ上でオイラーツアーをして、出発した時間と帰ってきた時間を記録する これを使うと木の上で２つのノードが親子関係にあるかどうか調べられる [出発した時間, 帰ってきた時間]の区間が図１のような関係になっている時親子関係がある。 次にS…