VK Cup 2017 Round 3(Codeforces Round #412 Div.1 + Div. 2)

agw @masashinakata

VK Cup 2017 Round 3(Codeforces Round #412 Div.1 + Div. 2) - Togetterまとめ: togetter.com/li/1108250

agw @masashinakata

をー、ABC通ってたー ヽ(´▽｀)ノﾜｰｲ♪

agw @masashinakata

Bで終了条件間違えて再提出、Cでにぶたんの初期値間違えて再提出だったけど、なんとか持ちこたえた感じだ

agw @masashinakata

Bは終了条件がよく分かっておらず、Cは解がない場合の判定がよく分かっていなかったりする…

タッパーをオーブンで焼かない @DEGwer3456

14th 2659 -> 2738(+79) よい

タッパーをオーブンで焼かない @DEGwer3456

Wow! Coder DEGwer competed in Codeforces Round #412 and gained 79 rating points taking place 14 codeforces.com/bestRatingChan…

よすぽ @yosupot

pic.twitter.com/aJkAhs3dNn

拡大

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Eやっと通った。こういう実装が遅すぎる。（もっと簡単になるのか・・・？）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

りんごさんのコードの短さ見て何か間違ってることがわかった。

よすぽ @yosupot

@snuke_ じゃあ僕のコードの短さ見て正しさを感じてください

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@yosupot 実装が速すぎる。雰囲気方針は違いそう。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

E：単調増加に並べるのが最善。ある人の親というのを「その人をちょうどのscoreで通過したら、後にちょうどのscoreで通過される人」と定義する。親が増えることはあるが、親が親でなくなることはない。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

人を追加したとき、その人の親を探す。さらにまだ親がいない人の親を追加した人に近い順に見つかり続けるまで探す。これらの操作は区間addと区間内でx以下の値の内最も左にあるものを答えるクエリを処理するsegtreeを使えば出来る。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

質問クエリでは、-1がどこまで続くかを求め、その地点の親みたいなのを探し、いなければずっと+1、いればその人の根（親の親の・・・親）から+1し続けた値が答え。根はunionfind的にやれば均しO(log N)。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

あー、そっか。最下点みたいなやつだけ気にすれば良いのか。途中でぶつかる人がいても、代わりにそこで+することにして最下点で-1ではなくminが取られるんだと思えば良いのか。なんか気づかなかったな。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

ボケてるしボケてをやれば良さそう。

chokudai(高橋 直大)🍆 @chokudai

E問題、「まぁ通らんやろ・・・」って捨てた超軽実装な方針があっさり通って、書けばよかったーって思ってる codeforces.com/contest/806/su…

chokudai(高橋 直大)🍆 @chokudai

冷静に考えると、C++ならまぁ通るだろうなって信用していい程度の実行時間なので、C++で書くのが最善かなあ。（ただC++のBITは持ってない）

naoya t @naoya_t

@masashinakata @masashinakata naoyat.hatenablog.jp/entry/Codeforc…