Facebook Hacker Cup 2019 Round 1 + Educational Codeforces Round 67

千咲=タプリス=シュガーベル @gzlcp

1 つでも実現したら優勝だろ

千咲=タプリス=シュガーベル @gzlcp

risujiroh さん順位表で隣だったのにいなくなったから hack されたのかと思ったら全完してた

千咲=タプリス=シュガーベル @gzlcp

あ

千咲=タプリス=シュガーベル @gzlcp

1 ページ目でたえた

千咲=タプリス=シュガーベル @gzlcp

うしさんの隣にいます

もる @eomole

Texas InstrumentsとFacebookって何か関係あるのだろうか…？

千咲=タプリス=シュガーベル @gzlcp

F みたいなの rated のときに出てほしいな

うし @ei1333

A: う B: し C: ソートするところを先に埋めて、残ったやつを降順で埋める D: 前から貪欲に揃えるようにいい感じにやる E: 何も考えずに全方位木DPライブラリを貼るだけです F: 解けねえ G: よくわからん　適当にギャグみたいなグラフを作ってフロー流したら通ってウケちゃった

千咲=タプリス=シュガーベル @gzlcp

F は線形だと解けるんだけどよく考えたら展開すると線形になる

千咲=タプリス=シュガーベル @gzlcp

ので頑張る

千咲=タプリス=シュガーベル @gzlcp

E、ちょっと迷ったけど結局全方位書いてしまった

千咲=タプリス=シュガーベル @gzlcp

全方位、無すぎるけど想定なのか

うし @ei1333

E、かなりきれいに貼るだけができる

千咲=タプリス=シュガーベル @gzlcp

G、重い多項式（フロー）か難しい問題か迷ったけどフローは知らないので頑張って指数アルゴリズム作ろうとしてた

うし @ei1333

Gはなんですか　ギャグですか

千咲=タプリス=シュガーベル @gzlcp

フロー知らないのでこまってしまう

うし @ei1333

ギャグフローはちょっと...

こるとん @kyort0n

Educational Codeforces Round 67 お疲れ様でした A n - min(s, t) + 1 B 累積和取ってにぶたんしたけど 絶対想定解じゃねえ C a[1]=5e5スタート ソート範囲内では+1 そうでないとこなら-1 最後に全部満たすかチェック

こるとん @kyort0n

D aとbで対応する項をチェック 値の大きい項から順に行き先をセグ木で管理して、行き先が交差しないか調べた 流石にもっと良いやり方ありそう E 答えはmax_i(頂点iから他の頂点までの距離の総和) + n 他の頂点までの距離の総和は木dpでok

こるとん @kyort0n

G 最小費用流 (街、日付)で頂点を持つ 自分の街に留まるコストc 道に対応する辺は、 (2*i-1)*d + c (i=1, 2, ..., k) を張る

有為 @uwitenpen

Fいけんかった・・

こるとん @kyort0n

初めて最小費用流の非自明問題通せた気がする やったね

千咲=タプリス=シュガーベル @gzlcp

D は隣接 swap だけ考えればよいです

千咲=タプリス=シュガーベル @gzlcp

多分貪欲に寄せていけばよいのでセグツリで頑張る

うし @ei1333

D、priority_queueで寄せてったな