■A - Distinct Strings
文字数の種類で1or3or6
■B - Star or Not
n-1本edgeが生えている頂点があればスター
■C - Calendar Validator
やるだけ
■D - Play Train
自分の前と後ろを管理する。
■E - フ
これはただの区間スケジュール問題
■F - String Cards
これ難しい。
前からではなく後ろからdpをする必要がある。
s0+s1みたいなことをするとして
s0の後ろにくっつけられるn要素で作った辞書順最小の文字列が必要になるため。
■G - X
フローなのは見たらわかる。
a0+a1-c
a0+a1+a2-c
a0+a2-c-cなどを最大化する。
マイナスが邪魔なので式変形をして
(a0+a1+a2)-(a2+c)
(a0+a1+a2)-(c)
(a0+a1+a2)-(a1+c+c)の最大化なので
a2+c
c
a1+c+cの最小化なので、
これをグラフに落とし込むと最小カット(埋める燃やす)に落ちる。
■H - Social Distance 2
ei1333の日記-積の和典型
を思い出すと公式解説に書いてある「Combinatorialな言い換えで解く方法」の式が立つ
あとは分割して適当に畳み込みすればいいので
分割統治で頑張る。queueにいれてsizeが1になるまでやればいい。
