babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング JOI 難易度８問題 問題 解法 解答 問題 http://imoz.jp/data/joi/2013-sp-d4-presents.pdf 解法 学生を頂点，プレゼントをあげる関係を有向辺で表すと，ループ状の頂点の集合とループにつながる一本道の構造が１つか複数できることが分かる．ループ上では，自分のプレゼントと違うものをプレゼントされる方が嬉しい人が偶数人いれば，その中では嬉しさを最大化できる．もし，奇数人いる場合は，一人が嬉しさを減少させればその中で嬉しさを最大化できるので，嬉しさを減少させる人を選ぶ必要がある．これは，嬉しさの減少が最も小さい人を選べばよい．メモ化再帰などを使って O(N)． 解答 beta.… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2018%2F11%2F26%2F211806" title="JOI &#39;13 春合宿４：2 - プレゼント - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20181126/20181126211750.png Hatena Blog https://hatena.blog 2018-11-26 21:18:06 rich https://babcs2035.hateblo.jp/entry/2018/11/26/211806 1.0 100%