CSA Round #41

競技プログラミング @LatteMalta

subset treesでTL厳しすぎて非常に時間溶かした

有為 @uwitenpen

Fは区間同士が階段状に交わっていればよく、始端昇順にソートしてn*nのテーブルを埋めていく感じでDPでO(n^2)でできる

satanic@研究💪 @satanic0258

E問題StarrySkyTreeでｴｲｴｲしてたけどダメだった

有為 @uwitenpen

Gは分割統治だと思ったけどtropical演算のFFTみたいなのが必要になり無理

(nは自然数) @n_vip

フジワラFM懐かしすぎるだろ

競技プログラミング @LatteMalta

Eはなんか遅延セグ木使う解法しか思いつかった。例のセグ木上で二分探索してlogを1つ落とすテクを実装する時間がなかったためO(Mlog^2 N)出したらふつうにTLEした

とーらす🌸📦🌕✨🍀 @torus711

やったこと　A: ソートして二個ずつとる　B: 何もできないか，一つの塊を広げるか，二つの塊をくっつけるか　C: なんかがんばる　D: DFS 順序をパスにして，BFS 順序は頂点 1 から適切な順序で辺を張って全部距離 2 にする．順序の第二要素は一致してないとダメ．

有為 @uwitenpen

日本人めっちゃでてる

kmjp @kmjp_pc

Subset Treesはなんも考えずdp[2セグメント交差する右端][1セグメントだけ存在する右端]を更新していって、このままだとO(N*R^2)になりそうなので適当にBITで累積和取ったらO(NR*logR)で通ったけどこれEの方がむずくない？

satanic@研究💪 @satanic0258

D解法頭良すぎるな

kmjp @kmjp_pc

Eはろうそくを昇順に並べて差分を取ってBITで長さを管理し、長さ順が昇順から崩れそうなら二分探索で適当に修正した。このデータ構造は今後も使えそうなのでライブラリ化しておきたい。

kuuso @kuuso1

D解法天才では（着想ゲーきつい．

有為 @uwitenpen

Dはほんとひどい

hogeover30 @hogeover30

A~Dまで思いつきゲーと言う感じだ。E以降は読んでない

kuuso @kuuso1

木で作れると思い込んでて，bfsのどこまで同じ深さで切るかをかんがえるのかーっ？？て無限にハマってた．

koyumeishi @koyumeishi_

D開くとブラウザ爆発したんだけど皆そんなことない感じ…？（firefoxでもchromeでもダメだったから開くのを諦めた）

hogeover30 @hogeover30

D開いたらPCメッチャ「フオォォォォォォ」っつってた

有為 @uwitenpen

1-3-4-5-2-6 1-5 1-6 1-4 1-2

kuuso @kuuso1

そもそもBに何回WA出すねんって感じで今日は体調わるかったなーって開始30分でどんよりしてた．

しさし @shisashi

ごめんEむり

kmjp @kmjp_pc

Fリジャッジでちょっと順位が下がった。

kuuso @kuuso1

これはdiv2あるな．

有為 @uwitenpen

不正なケースが入ってたのか

koyumeishi @koyumeishi_

CSAリッチなデザインなのはいいんだけど、複数の問題タブで開き難いし、順位表見ようとするとCPU100%になるしで色々つらくて毎度途中でやる気を失う

(nは自然数) @n_vip

リジャッジと言えばindia hacksのリジャッジはあるんですかね