コンテストページ:https://codeforces.com/contest/1322
結果
A, B, C の 3 完です。
いえ、Cしれません がシステスに落ちてしまったようです。
反省
暗算の間違いや、標準入力の高速化わすれなど、かなりしょうもないミスが多かったです。 Vim 環境に移行してから、環境整備はかなり保守的にしているのですが、標準入出力高速化を含むテンプレなどは、そろそろ整備したほうが良さそうです。(します)
A - Unusual Competitions (00:06:25)
深さを管理して、負になっている部分を選択すると良いです。 ここまでは順調です。
Codeforces さん、序盤はジャッジが遅かったのですが、順位表が動くのも遅かったですから、これはおそらくみなさ同じだったのでしょう。
B - Present (01:09:29 + (2))
入力は高々 17 桁ですから、答えは 18 桁以下です。 0 ≦ k < 18 に対して、このビットが立っているのかを計算です。
まず、繰り上がり以外の部分の寄与は簡単です。 繰り上がり部分は、$ a $ の項をすべて予め $ 2 ^ k $ で割っておくと、 これらのペアのうち和が K 以上になるものですから、尺取り法で求めればよいです。
お気づきでしょうか。 17 桁ではたりません。
はい、お疲れ様でした〜〜(泣) この問題でのロスがかなり痛かったです。
C - Instant Noodles (01:58:00 + (5))
右側のうち、どこにつながっているのかが完全に同じものを纏めましょう。 これを計算して vector にいれて、map でカウントです。
TLE を連発してしまいました。 最悪ケースでも Θ( N * log ( N ) ) のはずなのですが……
私は天才なので思い出してしまいました。これは † Codeforces † であるということを。
std::cin.tie(nullptr)
さんと std::basic_ios::sync_with_stdio(false)
さんを召喚して事なきを得ました。
さすがにテンプレを用意しないと、書き忘れてしまいます。