UVaサイトが変わったのはしょうがないけど、ほとんどのブラウザでは表示できないような作り方じゃ、とても恥ずかしいというか、悲しい。今日はとうとう Firefox 2.0.0.16までもダメになってしまった。試しているうちに、Apple社のSafariはまだ使えるので、助かったけど。

1. 問題
 正の整数S (<=8), M (<=20) とN (<=100) はそれぞれ、授業科目数、採用済教師数、採用予定教師数を表す。
 採用済教師も採用予定教師も、それぞれに、雇用コストC (10000<=C<=50000) および教える授業科目リストが与えられる。
 採用済教師は採用しないといけないが、全体の雇用コストが最小、しかも、各授業科目に最低2人の教師がつくように、採用予定の教師をどう採用するか、答えよ。

2. 例
 実例で問題の意味を解説する。

採用済の2人で、2つの授業科目の担当者の一人目が決まり、雇用コストは30000になっている。一人目の採用予定者は、両方の授業科目ともに担当できるので、授業科目にそれぞれ教師二人以上必要という条件が満たされている。雇用コストが30000、採用済教師に支払う雇用コストとあわせて全体的に、雇用コストが60000になる。二人目の採用予定者は雇用コストが高いので、結果的に、採用予定者の一人目だけを採用すればOK。

3. 計算方法
 DPによる方法を考える。
 各授業科目の担当者数をそれぞれ2ビットで表す。0は担当者なし、1は担当者数1, 2は担当者数2以上を示すが、3にならないように気をつけよう。
 雇用コストを配列 p[n][b] (0<=n<=100, 0<=b<=43690、大きさ p[101][43691])で表す。ちなみに、43690 = (1010101010101010)2
 なお、各授業科目に教師二人以上付くという充足条件を配列 goal[9] = { 0, 2, 0xa, 0x2a, 0xaa, 0x2aa, 0xaaa, 0x2aaa, 0xaaaa } とする。

DPの漸化式は以下の通り。

上記の、Cn はn番目予定者を採用する際の雇用コスト、b2はbとn番目の教える授業科目パターンから算出する。
 基本的に b2 = b + n番目予定者の授業科目パターン だが、各2ビットが3にならないように工夫しないといけない。
 また、採用済者全員の雇用コスト p[0][x] は雇用済者リストから算出する。x は採用済者全員の授業科目パターンの合成に相当する。

再び、2の実例で説明する。

配列の初期値 [n][b] = 0 (0<=n<=2, 0<=b<=goal[2]=10)。
採用済者一人目により、x = 1。
採用済者二人目により、x = x+4 = 5。
それで、p[0][5] = 10000+20000 = 30000。
2重ループ n = 1~2、b = 0~goal[2] に入り、
 予定者一人目の不採用により、p[1][5] = p[0][5] = 30000、
 予定者一人目の採用により、p[1][10] = p[0][5] + C1 = 30000+30000 = 60000。
 予定者二人目の不採用により、p[2][5] = p[1][5] = 30000、p[2][10] = p[1][10] = 60000、
 予定者二人目の採用により、(p[2][10] = ) p[1][5] + C2 = 30000+40000 = 70000 の値になりそうだが、60000よりも値が大きいので、結局 p[2][10]の値は60000のままだ;もうひとつ、(p[2][10] = ) p[1][10] + C2 = 60000+40000 = 100000の値も60000を超えたので却下される。
最終的に答えとなる p[2][10] の値は60000となっている。

4. 結果
 長い間放置してきた問題だが、これで解けた。実行時間をもう少し改善したい気持ちもあるが、ビットパターンの計算をもっと簡潔にできるものを先に決めるべきかも。

  0 ? 0 = 0
  0 ? 1 = 1
  1 ? 0 = 1
  1 ? 1 = 2
  2 ? 0 = 2
  2 ? 1 = 2  ← 一番の問題がこちら
になる演算子がほしい!

Comments are closed.

Post Navigation