一応シングルスレッド動作だけど3分かかるゴリ押しコードで通したので、洗練された解答を見たい方は公式Analysisを見た方がいいかと。
https://code.google.com/codejam/contest/5304486/dashboard#s=p2&a=2
問題
良いドラゴンと邪悪なナイトがターン制で戦う。
ドラゴンの体力と攻撃力はHd,Ad、ナイトの体力と攻撃力はHk,Akである。
ドラゴンは以下の行動のいずれかを取れる。
- 攻撃:相手の体力を自身の攻撃力分減らす
- バフ:自身の攻撃力をB加算
- デバフ:相手の攻撃力をD減算、ただし負にはならず0でとどまる
- 回復:自身の体力を初期値に戻す
ナイトは攻撃しかしてこない。
先に相手の体力を0以下にした方の勝ちである。
ドラゴンが最適手を取る場合、最短何ターンで相手を倒せるか。
解法
回数はおいておいて、最適な行動順はデバフ→バフ→攻撃の順である。
ただし、回復しないと相手ターンで負けるときだけ回復する。
まずバフ・攻撃の合計回数の最小値を求めよう。
これは三分探索でもよいが、与えるダメージがO(Ad + B*(Buff回数)^2)であることを考えるとバフ回数をO(√Hk/D)回程度総当たりしても問題ない。
Smallの場合、以後は自身の体力・相手の攻撃力・残り(バフ+攻撃回数)を状態としてDFS/メモ化再帰してもおそらく間に合う。
あとはデバフを1回ずつ行いながら、残りの自身の体力、相手の攻撃力に対し、回復以外に(バフ+攻撃)回数分のターンを迎えるのに何ターンかかるかを求めればよい。
以後デバフは行わないので、相手の攻撃力は固定であり回復するターンは周期的になるためO(1)でこれは計算できる。
以下の解法はデバフ回数をO(Hk)回頭悪く総当たりしている。
一応最近のCPUだとこれでも1ケース最悪5秒。幸い全ケースそんなにかかるわけではないので、シングルスレッドでも8分以内に提出できる。
ll HD,AD,HK,AK,B,D; ll calc(int H,int A,int L) { if(A==0) return L; int T=(H+(A-1))/A; if(L<=T) return L; int ret=T; L-=T-1; H=HD-A; if(H<=0) return 1LL<<32; T=(H+(A-1))/A; if(T==1) { if(L==1) return ret+1; else return 1LL<<32; } return ret + L + (L-T+(T-2))/(T-1); } void solve(int _loop) { int f,i,j,k,l,x,y; cin>>HD>>AD>>HK>>AK>>B>>D; ll mia=1LL<<31; FOR(i,1000000000) { ll at=AD+B*i; ll turn=i+(HK+(at-1))/at; mia=min(mia,turn); if(at>=HK || B==0) break; if(turn>mia) break; } ll ret=1LL<<32; ll turn=0; ll nh=HD; FOR(i,1000000000) { ret=min(ret,turn+calc(nh,AK,mia)); if(AK<=0 || D==0) break; if(nh<=AK-D) { nh=HD-AK; turn++; } AK=max(AK-D,0LL); nh-=AK; turn++; if(nh<=0) break; } if(ret>=1LL<<32) _P("Case #%d: IMPOSSIBLE\n",_loop); else _P("Case #%d: %d\n",_loop,ret); }
まとめ
デバフ→バフ→攻撃、が最適なのはRPGやるとなんとなく身に付くけど、一般的な知識なのかしら。