■41:C - ウサギ跳び
方針的には簡単だが、実装が少し面倒
端っこの処理を上手にやらないと事故が起きる。
■42:C - おやつ
ナップサック
一番安いものを覗いて予算内に収まればいいので
入力情報をソートしてdpを使い回すといい
■43:C - 転倒距離★★★
配列Aは0,1,2,3,4....と読み変えて問題がない
それに合わせてBもマージする。
そしてAB間の転倒数が偶数なら成立、奇数なら非成立なのもわかる。
BからAを転倒数の半分を超えないとこまで復元すると求めたいものが出来る
注意しないといけないのはN=10^5の転倒数はintで収まらないことがあること
このせいで謎のREとTLEが出て困った
■44:C - ビーム
XとYは独立で考えていい
dpは更新が少ないので使い回す。
■45:C - エックスオア多橋君
aとbを結んだ経路のxorはaからxと、bからxを結んだそれぞれのxorのxorと同じ(共通部分が打ち消されるため)
答えがintで収まらないことがあること
x=0のときにa==bは除く必要がある
■46:C - 合コン大作戦
片側をsortし、もう一方をそのsortに都合のいいようにsortする
その中から条件を満たす最弱を割り当てる
(注)
早い：auto it = st.lower_bound(men[i].second);
遅い：auto it = lower_bound(st.begin(), st.end(), men[i].second);
■47:C - N!÷K番目の単語★★★
前から決めていく
使われていない数の何番目を使うかを決めていく
あとはセグ木上で二分探索
■48:C - 足の多い高橋君★★★
回分の繰り返しになることにわかればいい
わかればそれの繰り返し二乗法
■49:C - ぬりまーす★★★
強連結成分分解(SCC)を使う
タイプ２の条件の読み替えと、
使わない点の処理方法(頂点Nを増やして、それと双方向に結ぶ等)
■50:C - LCM 111
lcm(A,B) = A*B/gcd(A,B) = (A/gcd(A,B))*(B/gcd(A,B))*gcd(A,B)
なので1000100010001みたなもののmodMでの値を行列累乗の容量で求めればいい
