今日の精進 2020/06/15
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完
A:
小さいやつ見つけたあとにもう1周させて各小さいやつの距離を求める
B:
Aがi皿、BがN-i皿で雑に場合分けする
頭死んでて4WAした（はーーーー？？
C:
next_premutationで全部の場合試す
雑に10^5まで埋まってるか確認した（これ想定解？
| Educational Codeforces Round 35 |
|---|
https://codeforces.com/contest/911
復習
D:
最初にBITで数えた後に
l,rの範囲のswapで偶奇変わる
0->1か1->0にしかならないので何回swapするか計算(r-l)*(r-l+1)/2回なのでこれと偶奇判定
https://codeforces.com/contest/911/problem/D
半分全列挙
前半半分、後半半分をbit全探索して組み合わせを足す
いつもクラスカル法使うけど今日はプリム法使ってみた
実装ゲー
最後に誰が打つか考えてそれ抜いたとき終わるか確認するのが楽
二分探索
mid分間使うとき左の人から貪欲に動いてく
判定の添え字で頭壊れた
今日の精進 2020/06/10,11
平行移動、回転しても変わらない値で比を比較する（比を比較するって頭痛が痛いみたい
最初、凸法で凸多角形の辺の長さの合計でやろうとしたけどめちゃくちゃWAになったので重心求めて重心との距離が最大のもので比較した
凸法勉強しなきゃだなぁ
Mの余りで分ける
先に余りM-mとmのペア作れるだけ作ってから同じ値のペア作るのが最適
余りがmのときの作れるペア（同じ数）の個数をとっておいてmap乱用するとできた
こどふぉバチャ
Educational Codeforces Round 34
https://codeforces.com/group/ruzjfVC9CQ/contest/903
ABCの3完
A:
適当全探索
B:
適当にシミュレーション
C:
O(N^2)で貪欲
D:
多倍長ライブラリ持ってますか？僕は持ってません。
えでゅふぉ
Educational Codeforces Round 89 (Rated for Div. 2)
https://codeforces.com/contest/1366
A:
無限場合分け
B:
範囲を広げてく
C:
同じ感じになる場所の0,1の数の小さい方を足す
(連結成分-1)*2個の頂点をつなぐ
各連結成分は1個はつなぐ
をすると解けるらしい
最初と最後の数を加えていきながらdequeでよしなにしたら通った
これ境界みてくだけでいけたのね
今日の精進 2020/06/10
今日の精進 2020/06/08
青diff長期バチャやることにした
通ってきた頂点の最小値をコストとする
各頂点の一番コストが高いものを調べるようにダイクストラ
高い値から出るようにしていく
初期値は-1
値とindexを入れたペアでソート（値は*(-1)しておく
ペアの配列の最後に(0,0)入れておく
(次の要素と今の要素の絶対値)*(今までに見た要素の数)を今までみた要素の中で最もindexが小さいとこに入れる
今日の精進 2020/06/06
| Educational Codeforces Round 37 |
|---|
ABCの3完
A :
最初要素間の中央値でよしなにしようとしたけどなんかWAが出たので愚直にシミュレーションした
B :
愚直にシミュレーション
i番目の人見てるときに経過時間がrより大きければ0そうじゃなければその時間を配列に代入
C :
0が来た時i番目までの最大値がiと一致するか判定
ダメならNO
最後まで行けたらYES
https://codeforces.com/contest/920
復習
さっきのE
まだ使ってないものを入れるsetを用意しておく
最初から全部見ていってdfs(使用済みならcontinue
dfsではまだ見てないsetの要素と辺が張ってあるか確認してなければdfs
途中でどんどん要素が消されていくので次の要素見るときはlower_boundを使う
setの知らない使い方(想像しにくい)だった
https://codeforces.com/contest/920/problem/E
青diffバチャ
ABCで全完
1時間で全完してるのえらすぎる
A :
女子をN人中P人選び方を全探索
男子は女子の選び方をしたとき受け取る幸福度を合計して上からQ人
B :
縦1本横1本は絶対必要
横を小さい順にソートして累積和
全部の縦において横のほうが小さいときは横使う、縦のほうが小さいときは縦使う（さっきの累積和を利用してlower_boundとかで縦以上、縦未満を求める
C :
一回目で動ける範囲を全部求める（K回でいける範囲を求める
閉じたの減るのと動けるの減るの同じなのでその後は一番近い壁に向かって真っすぐいく
https://kenkoooo.com/atcoder/#/contest/show/62322bac-5b75-407d-a286-456ab230f5c1
今日の精進 2020/06/05
Educational Codeforces Round 38
ABCDの4完
A:
前がaiueoyで今がaiueoyだったら消す
追加するなら答えとなる文字列に加えるみたいにすると実装やりやすかった
判定で6まで見なきゃいけないところで5までしか見てなくて1ぺナ（は？
B:
配列の最初に1、最後に10^6を加えて
i番目まで先頭がいく、i+1番目以降は後ろがいくみたいに全探索
先頭でかかった時間 + 後ろでかかった時間を求めると誤読（は？
大きい方でよかったらしい
C:
n*n - floor(n/m)*floor(n/m) = xになるのを求めるといいことはわかる（ここまですんなり
↓ここから沼
さらに式変形(n - floor(n/m))*(n + floor(n/m)) = x
xの約数求める
それが上の式に当てはまれれるか判定
N/iとiが上のどっちかになる
( max(N/i,i) + min(N/i,i) ) / 2がnになる
( max(N/i,i) - min(N/i,i) ) / 2がn/mになる
s = ( max(N/i,i) - min(N/i,i) ) / 2
とおいてs = n/mを満たすmを探す
sqrt(n)で全探索
n/j == s満たすかn/(n/j) == s満たすか
満たせばOK
D:
適当ダイクストラ
辺のコストを2倍したら通った
https://codeforces.com/contest/938
この前のABCのB
sum*A[i] <= 10^18
ってするとsum=10^15,A[i]=10^15みたいなのが来るとオーバーフロー
A[i] <= 10^18/sum
ってすることでオーバーフロー対策できるのか
切り捨てとか怖くない？
とりあえずオーバーフロー対策は完璧
満たしたい条件はa*b <= X
b <= floor(X/a)で満たせる？
両方にaかける
a*b <= X' <= X
b <= floor(X/a)満たせばa*b <= Xを満たす
なんかいけるっぽい
青diffバチャ
ABCの全完（わーい
A : UnionFind
X軸同じやつ繋げる
Y軸同じやつ繋げる
集合の（X軸の数）*（Y軸の数）- (頂点数)
B : ダイクストラ
全頂点間に辺を張ってダイクストラ
辺の重みはmax(0,頂点間の距離-半径の合計)
complexまじ便利
C :
最大の直径の挙動見るとどの距離が必要かどの距離が作れないかがわかった
https://kenkoooo.com/atcoder/#/contest/show/92fe0d14-c106-4571-baf1-4c7afd232b25
復習
map<int,vector<int>>に値xが現れたindexを入れてく(前から見てるのでソート済み
こういうの鳩ノ巣ソートっていうのか
for(auto m : map)でxが小さいものからシミュレーション
各頂点を1回ずつしか見ないからO(NlogN)でできる
今日の精進 2020/06/04
復習
8方向にいけるもので連結成分の頂点数を数える
11^2とかきたらめんどくさいので121で割れるだけ割る
3^2もめんどくさいので9で割れるだけ割る
それ終わった後は11で割れるならC、3で割れるならA、他のはB
HCPCランダムチーム戦バチャ
A,E,Gを担当
A : A100通り、B100通り、C100通り、で全探索して残りをDでやる
E : 区間DP
dp[l][r][m]で[ l, r)の範囲をm種類目で作ることができるか
G : Z-algorithm
ABABAの最後のBとAの境界を全探索
境界以降のZ-algorithmで求めた値が一致してるか判定
残りの部分がBABになるか判定
個数が確定しているから(残り-A)/2がABラインのZで求めた値がA+Bより大きいか
https://onlinejudge.u-aizu.ac.jp/beta/room.html#HCPC200604/info
Codeforces Round #647 (Div. 2)
ABCの3完
A :
Aを2で割れるだけ割る、Bを2で割れるだけ割る
A != Bなら-1
A == Bなら2(で割れる回数の差+2)/3
B :
1 ~ 1023をkにしたときのxorが一致するか全探索
C :
Nを2のべき乗で割った数を足してく
D :
システス落ちたカス
難読やめろ
https://codeforces.com/contest/1362
