Codeforces Beta Round #4
#3でいろいろしくじって士官になれなかったので適当に参加しました。まだまだBetaなので遅延がひどかったです。
A,B,Cは適当。Dも順序関係が定まるので、DAGを作って最長経路を探すだけ。TopologicalSortしてDPでもいいし、DFSのときにまとめてやってしまってもOK。しかし、DFSでメモり忘れて指数オーダー投げてました。4完48位で尉官になりました。
ちなみにグラフ作るのにO(n^2)かかるので、DFSのときにまとめてやってもオーダー変わりません。
(追記)
- Aの再提出:問題文読み間違えた
- Dの再提出(1):最終行を失念した
- Dの再提出(2):メモし忘れた