Codeforces Round #379 (Div. 2) A B C D

codeforces.com

A

mapっぽいもの(int[256)を用意して数えて出力

Submission #22227451 - Codeforces

B

256を貪欲に選んだあと、残ったもので32を生成する。
怖いのでlongにした。

Submission #22231261 - Codeforces

C

c, dが昇順になっているので、二分探索してくださいって声が聞こえる。
余っているマナで最大の呪文2を唱えれば、使える呪文の中で一番大きい効果が得られる。

まず、何も呪文1を唱えないケースで計算しておく
(呪文2が使えたら使って、残ったnをxでかける)。
そのあと呪文1を全探索して、呪文2が使えたら使う。
残ったnをa_iでかける。

呪文1や呪文2がそれぞれ使えるかちゃんとチェックすることと、
long にしておくのを忘れなければACする。

Submission #22237778 - Codeforces

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だし通ってほしかったな。