アルゴリズムの問題にチャレンジ!
本記事は @_tanzaku_氏主催の、Competitive Programming Advent Calendar の記事です。
簡単な問題を作問したので、出題してみます。
ぜひチャレンジしてみてください!
Problem Statement
今年もクリスマスの季節がやってきた。クリスマスと言えばアドベントカレンダー。アドベントカレンダーとは、12月1日から、クリスマスの12月25日まで毎日窓を開けていくカレンダーのことである。それにちなんで、アドベントカレンダーイベントでは、参加者は一人一日ずつブログ記事を発表する。最初の参加者は12/1に、次の参加者は12/2に、といったように、a人目の参加者は12/a日(1 <= a <= 25)に記事を発表する。
あなたは競技プログラミングをテーマとしたアドベントカレンダーイベントを主催することにしたが、この企画は大変人気を博し、参加希望者数が25名を上回った。だが、なるだけ多くの人に参加してほしいとの思いから、1日に2つ以上の記事ができてもよいことにし、希望者全員が参加できるようにした。ここであなたは、各参加者を(各々が記事を発表する日である)1つの日付に割り当てなければならない。
ここで、あなたのタスクは参加者を適切に割り当てることでこのイベントにおける「(12/1から12/25までの中で)一日に発表される最大記事数」を最小化し、その値を出力するプログラムを書くことである。なお、参加者の中には「特定の日付以降に割り当てて欲しい」と言う者もいる。イベントの主催者であるあなたはすべての参加者の希望を満たすように割り当てを行う必要がある。
Input
入力は次のようなデータセットから構成される。
n x1 x2 ..... xn
各データセットは n という正の整数から始まり、 1 <= n <= 1000 と仮定して良い。nはイベントの参加者数を表す。nの次の行には参加者データが続き、これらが各参加者の情報を表している。参加者データは半角スペース区切りの xi(1 <= xi <= 25) という正の整数n個で表され、この参加者は「xi日目以降に割り当てて欲しい」ことを示す。入力の終わりは 0 で表す。
入力の各データセットに対して、「一日に発表される最大記事数の最小値」を1行に出力せよ。
Sample Input
26 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 25 25 25 25 31 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 20 20 20 20 1 25 0
Expected Output for Sample Input
2 5 2 1
データセット1
25人目までを1 〜 25日に、26人目をいづれかの日に割り当てることで最大記事数は最小になり、その値は 2 となる。
データセット2
24人目までを1 〜 24日に、25人目以降を25日に割り当てる。
データセット3
参加者データは日付順に並んでいるとは限らない。
データセット4
㍆㌋㌉㌏㌉㌸㌾㌋㌞㌹㌅
Judge Data
補足
参加者の要望を、「xi日以降かつyi日以前」とする問題も思いついたのですが、ゴリゴリ全探索する以外の効率的な解法がわかりませんでした。
そちらの問題の解法も募集しています。