A
セグ木を使えばできることはわかるが、流石に使わない楽な解法がありそうなので探す
→思いつかなかったのでそのまま書く
kが大きい人から順に、使えるうち最小のプレゼントを採用すればよいので、indexを持ったpairでRmQ+INFに更新
ソート済みの数列において区間最小値取得+値の削除ができればよいので、priority_queueで十分
前半枠でちょっとした嘘を生やして時間を使ってしまいがち、直したいな
B
操作の様子を掴むのに時間がかかりすぎた...
マージされる数のペアを考えると、平方数でない部分が同じもの同士はマージされることが分かる
どのタイミングでマージされるのか考える
一番最初にマージされるものは素因数分解でわかる
偶数個の数がマージされた場合、マージ後の値は必ず平方数になる→平方数同士でのマージがさらに発生する
奇数個の数がマージされた場合、マージ後の値は必ず平方数でない→このグループはこれ以上マージされない
同値類を意識して考察すれば早かったかも？
D
連結でない→彩色不可能
連結なら彩色可能？
頂点を一つRに塗り、その周囲の頂点を全てBに塗る
Bを塗った頂点を適当に一つ選び、その頂点につながる非彩色の頂点をRに塗る
これを繰り返せばよさそう？
Rを塗った後、周囲の頂点を全てBにするのでR-Rは生じない
Bを塗る頂点の隣には必ずRがあるので、非彩色の頂点がなくなるまで繰り返せば連結になる