解法 greedy 左端をflipするかの2通りを試す 位置iが1である場合、iをひっくり返すにはi, i + 1, i + 2をひっくり返す必要があるのでgreedyにやる別解 反転パターンを全探索。bit + 無駄な探索しない高速化をしないとTLEする ソースコード greedy int main()…

解法 月の出費の上限で二分探索 ソースコード int n, m; int money[ten(5) + 100]; bool ok(int month_spend) { int months = 1, spend = 0; rep(i, n) { if (spend + money[i] > month_spend) { ++months; spend = 0; } spend += money[i]; } return months …

問題の意味がなかなかわからなかった 問題概要 ノード数nのDAGが与えられる。入力次数が0のノードからnへのパスを全て列挙する。各辺ごとにいくつのパスに含まれているかを数えたとき、最大のパス数はいくつか。 解法 辺i -> jを含むパス数は、(入力次数0の…

解法 区間dp dp[i][j] = [i, j)をpalindromeにする最小コスト ソースコード int main() { int m, n; string s; cin >> n >> m >> s; const int inf = ten(8); int cost[256]; fill(cost, cost + 256, inf); while (n--) { char c; int add, del; cin >> c >>…