CSA Round #79 (Div. 2 only)

iwashi31 @iwashi31

E、最小値からダイクストラしつつ 5 * K 分近傍が集まったらソートして返すみたいなのやって 25 ケース目までは無理やり通したけどさすがにダメだったね

てんぷら @tempura_cpp

A 自分が間にいるか端にいるかで場合分け B 言われた通りにやるとできる C 前から順番に見て先頭におけないなら1番後ろに回す D なんか言われた通りに実装したら通ってウケた、計算量わからない

アルハンブラ宮殿のゆるキャラ @nebukuro09

ビームサーチまじ？

iwashi31 @iwashi31

僕の C です pic.twitter.com/Xv5y7MqdSy

拡大

iwashi31 @iwashi31

辞書順だし貪欲で良さそうと思ったら貪欲で良かった

てんぷら @tempura_cpp

D、ガチでなんの工夫もしていないのに通ってしまったのよく分からなすぎる(通るわけないと思って色々考えてた30分返して欲しい)

Hideyuki Tanaka @tanakh

CSA Round79のE問題やっとこ解けた(´･_･`)

iwashi31 @iwashi31

D は計算量よく分からんけど可能な限り速くするぞ！という気持ちで実装を進めたら通った

うし @ei1333

Cです pic.twitter.com/LHJvRqaUqT

拡大

とど @kame_2211

@ei1333 うC

うし @ei1333

@kame_2211 うっしっし

Hideyuki Tanaka @tanakh

符号が揃ってる数列の部分和の小さい方からの列挙を効率よくやる方法の簡単なルールを見つけ出すのに50分ぐらいかかったね(´･_･`)…

てんぷら @tempura_cpp

まぁ辞書順最小は貪欲でやるものだと決まっているので

うし @ei1333

んーこれどっかでかいたことあるきがする

iwashi31 @iwashi31

結局嘘解法だったけど Zobrist Hash 初めて書いてちゃんと動いてくれて楽しかった

うし @ei1333

つたじぇーさんのDすげえ

アルハンブラ宮殿のゆるキャラ @nebukuro09

Dでかなりなんの疑いもなくbitsetやったんだけどまったく想定解法じゃなさそうでウケた

うし @ei1333

んーなんやこのD　なにしてもとおるやん

iwashi31 @iwashi31

CSA はたまに爆速で問題解けて天才の気分に浸れるので好きです

hogeover30 @hogeover30

C、どうせ既出だろとおもってググってたんだけど見つからなくて結局自分で考えた

iwashi31 @iwashi31

D は各グループの代表者を特定しておいて、クエリでは代表者以外はスルー、代表者が出てきたらそのグループ全員についてクエリに含まれるかチェックするというのを書いた

iwashi31 @iwashi31

あー、E はスタート値を負の数の合計にしておくと後は N 個の非負整数を足していく話になるのか。賢そう

iwashi31 @iwashi31

ソートして前から [次のを足す], [今のを引いて次のを足す] を優先度付きキューに突っ込んでいくだけで良いのか…

iwashi31 @iwashi31

う～～～ん賢い

iwashi31 @iwashi31

珍しくレート変動時間かかってるなぁ。寝時がわからない