atcoder.jp 期待値DPの問題 難しかったので、要復習としてメモ． 実装は以下の記事を参考にほぼ写経させていただきました． www.hamayanhamayan.com qiita.com 実装 #include <bits/stdc++.h> using namespace std; #define rep(i, m, n) for (int i = (int)(m); i < (int)(</bits/stdc++.h>…

codeforces.com DPに関して学びになる問題だったので、メモとして残す． 漸化式 dp[i] := s[i]まででn or uが連続する区間においていたずらできる回数 この問題で漸化式を上記の様に定義すると、dpテーブルの遷移はフィボナッチ数列と同じになることに気付く…

atcoder.jp DPについて学びになる問題だったので、メモとして残す． 考えたこと DPで解く 実装 参考にさせていただいた実装 考えたこと 最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけ…