このサイトは、Real Sakai Lab Advent Calendar 2016の8日目・22日目のために作られたサイトです。

はじめに

毎年5月頃に行われている2年生の学科オリエンテーション内で開催されるプログラミングコンテストについて、来年もあると思われるのでそこで(問題セットに関して)どのような準備をするかを簡単にまとめておき、また2016年のオリエンテーションでは自分はほとんど作問に参加しなかったので、来年はちゃんと主導できるようになりたいという思いから簡単な問題を作って作問の流れを確認しようというモチベーションで書きました(このページに関しては時間と自分のスキルの問題で、割と適当になってしまいました…すみません)。

問題セット準備のために

やらなければいけないことは大きく分けて4つあります。

  1. 問題の案を出す
  2. 模範解答の作成
  3. 入出力ケースの作成
  4. コンテストの時間と難易度などを考慮して、出す問題・その順番などを決める

2016年のオリエンテーションでは8問が出題されましたが、そのうちの6問は実は去年や一昨年の流用でした。なので、今年やった作業はほとんど4だけであり、準備も2,3日前から始めれば終わってしまいました。ということで、来年はさすがにちゃんと問題を用意したいと思った(そうじゃないとまずいことも起こりそうな気がする)ので、今回は上記の1,2,3に該当する部分を簡単な問題を用意してやってみることにしました。

問題作成

案を出すことに関しては、多分普段からストックしておかないと急にそんな複数問も思いつけるものでも無い気がするので、今から少しずつストックすることにしましょうとしか言えないです(アイデアだけでも歓迎しますので、もしこれオリエンテーションにいいんじゃないですかみたいなアイデアがあればぜひ教えてください)。

2と3に関しては、補助してくれる便利なツールがあります。それが今回も利用したRimeというものです。今回はこれを利用して、ランダムケースの作成や、ケースのテストなどを行いました。使い方に関してはドキュメントがまとまってたので、それに沿って使ってみます。

まず、”プロジェクトディレクトリの構成”にある通り、1つのプロジェクトディレクトリに対して複数の問題ディレクトリがあるような構成を取ります。そして、そのディレクトリ内には解答となるコード、入力生成器(generator)、出力検証器(validator)、手動で作成したケースなどを入れます。

なお、今回作って見て初めて気づいたのですが、あとで書く2問目のような制約の異なるデータセットを用意したい場合には、各制約ごとにディレクトリを分けないと検証がしにくいということがわかったので、次回からは初めからそのようなディレクトリ構成にしようという知見が得られました。

ということで、今回試しに2問作ってみたので、拙作ですが、お楽しみください！(今回、自動でdiffを取って確認するとかそういうのができるやつを用意できればよかったんですが、準備できませんでした。それぞれ入力と対応する出力を用意しておくので、手元で確認してみてください…また、その辺に詳しい方がいたら教えてください…)

(遅くなってすいません。23日に公開しました。)

A - RSLにようこそ

Problem Statement

　「ぼく」は来年研究室に配属されることになりました。「ぼく」の行きたいRSL研究室の定員はN人なのですが、幸か不幸かRSL研究室はとても人気で事前調査では希望者がM(>N)人いることが分かりました。研究室配属は成績が全てです。「ぼく」の成績はAですが、「ぼく」よりも成績のよい希望者がN人以上いると、「ぼく」は希望の研究室への配属が叶いません。

　それはどうしても嫌だったので、「ぼく」はこっそりとM人の成績の情報を入手し、同級生の中でも影響力の強い友人にお願いして、「RSL研究室は成績がX以上じゃないと入れない」という情報を流して、成績がX未満の希望者に諦めさせて自分が確実にRSL研究室に配属されようという陰謀を企てました。ただし、Xが高すぎてもその情報は嘘なのではないかと思われる心配があったので、できるだけXは小さい数字に設定することにしました。「ぼく」の設定したXの値を求めてください。

Input

入力は複数のデータセットからなり、1行目にはデータセットの数Dが与えられる。

そして、1つのデータセットは以下の形式で与えられる。

N M A
S1 S2 ... SM

Nは研究室の定員、Mは研究室配属希望者の数、Aは「ぼく」の成績、Si (1 ≤ i ≤ M)はi番目の配属希望者の成績を表す(この成績の中には自分も含まれています)。

N, M, A, Si (1 ≤ i ≤ N) は整数で与えられ、以下の制約を満たす。

Output

各データセットに対して、「ぼく」の設定すべきXを出力せよ。ただし、Xとして設定できるのは成績としてありえる範囲でなければならないので、0 ≤ X ≤ 100000である必要がある。どのようなXを設定しても「ぼく」が配属されることが出来ない場合には-1を出力せよ。

Sample Input

2
2 4 8
3 9 8 10
1 3 100
100 2 5

Sample Output

10
0

Dataset

Download

B - ゼミ

Problem Statement

　「ぼく」の所属する研究室には「ぼく」も含めて同じ年にN人の生徒が配属されました。ゼミではそのN人を2つのグループに分け、隔週でどちらかのグループが発表を行います。生徒たちは非常に優秀なので、発表の準備がバッチリです。自分の発表に何分かかるのかを、完璧に把握しています。

　研究室のみんなは、あまりにもゼミが早く終わったり、逆に長引くのも嫌なので、この2グループの発表時間の合計の差ができるだけ少なくなるようにグループ分けをすることにしました。

　発表のグループを2つに分けたときに、発表時間の合計の差の最小値を求めてください。

Input

入力は複数のデータセットからなり、1行目にはデータセットの数Dが与えられる。

そして、1つのデータセットは以下の形式で与えられる。

N
M1 M2 ... MN

Nは生徒の数、Mi (1 ≤ i ≤ N)はi番目の生徒の発表時間を表す。

N, Mi (1 ≤ i ≤ N) は整数で与えられる。この問題ではデータセットが3種類あり、それぞれでは以下の制約を満たす。

データセット1

データセット2

データセット3

Output

各データセットに対して、発表時間の合計の差の最小値を出力せよ。

Sample Input

2
3
17 14 22
6
1 1 4 5 1 4

Sample Output

9
0

Dataset

データセット1

Download

データセット2

Download

データセット3

Download

解説

(遅くなってすいません…)

各問題ごとに、簡単な解説を書きます。実際のコードは、私が模範解答用に用意したC++のコードへのリンクを貼るので、興味がある方はそちらも合わせてご覧ください。

A - RSLにようこそ

この問題はM人の成績表が与えられて、その成績表において「同じ成績の人はいない。」ことが保証されています。よって、その成績表をソートし、眺めることによって「ぼく」の成績は上からN番目以内に入っているのかどうかがわかります。

上からN番目以内に入っているのであれば、何も情報操作をする必要などないので、成績の値の中で取りうる最低の値0が答えとなります。 では、そうでなかった時はどうすればよいかというと、情報操作のための数字Xはできるだけ小さくしたいので、「ぼく」はN番目でギリギリ入ることができれば良いということがわかります。つまり、成績が上からちょうどN番目の人が諦めてくれるような数字Xを設定するのが良いわけです。そのようなXの中で最小の値と出来るのは(成績が上からちょうどN番目の人の成績)+1ということになります。

ただし、ここで注意が必要なのがこの(成績が上からちょうどN番目の人の成績)が最高の100000だった場合、ぼくの設定できるXは存在しないので、-1と答えなければなりません。

B - ゼミ

この問題は3つのデータセットに分かれ、それぞれで制約が異なります。よって、それぞれに対して異なるアプローチを取ることになりますが、どれにも共通して言える、問題を解くためのポイントがあります。それは、「片方のグループの発表時間の合計が決まれば、もう片方のグループの発表時間の合計も一意に決まる」ということです。グループが2つしか無いので、当たり前のことです。それではこのことを念頭に、データセットに対する解説に移ります。

