olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

2017-05-14から1日間の記事一覧

ビンゴ(09予選6)

N*Nのビンゴに1~Mまでの数字を入れる。和をSにしないといけないという条件の下で、何通りのカードが作れるかな?という問題。 dp[i個の数字で][jを作る]通り数のDPを組む。大きいものから見ることで1次減らせる。 計算量はO(NMS) 難易度は7程度に感じられた。…

最悪の記者(07本選4)

Nチームがリーグ戦を行った。M個の勝敗の情報が与えられたとき、順位表のうちの一つを出力せよ。という問題。 なお、引き分けの試合はなく、同順位のチームもなく、順位が上のチームが下のチームに負けなかったことが保証されている。 勝ったチームから負け…

夜店(12本選3)

N個の屋台をT時間の間に遊びたい。また、時刻Sの時に花火もみたい。 一つの屋台で遊ぶ時の楽しさと時間が与えられるので、楽しさを最大化しようという問題。なお、屋台は番号の若い順にしか回れず、一つの屋台では一度しか遊べない。 N個目までの屋台につい…

スタンプラリー2(16本選2)

N個の店があり、それぞれJかOかIが決まっている。3店を選んでJOIを作る。 なお、3店は番号の小さい順に選ぶ必要がある。 ここで、任意の場所に任意の文字の店を一つ追加して、JOIを作る通り数を最大化したいという問題。 まず、最初の段階でJOIの通り数を数…

オレンジの出荷(16本選1)

N個のオレンジがあり、それぞれ大きさが決まっている。一個の箱には最大でM個オレンジを詰められ、箱に詰める際のコストはK+num*(MAX-MIN)で求められる。 (numは箱に詰めたオレンジの数。MAX,MINは箱に詰めたオレンジの大きさの最大値、最小値) コストを最小…

ケーキの切り分け2(15本選2)

N個に切られたホールケーキがあり、それぞれの大きさが与えられる。 先攻はまず好きなピースを取り、それ以降後攻は空間が隣にあるケーキの内で大きいほうのケーキを、先攻はそのようなケーキの内好きなほうを取る。 先攻の大きさを最大化しようという問題。…