SRM500台を埋めていくという話らしいです。500は書くのを忘れたので501から。
問題
nA回paramA / 1000を足すのとnB回paramB / 1000をかけるのを好きな順番でやって値を最大化する。
考察
サンプルをパッと見た感じで全部足してからかけるか、全部かけてから足すかという感じに見えた。かける値が負のときは偶数になるように調整するっていうのもサンプルにあるしまぁそれでやるかーって書いたら普通に通ってしまい拍子抜け。冷静に振り返るとひどく冗長なコードを書いてしまった。245.96 points。
DPでやるというのは頭に浮かばなかった。確かにこういう場合分けは抜けが怖いのでそれも候補として持っておくべきだった。
そして、あれ、他の人の記事などを読んで「paramBを1回だけかけて符号を調整する」という場合を考慮していなかったことに気づいたけど通ってしまっているなぁ。(nA, nB, paramA, paramB) = (1, 9, -10000, -100)みたいなのでダメですね。サンプルの弱さに救われているだけで本番これやったらハックされるやつだ。うーん、反省。
#include"bits/stdc++.h" using namespace std; using ll = long long; class FoxPlayingGame { public: double theMax(int nA, int nB, int paramA, int paramB) { double ans1 = 0; if (paramB < 0) { nB = nB / 2 * 2; } for (int i = 0; i < nA; i++) { ans1 += paramA / 1000.0; } for (int i = 0; i < nB; i++) { ans1 *= paramB / 1000.0; } double ans2 = 0; for (int i = 0; i < nB; i++) { ans2 *= paramB / 1000.0; } for (int i = 0; i < nA; i++) { ans2 += paramA / 1000.0; } return max(ans1, ans2); } };