この解法 TLE すると思ってたので「は？」と言わざるを得ない。 問題 3046 -- Ant Counting 解法 dp[n][t] = (n 種類目まで見ている時点で, セットの大きさが t 以下になるような集合の数)とします。 すると, dp[n][t] は, n 種類目まででセットの大きさが t…

今では典型ですね。 問題 3280 -- Cheapest Palindrome 解法 典型なので略。 const int INF = 1e9; int dp[2020][2020]; int cost[26][2]; string s; int dfs(int l, int r) { if (l >= r) return 0; int& ret = dp[l][r]; if (ret != -1) return ret; ret =…

dp の練習で蟻本のやつを解いてみました。これは簡単。 問題 3616 -- Milking Time 解法 まずスタートの時間ごとにソートする。dp[m] = (m 番目から最後までの milking time だけで最大化しようとした場合の最大値)として, 適当に dp する。 struct Milk { i…

満点解法書いてみてなんとなく理解したので書きます。ソースコードは解説コードに少し説明を加えただけです。 問題 G: おおきなかずを作った (I made a huge number) - 技術室奥プログラミングコンテスト | AtCoder 解法 基本的な方針は以前書いたものと変わ…

SRM 665 に参加しました。今回は 0 完でしたが運良く unrated になった(なりそう)のでレート下降は避けられそうです。前にも今回のような感じで「全探索してもギリギリいけそうなきがするけどダメな制約」的な問題があったような気がするんですが, また引っ…