ABC104 参加記

B問題 AcCepted

問題

B - AcCepted

解法

やるだけ.僕はやれないので2WA(つらい

C問題 All Green

問題

C - All Green

解法

まず,すべての得点は100の倍数なので,すべて100で割って考えても問題ない.
dp[i][j]=(i\times 100点まで解いてスコアj)
とすると,
dp[i+1][j+k]=min(dp[i+1][j+k*i],dp[i][j]+k) (0 \leq k \leq p_i)
dp[i+1][j+p_i]=min(dp[i+1][j+p_i*i+c_i],dp[i][j]+k)
という遷移が可能.G点以上であれば何点でもいいのでj+kmin(G,j+k)のようにするとスマートに書ける.
計算量はO(DG max\{p_i\})で,問題ない.
ちなみに1\leq D\leq 10なので,各得点についてボーナスを取るかどうか全探索し,残りを貪欲に取ることでも解けるらしい

D問題 We Love ABC

解法

「3段階のものは真ん中を基準に考えると良い事がある」というのはたまに出る.(ex. Snuke Festival
C - Snuke Festival)
この問題でも,Bを決めるとそれを含むABC列の個数は(左にあるAの個数)\times (右にあるCの個数)になる.
ということで,左から見ていってそこまでにAが何個あるか数える方法を考える.試しに???について書き出していくと,f:id:SugarDragon5:20180805234852p:plain
こんな感じになるので,dp_i=(左にあるAの個数)とすると,
dp_i=\left\{\begin{array}{l}
dp_{i-1}+3^x (s_i=A)\\
dp_{i-1} (s_i=B,C)\\
dp_{i-1}*3+3^x (s_i=?)
\end{array}\right.
のようになる.これをCについても行えばよい.
計算量はO(N)で問題ない.

結果

72分2ペナ全完135位
f:id:SugarDragon5:20180805235906p:plain