MUJIN 2018

開始前: 賞金あるやん!ありがとうございます 海外勢もいないし頑張りたい

A,B:無
C: Bとの落差で少したまげたけどやるだけ
D: 設定が意味不明すぎて混乱したが結局サイクル検出のようなことをやればいい バグるだろうなあと思って書いたらバグらなくてたまげた サイクル検出はライブラリ化してるけど、それの最終状態でvis=1になるやつをcountすればいい(自分用メモ)
E: また迷路かよ… よくあるdijkstra亜種, 辺の長さが今いる時刻によって変わるけど、別にトポロジカル順に見れることに変わりはない
F: 去年のTCO final でみて結構なるほどなって思った 大きさ順でdpしていくと候補が増えていくDPになる
G: 係数a,b,cとしてabc空間を考えると三角錐みたいになる, 同値条件を考えるとa-a' : b-b' : c-c' = A:B:C ただしA,B,CはAp+Bq+Cz=0なるもののうちgcd=1のやつ になるので、同値類を数えたければ(a,b,c) in X かつ (a+A,b+B,c+C) notin X みたいなのを数えれば良くて, 式立てればできる まあ式を写し間違えて死ぬほどバグらせたんですが

H: それになりうる状態のmaskを持ってDP みたいなやつ たまに見る(ex. 去年のTCOのbreakfastみたいな名前の問題)
実際は状態が少ない 系
慣れてないと実装がちょっと混乱する 集合の集合が出てくるし
元のDPを考えると、DPのキーの集合がキーになる