kmjp's blog

競技プログラミング参加記です

Google Code Jam 2017 Round 1A : C. Play the Dragon

一応シングルスレッド動作だけど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やるとなんとなく身に付くけど、一般的な知識なのかしら。