SoundHound Inc. Programming Contest 2018 (春):D - 建物を解いたという日記

・DP(H,W)っぽい

・bitDPをしたいけど、制約的に不可能

・「部屋 (1,j) からスタートして(H,任意)から建物を出るときの最大利益」と誤読

・入室回数を出来るだけ減らしたいので、通過or往復で、解説の図のような通行しかしない

f:id:eiya5498513:20180128081800p:plain <=解説の図

・往復部分は独立に求められそう（本当か？本当だね）

・Tの位置全探索すれば良いけど全探索したくないね（TLE）=>DPの漸化式の中のforをならす一般的なテク

・typo酷いね（基本的にwと2とsが打てなかった）

・Pの処理間違えて悲しいね

・誤読してて悲しいね=>うーん。明らかに逆にたどっても変わらないし(H,j)からスタートして(1,1)から出ることにするか！ｗ

・通ったら暫定8位でウケる（その後落ちた）

ところでこれテク的にはDP二回+forならしなのでAGCだと800～1000点くらいで出そう。（サンプル数0）