JOI本選 - つらら古本屋夜店

11-22 に解いた問題

古本屋は自分にとってちょうどいい難易度で良問でした。

本選の難易度6はあと4問になりましたのでね、

JOI 2010 本選3問目

問題

N本のつららがあり、i 本目のつららが i - 1本目のつららと i + 1本目のつららより長い時に i 本目のつららは1時間のに1cm伸びる。L cmに達したつららは折れ、0cmのつららとみなされる。全てのつららが折れるのは何時間後か。

最初のつららの長さ a_i cm (1 <= i <= N)

解法

もっとも長いつらら i が折れるのは L - a_i、2番目に長いつらら j が折れるのはもっとも長いつららが隣にあった場合は L - a_i + L - a_j、そうでなければ L - a_j となるので、もっとも長いつららから折れる時間を計算していけば解が求まる。

大きい値を順に取り出すのでpriority_queueを使う

コード

JOI 2011 本選2問目

問題

本をN冊持っており、そのうちK冊を売りたい。JOI古本屋では本を10種類のジャンルに分けており、同じジャンルの本をT冊まとめて売ると、そのジャンルの本1冊あたりT - 1円安くなる。

本のジャンルともとの買い取り価格が与えられた時、最大の売値はいくらか。

解法

考察として、同じジャンルの本が4冊あり、それぞれの買い取り価格が 100, 200, 400, 500だった時にそこから3冊売るのであれば、どの組み合わせでも(3 - 1) * 3で6円高くなる。

売る冊数が同じであれば増える金額は同じなので、(100, 200, 400)を売るよりも、 (500, 400, 200)の本を売った方が買い取り価格は当然高くなる。

ジャンル i の本の j 冊目を v[ i ][ j ]として、それぞれのジャンルでソート、j冊目までの買い取り価格のテーブルを作っておいてからあとは単純なDP

コード

JOI 2012 本選3問目

問題

祭りに夜店が N 個あり、それぞれ楽しさが a_i で遊ぶのにかかる時間は b_i である。祭りは時刻 T に終わるのでその時間を過ぎて夜店で遊ぶことはできない。また、時刻 S には一番大きな花火が打ち上がるのでその時刻に夜店であそんでいてはいけない。夜店で遊んだ合計の楽しさの最大を求めよ。

解法

夜店の数 N 、終了時刻 T ともに3000以下と小さいのでテーブルを更新していくだけで求まる。O(NT)。

コード

Luzhiled's memo