atcoder.jp 結構雰囲気で解いてしまった。 まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQue…

atcoder.jp 表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0 dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1 dp[N][S]が1であればYes、そうでないならNo。 ま…

atcoder.jp UnionFindだろうと思ったが、ACLの使い方の理解が浅かったので、BFSで解いてしまった。 void solve(long long N, long long M, std::vector<long long> u, std::vector<long long> v){ vvl G(N+9); REP(i, M) { G[u[i]].push_back(v[i]); G[v[i]].push_back(v[i]); } vb</long></long>…

atcoder.jp 再帰的なDFS。 パッと書けるようにしたい。 void dfs(string S, ll n) { if (n==0) { cout << S << endl; return; } REP(i, 3) { S.push_back('a'+i); dfs(S, n-1); S.pop_back(); } } void solve(long long N){ dfs("", N); }