2019/12/30

Codeforces 1270 D

interactive

規則性が見えやすいように実験結果を整理するべき(表にして整理する)

適当に実験していても見えてこないとき

→ある程度強い仮説を立てて検証していく

 

ABC149 E

愚直に全て計算してsortするのは間に合わない

→各人の寄与を別々に計算したい

→係数がわからない

 

Ax + Ayが大きい順に採用したい

→採用するかどうかの境界がある

→二分探索

 

貪欲に採用していく場合境界ができる

 

Codeforces 1283 D

貪欲に近い点から採用していきたい

→各treeからの距離が近い点から置いていきたい

→各treeからBFSをすればよい

 

直線軸はグラフ

 

Codeforces 1283 F

n<=10^5ぐらいなので順次決定できそうな気持ちになる

サンプルを基にグラフの決まり方を整理する

がんばって整理したものを実装する

 

最初の入力で電源とつながるランプpが分かる

コストが2^iなので、入力は(pとnの間にある頂点のうちpに近い方から),(pとn-1の間にある頂点のうちpに近い方から)...と続く(2^xとpの間に2^(x-1)がある場合などはxより小さい未出現の頂点)