記事一覧
ABC 139 E - League【Python】
問題はこちら。 愚直にシミュレーション。PyPyでもだめだったのでC++で通した。想定解法はグラフの最長パスを使うらしいが賢すぎて思いつかない。 #include <bits/stdc++…
固定された記事
AtCoder Beginners Contest 159 F - Knapsack for All Segment【Python】
問題はこちら。 公式解説と少し違った。「f(L, R, j) = 各項が L 以上 R 以下の単調増加数列 x_1, x_2, ..., x_kを用いて A[x_1] +A[x_2] + ... + A[x_k] = j とする方法の総数」と定義しておく。 dp[i][j] = f(0, i, j) + f(1, i, j) + f(2, i, j) + ... f(i, i, j) とすると答えは dp[0][S] + dp[1][S] + ... + dp[N -