Codeforces Round #332 (Div. 2)

すぎむ @sugim48

※ 注意 : 問題は難易度順に並んでいるとは限りません。 codeforces.com/contest/354

nico_shindannin（診断人） @nico_shindannin

Codeforces 全問とりあえず眺めたいところじゃ。

nico_shindannin（診断人） @nico_shindannin

すぎむさんが8秒前に似たようなこと言ってた

有為 @uwitenpen

Eできなかった・・

kmjp @kmjp_pc

前回といい今回といい、計算量とかオーバーフローとかあまり考えずにやって落とすというひどく雑なプレーをしている。

すぎむ @sugim48

E の実装が困難すぎる

有為 @uwitenpen

微妙にバグらせるとつらい・・

nico_shindannin（診断人） @nico_shindannin

【ニコ生放送中】 TopCoderでプログラムしてみた 第2229回(Codeforces #332 直後放送) nico.ms/lv242719445#00… #co78570 pic.twitter.com/JoRwbo27P7

拡大

すぎむ @sugim48

E の実装で変数名が無限に増えてしまってついに禁断の _unko_[8192] が現れた

すぎむ @sugim48

E の 実装を続ける気力、無し――

有為 @uwitenpen

あーバグ取り終わった・・これはわからん・・

有為 @uwitenpen

13の時点でやばい予感しかしなかった

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

風邪で頭があれで問題文すら頭に入ってこなかったからEだけやった。(寝なさい)

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

TLEよく分かんなかったけどビット演算で押せば大丈夫やろーと思いながらやった。一ヶ所バグらせてハマってしまった。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

実装特に悩ましい部分はないし、風邪ひいててもできる程度だと思うけどなあ

有為 @uwitenpen

32位か・・

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

dp[頂点集合][親]=条件を満たしてる部分木、d[頂点集合][親]=作りかけの部分木、dに部分木をくっつけて行って(このとき、くっつける部分木に"親"の子のうち番号が最大のものが入ってるようにすると、重複なく数えられる)

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

dのうち、"親"をlcaにもつ頂点が全て部分木に含まれていれるものはdpの方へ昇格させる。

pekempey @pekempey

Bをsubmitしたら一気に2回分提出されたの何なんだろう

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

辺制約は、各頂点に隣接する頂点の集合を持たせて、くっつける部分木の"親"以外の部分に隣接すべき頂点が含まれてはいけないとか、くっつける部分木の"親"が隣接すべき頂点に全て隣接するかとかチェックする

nico_shindannin（診断人） @nico_shindannin

【ニコ生放送中】 TopCoderでプログラムしてみた 第2230回(Codeforces #332 直後放送 D) nico.ms/lv242721544#00… #co78570 pic.twitter.com/fzo6kIAmLn

拡大

有為 @uwitenpen

なんでこういうの速く解けないんだろうなあ・・

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

lca制約は、lca(a,b)=cのとき、a,bはcの部分木内に無くてはだめで、cに部分木をくっつけるときに同じ部分木内にa,bが同時に含まれてはだめ。辺制約もこれもビット演算でできてハッピー。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

コード読んだ方が早そう

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

DPすき