Codeforces Round #694 (Div. 1)

A

セグ木を使えばできることはわかるが、流石に使わない楽な解法がありそうなので探す

→思いつかなかったのでそのまま書く

 

kが大きい人から順に、使えるうち最小のプレゼントを採用すればよいので、indexを持ったpairでRmQ+INFに更新

 

ソート済みの数列において区間最小値取得+値の削除ができればよいので、priority_queueで十分

 

前半枠でちょっとした嘘を生やして時間を使ってしまいがち、直したいな

 

B

操作の様子を掴むのに時間がかかりすぎた...

マージされる数のペアを考えると、平方数でない部分が同じもの同士はマージされることが分かる

 

どのタイミングでマージされるのか考える

一番最初にマージされるものは素因数分解でわかる

偶数個の数がマージされた場合、マージ後の値は必ず平方数になる→平方数同士でのマージがさらに発生する

奇数個の数がマージされた場合、マージ後の値は必ず平方数でない→このグループはこれ以上マージされない

 

同値類を意識して考察すれば早かったかも?

 

 

D

連結でない→彩色不可能

連結なら彩色可能?

 

頂点を一つRに塗り、その周囲の頂点を全てBに塗る

Bを塗った頂点を適当に一つ選び、その頂点につながる非彩色の頂点をRに塗る

これを繰り返せばよさそう?

 

Rを塗った後、周囲の頂点を全てBにするのでR-Rは生じない

Bを塗る頂点の隣には必ずRがあるので、非彩色の頂点がなくなるまで繰り返せば連結になる