selpo's diary

主に競プロの解説をします。C#erです。

問題B『DDPC特別ビュッフェⅡ』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

冷静に考えればそこまで難しくはないのですが、
朝だと頭が働かず、本番中には解けませんでした。

問題文 : DDPC特別ビュッフェⅡ

概要

N種類の料理があり、i番目の料理は時刻T_iまでしか食べられない。
また、それぞれの料理にはスコアA_iが決まっており、一度食べたらなくなる。
それぞれの時刻(t\geq 1)ではt\leq T_iの料理をひとつ選んで食べることができる。

うまく食べる料理を選ぶとき、スコアの合計をX以上にするのに必要な時間の最小値を出力せよ。
どうやってもX以上のスコアにできなければ、-1を出力せよ。

制約

1\leq N\leq 10^5
1\leq T_i\leq 10^5
1\leq A_i\leq 10^5
1\leq X\leq 10^9

解説

美味しい料理から食べていけばよさそうだが、制限時間の緩い(T_iの大きい)料理は後回しにしたい。
どれくらい後回しにできるか、とか考えるといろいろと面倒(←何回もバグりました)。

続きを読む

問題A『DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016 Ⅱ』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

めっちゃ簡単ですが、最初の記事ということで。

問題文 : DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016 Ⅱ

概要

順位に応じて以下のように賞金が決まっている。

1位: 100000
2位: 50000
3位: 30000
4位: 20000
5位: 10000
6位以下: 0

また、N人のうち、i位であった人の番号Id_iが順に与えられる。
番号順に、獲得した賞金を出力せよ。

制約

5\leq N\leq 100
1\leq Id_i\leq N

解説

Id_i=kの人の賞金B_kを問題文の通り求めて出力するだけ。
計算量はO(N)

続きを読む

はじめまして

競技プログラミングにおいて解いた問題の解説を書くことの利点について - うさぎ小屋
うさぎ小屋さんに触発されて、競プロの解説を始めました。
もともと解説を書いてみたいなぁというのはあったんですけどね。

ただ、C#しか書けないので、悪しからず。
とりあえず、昨日参加したDDPCの解説から始めようと思います。