hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://www.hackerrank.com/contests/75th/challenges/i-want-to-be-a-high-achiever 前提知識 動的計画法 解説 重要なテクがあり、これが適用できれば、ACにだいぶ近づく。 「A[i]の平均がX以上 <=> A[i]-Xの総和が0以上」 平均を実際に求めようと思うと、総和と個数の2種類の情報が必要になるが、 このテクを使えば、総和だけを見ることで平均がX以上になるかを判定できる。 これで変数を1つ減らすことで間に合うDPを作成できる。 dp[i][tot] := i番目までの教科を処理済みで、X[i]-Xの合計がtot… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F03%2F21%2F192931" title="I want to be a high achiever [灘校75回生中学卒業記念コンテスト] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-03-21 19:29:31 rich https://blog.hamayanhamayan.com/entry/2020/03/21/192931 1.0 100%