人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

JOI '13 春合宿4:2 - プレゼント

問題

http://imoz.jp/data/joi/2013-sp-d4-presents.pdf

解法

学生を頂点,プレゼントをあげる関係を有向辺で表すと,ループ状の頂点の集合とループにつながる一本道の構造が1つか複数できることが分かる.ループ上では,自分のプレゼントと違うものをプレゼントされる方が嬉しい人が偶数人いれば,その中では嬉しさを最大化できる.もし,奇数人いる場合は,一人が嬉しさを減少させればその中で嬉しさを最大化できるので,嬉しさを減少させる人を選ぶ必要がある.これは,嬉しさの減少が最も小さい人を選べばよい.メモ化再帰などを使って O(N).

解答

beta.atcoder.jp

解法でも書いた「ループ上で」のところの処理で実装ミスをしていて,6の字型にループが判定されてしまうバグを埋め込んでしまい 17 WA した.

f:id:babcs2035:20181126211750p:plain