Codeforces Round #330

有為 @uwitenpen

あ、やっぱりA

有為 @uwitenpen

A解けないのかｗｗ

よすぽ @yosupot

A問題、アカンかったのか、解いてて気づけなかった

kmjp @kmjp_pc

自信ないとはいえBCD pretest通ったのに…。

zerokugi @zerokugi

暫定2位でﾖｯｼｬ！と思ったらなんかAが消えててunratedなんでよろしくというアナウンスが来ていた　感情喪失

よすぽ @yosupot

A問題についてのみなら大丈夫な気がする、そもそもコンテストの問題ではなくなったから

紙ぺーぱー @camypaper

A問題爆破マジ？

すぎむ @sugim48

A って N=20 くらいの愚直解と想定解を比較できそうな気がするんですが、ランダムケースでは撃墜できないくらい優秀なヒューリスティクスだったんだろうか

よすぽ @yosupot

C問題、4^k試すだけやん思ったらpretest4が通らなくて死亡

かつっぱ@ 競プロYouTuber @catupper

Div1 A:Unsolveable B:wolframalpha.com/input/?i=x%2B%…　の逆関数 C:k^4ためすだけでとおる？ D:Mo's Algorithm

よすぽ @yosupot

k^4や

よすぽ @yosupot

D問題、なんでみんな高速に解けるのかわからない、ソースコード246行になったんだけど

かつっぱ@ 競プロYouTuber @catupper

Mo'sAlgorithmすると普通にTLEで落ちそう

zerokugi @zerokugi

D、最初mo's algorithm書こうとしてあれ？TLEするじゃんと気付きSegtreeに路線変更した

よすぽ @yosupot

Dは値が全部素数の時だけを考えればよくて、これはrangetreeで解けるはず。

よすぽ @yosupot

いやね、クエリ先読みとか考えもしなかった

よすぽ @yosupot

しかも落ちた

よすぽ @yosupot

MLEか

よすぽ @yosupot

気にしなくても正解するはずなんだけどなぁ

かつっぱ@ 競プロYouTuber @catupper

mo's AlgorithmだとO(Nsqrt(N)*8)とかかな

kmjp @kmjp_pc

BC通ってDがTLE。Dはだいぶ雑な平方分割してしまったからなぁ。とはいえ悪くない順位なのでUnratedは残念。

zerokugi @zerokugi

B落ちた　TLEか…にぶたん回し過ぎたかな

有為 @uwitenpen

あ、にぶたんと黄金比混ぜたら普通に合うな、これでいいのか

有為 @uwitenpen

C,D解いて9位だった

zerokugi @zerokugi

Mo's algorithmは区間クエリをちょっとトリッキーな順番にソートすることで隣り合うクエリのabs(l'-l) + abs(r'-r)の総和をO(n^1.5)にするアルゴリズム