傾向としてGはまだad-hoc寄りで、Hは高度典型って感じがする。
■A - New Generation ABC
if else if else
■B - How many?
s^3全探索する
■C - Distribution
ダイクストラっぽくやる方法もあるらしいですが
となりに配るdpで二周回す。
■D - Sum of Maximum Weights
パスの重みでソートして、union findでつないでいく。
■E - Packing Under Range Regulations
区間スケジュール亜種。
priority_queueに締め切り時間を突っ込んでいき
毎日、締切の早いものから処理していく
締め切りが終わったものがqueueから出てきたらNG
■F - Substrings
acbacだったとして、
acみたいなのが{0,1},{0,4},{3,4}で重複する
これを重複しないように{0,1}だけ処理するようにする。
??abcacとみて
1011223とする。(説明適当)
■G - Three Permutations
まず、pとqが与えられているが、pはソートして1,2,3,4....に変えても問題がない。
問題を読むと、どうせ包除原理だろうというのは察しが付く
ans = 少なくとも0要素が条件を満たす - 少なくとも1要素が条件を満たす + 少なくとも2要素が条件を満たす - ......
としたら良い。
サンプル１を例にして考える。
4
1 2 3 4
2 1 4 3
1-2が連結成分、3-4が連結成分。
連結成分ごとに個別に考えて、畳み込めばよさそう。
ここまでの考察は自然に出来る。問題はここから。
上で書いた連結成分をグラフ(ring)として見る
辺に対して
右の要素を割り当てるか、左の要素を割り当てるか、未決定の三要素に分けてdpをする
ただし、同じ要素を複数の辺に割り当てることはできない。
つまり、
1-2-1に対して
- ?-?-
- ?-1-
- ?-2-
- 1-?-
- 2-?-
- 1-2-
- 2-1-
- 1-1-(ng)
- 2-2-(ng)
といった感じで{1,4,2}を得れば良い。
ここのdpは一番最初に選択したものと、最後に選択したものを保持しておいて(3*3)遷移させれば良い。
■H - Collecting
最小費用流。
負辺があったときの最小費用流を正しく扱えますか？という問題。
まず、強連結成分分解して纏めることの出来る頂点は纏められる。
とりあえず、負辺とか無視して辺を張ってみる。
頂点数を倍にしてin/outを作り、
cost:有,cap:1の辺と、cost:無、cap:k-1の辺をin outの間に貼ることで
落とし物を一回しか拾わないようにすることができる。
あとの辺は適当に貼る。
ここからが問題で、あとは負辺をどうするか。
これはダイクストラ ポテンシャルとかで検索して
解説動画を見て勉強しうまい感じにやる。
