SoundHound Inc. Programming Contest 2018 (春):D - 建物 を解いたという日記
問題:D - 建物
・DP(H,W)っぽい
・bitDPをしたいけど、制約的に不可能
・「部屋 (1,j) からスタートして(H,任意)から建物を出るときの最大利益」と誤読
・入室回数を出来るだけ減らしたいので、通過or往復で、解説の図のような通行しかしない
<=解説の図
・往復部分は独立に求められそう(本当か?本当だね)
・Tの位置全探索すれば良いけど全探索したくないね(TLE)=>DPの漸化式の中のforをならす一般的なテク
・typo酷いね(基本的にwと2とsが打てなかった)
・Pの処理間違えて悲しいね
・誤読してて悲しいね=>うーん。明らかに逆にたどっても変わらないし(H,j)からスタートして(1,1)から出ることにするか!w
・通ったら暫定8位でウケる(その後落ちた)
Submission #2022867 - SoundHound Inc. Programming Contest 2018 (春)
ところでこれテク的にはDP二回+forならしなのでAGCだと800~1000点くらいで出そう。(サンプル数0)