今日の精進 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)でできる
