雑記

競技プログラミングについての話題(?)

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

11-22 に解いた問題

 

つらら | Aizu Online Judge

古本屋 | Aizu Online Judge

夜店 | Aizu Online Judge

 

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

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

 

JOI 2010 本選3問目

 

つらら | Aizu Online Judge (AOJ0551)

 

問題

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を使う

 

コード

AIZU ONLINE JUDGE: Code Review

 

JOI 2011 本選2問目

 

古本屋 | Aizu Online Judge (AOJ0561)

 

問題

本を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

 

コード

AIZU ONLINE JUDGE: Code Review

 

JOI 2012 本選3問目

 

夜店 | Aizu Online Judge  (AOJ0573)

 

問題

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

 

解法

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

 

コード

AIZU ONLINE JUDGE: Code Review