2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) 日本語での解説
このセットの日本語での解説です。足りない問題は時間ができたら埋めます。
A
dpでやるかと思ったらこれ順序わからない。順序がわからないDPっぽい遷移はグラフと相場が決まってる。結局グラフの最短路でやる。でもやる際はよくよく考えると辺のコストは一定なのでダイクストラではなくBFSすれば間に合う。復元は、dplog[ni][nj] = P(i, j);的な感じで
C
イベントソートの典型問題。追加と消去をしながら、別の2つのBITで[値段]=個数と[値段]=費用をもっておいてそいつらに追加と消去をする。
そして、答えを求めるときは、kをぎりぎり超えるような、lower_bound的な値段を[値段]=個数のBITから求める。これはBIT上の二分探索で実装できる。
