Codeforces Round #618 (Div. 1)

　Cまでの三完でした。
　Cで、PyPyで出たTLEを除くことができず、C++に書き直した……というトラブルを除けば上出来。PyPyでTLEになっていた原因は、気付けば当たり前のことだったんですが、ちょっと気付きにくいことな気もするので、まあ仕方ないかなぁ、という気もしています。

コンテストへのリンク

A. Anu Has a Function

　bit演算に関する問題なので、bitごとに考える。

・(1 or 1) - 1=0

・(1 or 0) - 0=1

・(0 or 1) - 1=0

・(0 or 0) - 0=0

　というのが各bitについて成り立つ。だから、今、k番目のbitが立っていても、もし後で「k番目のbitが立っている数」と演算しなければいけないなら、そのbitは0になってしまう。

　なので、「一つの数でしかbitが立っていない最上位の桁」を持っている数を最初に置けばOK。

B. Aerodynamic

　点対称ならOK。

　こういう問題は厳密に証明できずに提出してもまあ良いかな、という気がする。

C. Water Balance

　スライムを合成させていくイメージで考えた。

　コンテスト中、DP まとめコンテスト　N - Slimesを見に行ったけど、あまり関係なかったね……。

　右のスライムのコストが左のスライムのコストより小さければ合成させる、という方針で良い。

　このとき、

・4, 2 → 3, 3

　のように合成させていると、制限時間に間に合わない。そこで、もともと何匹のスライムだったか、という情報を持って、

・(4, 1), (2, 1) → 3, 2

　のように書くようにすると、O(n)になり間に合う。

　コストkのスライム達が並んでいて、その一個左隣のスライムのコストがkより大きければ、「一番左のスライムと何匹か合成されたスライム」のコスト（平均）は必ずkより大きいので、全部合成されるまで（左のスライムのコスト）>（右のスライムのコスト）となる部分ができてしまう。

　だから、こうやってまとめて良いことが分かる。

　さて、TLEになった原因は、出力の際に毎回for文を書いたせいでした。(x, y)に対して、

for i in range(y):

    print(x/y) 

　のように書いてたんだけど、こういう風に毎回for文を生成するのは遅い。

(str(x/y)+"\n")*y

　を出力するようにしたらTLEが取れました。