データセット1

このデータセットは、データセット2にもデータセット3にも内包されているのでこれ用の解答コードを用意していません。Nが非常に小さいので、片方のグループをどのようなメンバー構成にするかを全探索することができます(全部で2^N通り)。再帰で書いてもいいですし、ビットで集合を表してループを回して全探索しても良いでしょう。

データセット2

このデータセットでは、上のように全ての組み合わせを試すことが出来ません。ここでは、1人あたりの発表時間が少ないことに注目します。最大でも20000までです。これに注目しすれば、片方のグループの発表時間はたかだか20001通りになることがわかります。2^Nよりだいぶ少ないですね。さて、それでは片方のグループの発表時間としてありうるのはこの20001個のうちどれなのかが知りたいです。

そこで、片方のグループに注目し、人を順番に見ていったときにその人をグループに入れるか否かを選択していくような状況を考えます。そこでメモ用のテーブルとしてdp[i][j] = i番目の人までグループを決定し終えた時、グループの合計時間はj分であることはあり得るか否かという配列を用意して、到達可能な状態を伝播させていくことを考えましょう。

例で考えてみましょう。Sample Inputでは3人の発表者がいて、それぞれ17,14,22です。

まず、まだ1人も決まってない時点では発表時間は0に決まってますから、dp[0][0]=trueで初期化されます。

さて、1人目に注目すると、時間は17です。なので、1人目まで決め終わった時点では、この人をグループに入れない時を考えるとdp[1][0]=trueになり、入れるときを考えるとdp[1][17]=trueとなります。

次に2人目に注目します。すると前までの段階で0と17には到達可能のようです。そこで、2人目を入れないときを考えるとdp[2][0]=true,dp[2][17]=trueとなります。入れるときを考えると時間は14なのでdp[2][14]=true,dp[2][31]=trueとなります。

この要領でi番目に注目している時にはi-1番目が決定しているので、その情報を利用して情報を伝播していくことができるようになります。

そして、最終的にはN人に対してこれを行うので、dp[N][i]というところにそこに到達可能かどうかが入っているわけです。iと選んだ時にはもう片方の発表時間は全体から引けば分かりますから、dp[N][i]が到達可能であり、差が最小になる時の差を答えとすればよいことがわかります。

データセット3

先程のように、合計時間に注目することは出来ないほど大量の発表時間になってしまいました。そこで今度は人数が少なめなことに注目します。ただし、単純に全通りを試すのでは、最悪の場合、2^35 = 34359738368 通りを考えないといけないので、かなり時間がかかってしまいます。

そこで、このN人を半分に分けます。前半のA(=N/2)人と後半のB(=N-A)人に分けることにしましょう。この半分に分けた段階で最大でも18人なのでこれに対しての全探索は2^18 = 262144 通りと十分高速に動かせそうです。さて、それでは、前半のA人で、どのような値を作れるかをここで2^A通り列挙しておきます。

次に後半のB人についても全通りを考えていきます。これは2^B通りになります。今、合計時間がbだったとします。ここで、前半で列挙した2^A通り(合計時間a)との組み合わせをすべて試してa+bを求めて全体を求めているのでは結局最初にやっていた全探索と同じことになってしまいます。ただ、この場合明らかに無駄が多いです。なぜなら合計時間の差はできるだけ少なくしたいので、全員の発表時間をSUMとすると、片方のグループはできるだけSUM/2に近づけたいことになるから、aはSUM/2 - bにできるだけ近い値だけ見られれば十分なわけです。そのような値を検索する方法として、元の列がソートされていれば二分探索によってO(log(2^A))で実現することが可能になります。自分で二分探索を実装しなくても、言語によってはSetなどにこのような機能があるかもしれません。

ちなみに、この半分に分けるテクニックは競技プログラミング界隈では「半分全列挙」という名前が付けられています(このワードで検索してみると競技プログラミングに関連したページばかりが見つかるので、あまり一般的な言い方ではないかもしれません)。