ブログ名

競技プログラミングやお歌のお話をする高菜です。

Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics) 解法

コンテストページ:https://codeforces.com/contest/1322

結果

A, B, C の 3 完です。

f:id:ngtkana:20200307232047p:plain

いえ、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) さんを召喚して事なきを得ました。

さすがにテンプレを用意しないと、書き忘れてしまいます。