FightMonsterDiv1 [SRM749 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=15296

体力HPの敵がいる。
自分の初期攻撃力がattackで、攻撃するたびに(初期attack)*level/100だけ増える。
（つまり、増える量は常に固定）
1度だけスペル詠唱が可能で、スペル詠唱後はduration秒間、攻撃力が5倍になる。
攻撃、スペル詠唱ともに1秒かかるとき、敵を倒すのにかかる最小時間は？
　
1≦hp, duration, attack≦10^12
attackは100の倍数
0≦level≦100

解説

答えの候補を順に見てみると、倒せる0, 倒せない1は000000111111のようになっているので二分探索しよう。
md日間で倒すことを考えるが、最適な動き方がある。
　

• なるべく魔法攻撃を使ったほうがいい
• 魔法攻撃は攻撃力の高い後の方に使う方がいい

　
よって、なるべく後ろで魔法攻撃を使う方針で実装しよう。
md日間のうち、後ろのduration日間は魔法攻撃にする。
duration日の後ろ1日はスペル詠唱の時間で、残ったmd-(duration+1)日間は通常攻撃を行う。
通常攻撃と魔法攻撃の中身は等差数列の総和になっているので、O(1)で高速に計算可能。
　
この解法だと途中でlong longの範囲を超えるので、__int128で乗り切ろう。
これが嫌な場合は、levelが0以外の場合はsqrt(hp)が答えの上限になるので、場合分けすることでオーバーフローを回避できる。
こうする場合は二分探索は必須ではない。
　
あと、答えが1の場合は魔法詠唱はしないので、場合分けして答える。

typedef __int128 ll;
ll tousasm(ll a, ll d, ll n) {
    return (2 * a + d * (n - 1)) * n / 2;
}
struct FightMonsterDiv1 {
    long long fightTime(long long hp, long long attack, int level, long long duration) {
        // ans=1
        if (hp <= attack) return 1;

        ll d = attack / 100 * level;
        ll ng = 1, ok = hp;
        while (ng + 1 != ok) {
            ll md = (ng + ok) / 2;

            ll tot = 0;

            ll normal = max((ll)0, (ll)md - 1 - duration);
            ll magical = min((ll)1 * md - 1, (ll)duration);

            tot += tousasm(attack, d, normal);
            tot += tousasm(attack + d * normal, d, magical) * 5;

            if (hp <= tot) ok = md;
            else ng = md;
        }

        return ok;
    }
};