今日の精進 2020/06/15 - pitsuの精進日記

0の数が2以上、1が0じゃなければ0

距離iの頂点数cnt[i]としたとき答えに(2^cnt[i-1]-1)^cnt[i]と2^(cnt[i]*(cnt[i]-1)/2)をかける

ワーシャルフロイドの更新はその辺の両端だけを考えればいいので一回のクエリに対してO(N^2)で済む

前から貪欲に数え上げる

最初の人は1まで1ずつ減らせる

次の人は2じゃなければ2ずつ減らせる

2だったらもう減らせないので次の人は3ずつ減らす

みたいな感じで減らしてく

全方位木DP

dfs1で0を根とした木DPで部分木の頂点数を求めて

dfs2で0を根として各頂点から0への方向の頂点数も求める（N - dp[v]でできる

えでゅふぉバチャ

ABCの3完

小さいやつ見つけたあとにもう1周させて各小さいやつの距離を求める

Aがi皿、BがN-i皿で雑に場合分けする

頭死んでて4WAした（はーーーー？？

next_premutationで全部の場合試す

雑に10^5まで埋まってるか確認した（これ想定解？

Educational Codeforces Round 35

復習

最初にBITで数えた後に

l,rの範囲のswapで偶奇変わる

0->1か1->0にしかならないので何回swapするか計算(r-l)*(r-l+1)/2回なのでこれと偶奇判定

半分全列挙

前半半分、後半半分をbit全探索して組み合わせを足す

いつもクラスカル法使うけど今日はプリム法使ってみた

実装ゲー

最後に誰が打つか考えてそれ抜いたとき終わるか確認するのが楽

二分探索

mid分間使うとき左の人から貪欲に動いてく

判定の添え字で頭壊れた