Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

竹雄 @takeo1116

1855位でFinish(死)

竹雄 @takeo1116

Dの懺悔は明日やります

竹雄 @takeo1116

レート下がってないといいけどこどふぉだし別に下がってもいいや

竹雄 @takeo1116

土曜にARCやってなかったらA問題の2進数一生思いつかなかった説ある

olphe @_olphe

@takeo1116 わかる

竹雄 @takeo1116

@_olphe わかられ～

竹雄 @takeo1116

なんならB問題もmedian of mediansやってなかったら絶対もっと時間かかってたんだよなあ

竹雄 @takeo1116

やはり新しい習慣であるところの”””懺悔”””が効いているのかもしれない

竹雄 @takeo1116

懺悔室 - 竹雄のホームページ takeo1116.sakura.ne.jp/reflection/ref…

olphe @_olphe

CFは 得点/その問題にかかった時間 が大きい順に解くのがいいはず(厳密には知らないけど)なので瞬殺できるところまでは瞬殺してあとは問題と相談している

はむこ @hamko_intel

真面目にこの量のWAを防ぐのってどうすればよいんですかね pic.twitter.com/y9Tj3Kcij0

拡大

はむこ @hamko_intel

昨日のこどふぉのEが意味不明

はむこ @hamko_intel

BFSの問題みたいな、必要条件上げまくってたら実は必要十分になってました系に弱すぎる

有為 @uwitenpen

きのうのManthanのC, 01-10とflipだけ考えれば良かったんだけど、これであっている確信がなくて愚直解書いて比較してた。人々どうやって確信を持つんだろう

こうきやまぐち @Ymgch_K

@hamko_intel k=1のときとか現実世界にありそうなシチュエーションぽくないですか

はむこ @hamko_intel

@Ymgch_K ぼっちに厳しい世界…

こうきやまぐち @Ymgch_K

@uwitenpen どのへんで不安になるのか気になりました（コスト2以上のswapでflipより得することはないからしない、だけじゃだめなんですか）

有為 @uwitenpen

@Ymgch_K swap1回だけじゃなくて、刻んでswapすることもできるじゃないですか。その場合flipより得する場合が出てくるのか自信がなかった

こうきやまぐち @Ymgch_K

@uwitenpen 刻んでswapってなんですか？（そもそも仮に最適解に2以上のswapが含まれていればその部分を2のflipに置き換えられると思います）

有為 @uwitenpen

@Ymgch_K ABC→ACB→CABみたいにするやつです

けんちょん @drken1215

@_olphe SRM 502 DIV1 Medium が、Codeforces の最適戦略を題材にした問題で面白かったです！！！

olphe @_olphe

@drken1215 そんな高いところで出る問題だったか…

けんちょん @drken1215

@_olphe で、「得意順に問題をソートした上でナップサック的な問題を解く」という想定解法の問題です。 結局、おるたんの言う通り、Codeforces は得意順 (難易度/かかる時間の大きい順) にやるのが最適ですね！

olphe @_olphe

@drken1215 よかった～(ありがとうございます)

kroton @kroton_pc

Manthan, Codefest'18 F. Maximum Reduction codeforces.com/contest/1037/s… これすき