かなり簡単な回だったのでたいして順位は良くなかったけれど、これくらいで全完できれば自分としては満足。
コンテストへのリンク
A - Serval vs Monster
H/Aの小数点以下繰り上げ。
Pythonなら、-(-H//A)と書くのが簡単。
B - Common Raccoon vs Monster
Hとsum(A)を比較
C - Fennec vs Monster
大きい順にsortし、K番目以降の和
D - Caracal vs Monster
まず、「何回分裂するか」が分かれば攻撃の回数は分かるということが重要。たとえば、二回分裂した後、三回目の攻撃で消滅するなら、答えは、1+2+4回です。
その上で、たとえば、H=12のときのHPの変化を考えると、
・12→6→3→1→0
これは、H=4のときの、
・8→4→2→1→0
と同じ。
なので、$2^k\leqq x\leqq 2^{k+1}$の範囲にあるxは同じ挙動をすることが分かります。
E - Crested Ibis vs Monster
あるHPの敵を倒すのに必要な魔力、でDPすれば解けます。
「効率の良い魔法を使うのが良いのでは？」などと考えたくなりますが、DPすれば全部の場合を調べられます。
F - Silver Fox vs Monster
左から貪欲でOK。
一番左の敵を倒す際にできるだけ他の敵も巻き込みたいので、一番左の敵の位置+Dの位置で爆弾を使う。
そのとき、一番左～一番左+2*Dまでの敵のHPを(一番左の敵/A)の繰り上げだけ減らします。二分探索により一番左+2*D番目の敵の位置を求め、遅延Segment treeを用いて区間のHPを減少させました。
データ構造を使わない方法もありますが、思いついた方法で解けば良いよね。
0 件のコメント:
コメントを投稿