問題 TopCoder Statistics - Problem Statement 解法 さっきと同じように dp を考えます。dp[n][s] = (長さ n の数列で, スコアの合計が s であるようなものの数) という dp が自然な気がしますが, 今回の dp では最小要素がどこにあるのか, という情報も必…

問題 TopCoder Statistics - Problem Statement 解法 cartesian tree で注目すべき特徴は, ・数列の最小の要素が cartesian tree の一番上に来る ・最小の要素を中心に, 数列は左側と右側に分かれる ・で, 左側と右側でまた cartesian tree が出来るというこ…

問題 TopCoder Statistics - Problem Statement 解法 まず, あつまるべき座標を決定した際にそれぞれのアヒルはどのように動かすのが最適かを考えてみましょう。各行にはたかだか 1 匹のアヒルしかいないので, ある一列にアヒルを揃える際は, (a, c), (a+1, …

問題 No.307 最近色塗る問題多くない？ - yukicoder 解法 すべての盤面が一色になるまでは各クエリごとに幅優先探索をして愚直に色を変えていき, すべての盤面が一色になったら各クエリごとに全体の色が変わることを O(1) で記憶しておけば良いです。計算量…