C
c, dが昇順になっているので、二分探索してくださいって声が聞こえる。
余っているマナで最大の呪文2を唱えれば、使える呪文の中で一番大きい効果が得られる。
まず、何も呪文1を唱えないケースで計算しておく
(呪文2が使えたら使って、残ったnをxでかける)。
そのあと呪文1を全探索して、呪文2が使えたら使う。
残ったnをa_iでかける。
呪文1や呪文2がそれぞれ使えるかちゃんとチェックすることと、
long にしておくのを忘れなければACする。
D
King八方の一番近い駒が何か分かればいい。O(N)
斜めはabs(x - x0) == abs(y - y0)
縦横は x == x0 || y == y0
かどうかをチェック
Submission #22252291 - Codeforces
頭いいなあ・・・。実装中も結構WAした。
JavaじゃTLE解法
コンテスト中ではTLEが取れなくて終わった。TLEが4秒だったのに対して、
最悪ケースで8秒ぐらいだったのでつらかった。
Comparatorを
- 右方向(R, Q)
- 下方向(R, Q)
- 右斜め方向(B. Q)
- 左斜め方向(B, Q)
で定義しておく。
駒全部を突っ込んだlistに対して、
Kingで二分探索をしてindexを取り出してきて
その両隣が対象の駒かチェックすればOK。
と思ったけどこれでもTLEになってしまった・・・。
なぜ・・・。Javaじゃこの解法で解けないのか。
C++なら通ると思います。
Submission #22249746 - Codeforces
コンテスト中ではTreeSetを使って
駒からKingかどうか探していて
TLEした。
Submission #22248797 - Codeforces
コンテスト終わってTwitter の TLを眺めていたら、
落ち着いて考えればKingから見れば済むことに気が付いて落胆。
アホか。
でもこれもN log Nだし通ってほしかったな。