8/5(日) 21:00-22:40
古アイスランド語勉強会の後に参加。
D(計算が合わなくて後回し)→C→B→A→D(再訪)、で4完
Dからやって計算合わないとめっちゃ焦る。
D - We Love ABC
DPでいいと思うんだけど
(Aまで来た数、ABまで来た数、ABCまで来た数)
サンプルケース3の計算合わない…
(一旦後回し)
あ
A(あるいは?)が来たとき、そのインクリメントは1ではなくて3^n (nはそれまでに出た?の数)だ
(Aまで来てない数、という項目を設けて利用すればよい)
そこだけ修正して
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2958129
C - All Green
ボーナスの取り方全2^D(≦1024)通り試す方向で
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2956917
おまけ
ボーナス得点の累計に高速ゼータ変換を使って書いてみたやつ
// 略 int solve(int D,int G,vi& p,vi& c) { int P = 1 << D; vector<int> bonus(P, 0), bonus_k(P, 0); for (int i=0,b=1; i<D; ++i,b<<=1) { bonus[b] = (i+1)*100 * p[i] + c[i]; bonus_k[b] = p[i]; } // zeta for (int i=0,b=1; i<D; ++i,b<<=1) { for (int j=0; j<P; ++j) { if (j & b) bonus[j] += bonus[j ^ b]; if (j & b) bonus_k[j] += bonus_k[j ^ b]; // ← if (j & b) を2回やってるのは行ごとコピペしたから } } int best = INT_MAX; for (int j=0; j<P; ++j) { int rest = G - bonus[j], bk = bonus_k[j]; if (rest <= 0) { best = min(best, bk); } else { for (int i=D-1,b=1<<(D-1); i>=0; --i,b>>=1) { if (!(j & b)) { int u = (i+1)*100, k = max(0, (rest+u-1)/u); if (k <= p[i]) { best = min(best, bk+k); } } } } } return best; }
B - AcCepted
pythonで
ちょっと面倒くさかったけど
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2957432
A - Rated for Me
pythonで
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2957524