考えたこと 2倍の回数はlogオーダーになるので大した回数にならない 3回2倍するとき a +x[0] *2 +x[1] *2 +x[2] *2 + x[3] 8a + 8x[0] + 4x[1] + 2x[2] + x[3] = newA になるようなxを見つける 最小回数なら2進法みたいな感じで貪欲にやれば求まる 適当な実…

考えたこと 最大の最小化なのでにぶたんをする Rを決め打つとO(n)で可能かどうかの判定ができそう 出すと通る THE典型みたいなにぶたん #include <bits/stdc++.h> using namespace std; using ll = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #d</int,></vi></int></bits/stdc++.h>…

考えたこと 長さ3の経路ができないような木を考えるとウニしかない 葉が101個のウニをつくる ウニの葉に頂点をつなげると長さ3の経路が+100される これで100,200,300,400,…,10000までつくれる ウニの中心から長さ3の足を生やすと長さ3の経路が+1される これ…

考えたこと 子の数の和が頂点数-1なら木構造がつくれそう つくれるなら適当な木を構成して直径を求めればよさそう 木の構成で悩む トポソみたいに葉としてしか使えない頂点を子にした頂点をつくるを繰り返して構成したらいい気持ちになる 木が構成できたら直…

考えたこと とりあえずソートしない理由はなさそう 明らかに二部マッチング 完全二部マッチングの個数の数え上げ NPなので無理です ソートしてあるとwarriors[i]とマッチングできるhorse[j]についてjの区間は[0,x]になって単調増加する warriors[i]がマッチ…

考えたこと 操作回数が多いのでうまくまとめる系の問題 時刻hで従業員nがtaskを持っているとき交換が起きるのはn-1,nの約数でh+1以上の最小の時刻 約数の列挙はO(sqrt(n))でO(n)個分やってたら当然TLE 交換回数がO(logn)とかO(sqrt(n))になってくれるとうれ…

考えたこと _の配置の組み合わせ数を無視してとりあえず;の方だけ数えてみようとする ;でペアを組めるのは_を挟んでるやつだけ i番目を始点, j番目を終点とできるなら辺i→jを張るみたいなグラフを考える DAGのマッチングに落ちたと思ったけどマッチングが何…