1. 問題
高速性が要求される問題のひとつ。N (3<=N<=5000) 個の入力データから、任意の3つ (x, y, z) を選んで、x+y=z となるTripleの数を求めよ。
なお、入力データはすべて正の整数、32ビット範囲内に収まる。プログラムの実行制限時間が8秒。

2. 実例
次の入力データをみてみる。
1 2 3 4 5 6

1+2=3, 1+3=4, 1+4=5, 1+5=6, 2+3=5, 2+4=6 になるので、答えは6になる。

3. 計算法
入力データの個数が5000までなので、一見簡単に解けそうだが、やってみて、大変さが分かった。出題者の意図は O(n^2) アルゴリズムの提出にある。

自分の順位は現時点では18位なので、まだまだ改善するところを考えないといけないが、つぎのような方法でやってきた。

入力したデータに対し、ソートを行い、グループ化を行う。グループ化というのは、同じ値の入力データをまとめることだ。たとえば、1 1 1 2 2 3 3 という入力データを (1,3) (2,2) (3,2) にクループ化する。ソートにはO(nlogn)、グループ化には O(n) で済むが、ソートの高速化は問題として残っている。

次に、ソートされ、グループ化されたデータに対し、Tripleの数を算出する。

言葉で説明するのが面倒なので、ソースプログラムを使う。勿論分かりやすくするため、一部を書き換えているし、もっと高速化できるところもある。この部分の実行時間はO(n^2)。なお、ans変数は64ビット整数(long long int)でないとオーバーフローになってしまう。

typedef long long llong;
#define SIZE  5000
int N;
unsigned data[SIZE+5];  /* 入力データ(ソート済み) */
int freq[SIZE+5];  /* 同じ値を持つ入力データの個数 */
ans = 0;
if (N == 1) { puts("0"); exit(1); }
for (k = 1; k < N; k++) {
    i = 0; j = k-1;
    while (i < j) {
        if (data[i]+data[i] == data[k]) {
            ans += (llong)freq[i]*(freq[i]-1)/2*freq[k];
            break;
        }
        if (data[j]+data[j] == data[k]) {
            ans += (llong)freq[j]*(freq[j]-1)/2*freq[k];
            break;
        }
        if (data[i]+data[j] == data[k]) {
            ans += ((llong)freq[i])*freq[j]*freq[k];
            i++, j--;
        } else if (data[i]+data[j] &lt; data[k]) i++;
        else j--;
    }
}
printf("140733424702768\n", ans);

4. スピードの改善
スピードを上げるために、データのソートとグループ化に、2分探索木を使ってみた。順位は14に上がったが、劇的な改善にまだ繋がっていない。最後のtriple数の計算がボトルネックになっているから。

2分検索(バイナリサーチ)のような手法が使えるのではないか、そんな気がしている。ランク1位の時間は0.540秒なので、自分としてはせめて1秒を切りたい。

元問題

余計なことは書かない。一生懸命導いた数式の結果だけをメモしておく。

p11250.jpg

あとは、入力データのm, nに対し、それぞれ多倍長整数(本ブログ参照)を使って、上記の通り、分子、分母に分けて計算し、最後に、ユークリッド互除法で分子、分母を約分し、結果を得る。

数式のネット検索は、Googleといえども、まともにできない。入力の仕方にも、使う変数の文字にも、可変要素が多すぎるかな。

ソースプログラムAを書いて、それをコンパイルして実行可能なプログラムBができあがる。プログラムBを実行したら、画面上の表示内容がAそのものになっている。

そういうソースプログラムAを自己印刷プログラムという。英語ではQuineという。

自己印刷プログラムはふつう、入力を使わない。入力ファイルを画面表示するだけなら簡単に作れるから。

C言語で作られている自己印刷プログラムに以下のようなもの2つがよく知られている。

main(a){printf(a,34,a="main(a){printf(a,34,a=0`,34);}",34);}

 

char*f="char*f=0`;main(){printf(f,34,f,34,10);} ";main(){printf(f,34,f,34,10);}

以下のものは多少長いが、いろいろ応用利きそう。

char*lines[]={
    "char*lines[]={",
    "0` ",
    "0};",
    "main(){",
    "int idx;",
    "puts(lines[0]);",
    "for(idx=0;lines[idx]!=0;idx++){",
    "printf(lines[1],34,lines[idx],34,',',10);",
    "}",
    "puts(lines[2]);",
    "for(idx=3;lines[idx]!=0;idx++){",
    "puts(lines[idx]);",
    "}",
    "}",
    0};
main(){
    int idx;
    puts(lines[0]);
    for(idx=0;lines[idx]!=0;idx++){
        printf(lines[1],34,lines[idx],34,',',10);
    }
    puts(lines[2]);
    for(idx=3;lines[idx]!=0;idx++){
        puts(lines[idx]);
    }
}

自分自身を表示する。哲学的な要素が含まれ、なかなか奥深い。

1974年度のチューリング賞を受賞したクヌースの受賞講演「芸術としてのプログラミング」にも、

 数年前、Stanford大学の学生たちは、自分自身を印刷する最短のFORTRANプログラムを見つけようとはりきったこともあります。

とわざわざ紹介してある。

平方数とは平方根が整数の数のことだ。小さい順で並べていくと、0, 1, 4, 9, 16, 25, 36, … となる。あるいは、素因数分解して、すべての素因数の指数が偶数である場合も平方数になる。たとえば、36 = 22x32、素因数の指数がそれぞれ2であるので、36は平方数といえる。平方根を計算することは結構時間がかかるので、素因数が分かるのであれば、素因数の指数を調べるほうがはるかに高速。

1. 問題
 n (0<n<=200000) 個の整数(絶対値は1018よりも小さいが、すべての素因数は30以下。)が与えられた時に、n個の中から任意の2つを選んで、その積が平方数となる(組合せの)数Xを、n個の中から任意の3つを選んで、その積が平方数となる(組合せの)数Yを求め。

2. 実例
 例をもって説明する。
 たとえば、3つの整数 2, -2, 2 が与えられた時、2×2 = 4 になるので、X = 1。また明らかに Y = 0。
 簡単だな、と思うかもしれないが、データの個数が20万、個々のデータの値の大きさを考えると、そう容易く解けないはずだ。しかも、実行時間は3秒に制限されている。
 20万個のデータすべてをここに書き出すことは非現実的だが、20万個のデータが何百組も与えられても、3秒以内に計算を終了させ、正解を出すプログラムを作ることが簡単ではない。すべては高速性にかかってくる。

下は多少複雑な例。それでもデータの個数は100でしかない。

100
64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117
649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826
809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 470
45881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889
594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729
15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 17
71561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24
137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881
148035889 594823321

答えは、X=4950 Y=161700。

3. 計算法
 まず、1~2500000の間の、素因数が30以下のすべての値に対し、エラトステネスのふるいを応用して、素因数分解をしておく。2500000を超えた入力値に対しては、単純に1つ1つ素因数分解をしておく。
 ただ、本問題では素因数の指数の奇偶性が問題になるので、個々の素因数に対応して、以下のビットパターンを採用する。

 最下位ビットから bitpat[11] = { マイナス, 2の数&1, 3の個数&1, 5の個数&1, 7の個数&1, 11の個数&1, 13の個数&1, 17の個数&1, 19の個数&1, 23の個数&1, 29の個数&1 };

 「マイナス」はデータが負数を表すビット、
 「2の数&1」は素因数2の指数が奇数なら1、偶数なら0になる。
 「3の数&1」は素因数3の指数が奇数なら1、偶数なら0になる。
などを意味する。

 例えば、6のビットパターンは110、-6のビットパターンは111、10のビットパターンは1010、平方数のビットパターンは0。

 データの積を取ることは、すなわち、ビットパターンの XOR 計算にほかならない。そのXORの結果がゼロになれば平方数、ゼロ以外であれば非平方数となる。

 また、入力データを値がゼロのものとそうでないものに分ける。値がゼロのデータの数がzだとすると、XとYに相当する部分は以下のように算出する。

  X = nC2n-zC2 = z(2n-1-z)/2
  Y = nC3n-zC3

あとは、値がゼロ以外のデータについてのみ、XとYの値を算出し、上の値に足し加えておけばOK。

4. 結果
 書くのは嫌になるほど、多くのことをトライして、最終的に実行時間を0.480秒に押さえ、現時点でのランク1位にできた。

細かいことは省略するが、ヒントになるものをリストアップしておく。

  1. 入力の値に対するビットパターンは2047以下。つまり、異なる入力データの数は2048通りしかない。
  2. XOR計算 a^b = 0 となるa, bは、a = bに限る。a^b^c = 0となるa, b, cは a^b = c に限る。従って、異なる2048個の値から、任意の2つを取り出してXORがゼロになる計算は2048回(O(n))で済むし、任意の3つを取り出してXORがゼロになる計算は2048×2048回(O(n2))で済む。
  3. 入力データを平方数と非平方数に分けた。平方数同士では、XORがゼロになる。平方数と非平方数とのXORはゼロにならない。非平方数と非平方数とのXORがゼロになるのは、その2つの非平方数が等しい場合に限る。
  4. 入力データの処理にscanf()ではなく、read()関数を使った。getchar()を使ってランク2にできたが、1位になるには、read()を使ってしまった。
  5. 計算のオーバーフローに気をつけよう。整数同士の積に64ビット整数を使おう。

5. ソースの一部

typedef long long llong;
typedef unsigned short ushot
#define MAX    2500000
ushot bitpat[MAX+5];
ushot pp[10] = { 2,3,5,7,11,13,17,19,23,29 };
/* 1~MAXまでの各整数に対するビットパターン */
void sieve(void)
{
    register int i, j;
    int k, p;
    ushot b;
    for (k = 0; k < 10; k++) {
        p = pp[k], b = 1 << (k+1);
        for (j = p; j <= MAX; j *= p) {
            for (i = j; i <= MAX; i += j) {
                if (bitpat[i] & b) bitpat[i] &= ~b;
                else               bitpat[i] |= b;
            }
        }
    }
}
/* MAXを超えた値に対するビットパターン */
ushot factor(llong n)
{
    int k, p, m;
    ushot ans;
    ans = 0;
    if (!(n & 1)) {
        m = 0;
        do n >>= 1, m++;
        while (!(n & 1));
        if (m & 1) ans |= 2;
    }
    for (k = 1; n > 1 && k < 10; k++) {
        p = pp[k];
        if (!(n  0x7fff0dc99530)) {
            m = 0;
            do { m++; n /= p; }
            while (n  0x7fff0dc99530 == 0);
            if (m & 1) ans |= 1 << (k+1);
        }
    }
    return ans;
}

XとYを算出する部分(分かりやすくするため、ソースの一部を書き直した。ソースそのものとは異なる)。なお、freq[a]はビットパターンがaである入力データの個数を示す。

X = Y = 0;
for (i = 1; i < 2048; i++) {
    if (freq[i]) {
        X += ((llong)freq[i]*(freq[i]-1))/2;
        for (j = i+1; j < 2048; j++) {
            if (freq[j]) {
                if ((i^j) > j && freq[i^j]) Y += (llong)freq[i]*freq[j]*freq[i^j];
            }
        }
    }
}

1. 問題

p11200.jpg

上記の通り、各セルには必ず、右下あるいは左下斜めの壁が置かれる。迷路の入口は上、出口は下。左右両側は通行禁止。こういう条件の下で、入口から出口までの異なる通路は果たして何本あるか。ちなみに、右上の迷路では通路が3本、左下の迷路では通路が1本という結果になっている。

2. 入力データの例
 上記の左下迷路に対応する入力データは以下の通り。大きくなると、目視での確認は相当きつい。¥は本来はバックスラッシュ\、右下斜めを表しているはずなのに。

1 ← 入力データの数
15 10 ← それぞれ列数、行数を表す
////\\\////\\// ← 迷路
/\\\\\/\/\/\\/\
\\\//\\\/\////\
//\\\/\///\//\\
\/\//\\/\\\\/\\
////////\\///\/
\\\\\\//\\\\\/\
\\/\//////\\///
\/\\/////\/\/\/
\///\///\\\\//\

3. 計算法

p11200-2.jpg

セル(r,c)に位置することは、そのセルの下の端の中央にいることと考える。そうすると、周りの壁の形によって、上記の8通りの進み方がある。

証明はまだしていないが、入口1箇所に対応する出口は高々1箇所。従って、1つの入口に入って探索していき、出口ひとつに出くわしたら、それ以降の探索は打ち切り、つぎの入口から探索し続ける、という戦略を取って問題なさそう。また、異なる入口から入り、最終的に同じ出口にいく通路もないと推測する。

1. 問題
 様々なサイズの長方形(または正方形)の紙Aが与えられている。1枚の紙Aを、折り紙するための4枚の正方形Bに切り分けたいけど、もっとも大きな折り紙Bが得られるような、最適なAがどれかを選べ。

2. 実例
 以下の実例を見てみる。

3 ← 与えられる紙の数
10 20 ← 1枚目の紙 10 x 20
40 8 ← 2枚目の紙 40 x 8
12 12 ← 3枚目の紙 12 x 12 の正方形
0 ← 入力データの終了

1枚目の紙10×20では最大5×5の折り紙しか得られない。2枚目の紙40×8では最大8×8の折り紙が得られる。3枚目の紙12×12では最大6×6の折り紙しか得られない。ということで、2枚目の紙を選べば、最大サイズの折り紙を手にすることができるわけだ。

3. 計算法
 縦幅に比べ、横幅の短くない長方形(または正方形。そうでなければ90°回転すればOK)に対して、最大サイズの折り紙(正方形、同一サイズ)4枚は3通りの並び方にしかならない。

p11207.jpg

長方形の縦幅サイズをY、横幅サイズをXとすると、3パターンによって得られる折り紙の最大サイズはそれぞれ、

 パターン1: X/4 と Y の小さいほうの値
 パターン2: X/2 と Y/2 の小さいほうの値
 パターン3: X/3 と Y/2 の小さいほうの値

になる。3パターンに対応する3つのサイズから、最大サイズを得、それが長方形 X, Y に対して入手できる折り紙の最大サイズになる。

さらに、与えられたすべての紙の中から、最大サイズのものをピックアップすれば、答えが得られる。

ということで、本問題は簡単に解ける。残りは実行時間の短縮ということだ。

自分の書いたプログラムは最初0.020秒だったけど、最適化を施し、最終的に0.000秒に到達した。つまり、乗算、除算しないで、ビットシフトでの計算を心がけた。

例えば、元のサイズX, Y を最初から12倍すれば、2, 3, 4で割り切れるので、実数ではなく、整数だけで計算可能になる。

となると、3つのパターンはそれぞれ

 パターン1: min(3X, 12Y)
 パターン2: min(6X, 6Y)
 パターン3: min(4X, 6Y)

に変わり、ビットシフトの性質を考えて、

 3X = (X << 1) + X  4X = X << 2  6X = 3X << 1
 3Y = (Y << 1) + Y  12Y = 3Y << 2

などと工夫すれば、除算も乗算も必要なくなる。

まあ、そんなテクニックは実行スピードの本質的な改善に繋がらないから、分からなくても構わないが、少しでも他人よりもランクを上げたい気持ちがあれば、覚えて損することはないだろう。

2以上の整数nについて、その素因数の和sf(n)の計算法を考える。

例えば、2 = 2 なので、sf(2) = 2。
6 = 2*3 なので、sf(6) = 2+3 = 5。
8 = 2*2*2 なので、sf(8) = 2+2+2 = 6。

2から30までの整数についての sf(n)の値は以下の通り。
2,3,4,5,5,7,6,6,7,11,7,13,9,8,8,17,8,19,9,10,13,23,9,10,15,9,11,29,10.

#include <stdio.h>
#include <string.h>
#define MAX 500000
#define ROOT_MAX 707
int sf[MAX+1];
void sieve(void)
{
    register int i, j, k;
    /* memset(sf, 0, sizeof(sf)); */
    for (j = 2; j <= MAX; j <<= 1) {
        for (i = j; i <= MAX; i += j) sf[i] += 2;
    }
    for (k = 3; k <= MAX; k += 2) {
        if (sf[k] == 0) {
            for (j = k; j <= MAX; j *= k) {
                for (i = j; i <= MAX; i += j) sf[i] += k;
                if (k > ROOT_MAX) break;
            }
        }
    }
}

計算できる最大値 MAX は適宜変えること。ROOT_MAXはMAXの平方根。関数の実行が終了した時点で、配列sf に2以上、MAXまでの素因数の和が格納される。

1. 問題
 使えるカセットテープの長さ(録音時間)と、録音したい曲のリストが与えられ、すべての曲が入るだけの、最も短いカセットテープを探せ。

2. 実例
 実例を見たほうが分かりやすい。

56 90 120 ← 3本のテープが使える。録音時間はそれぞれ56,90,120分。
20m 44s ← ここからは曲のリスト(m:分、s:秒)
4m 36s
7m 18s
13m 8s
9m 6s
8m 12s
% ← 入力の終了

出力結果を見てみよう。

90  ← 90分のテープを使う
Side A ← A面での録音
20m 44s ← 曲のリスト
4m 36s
7m 8s
Side B ← B面での録音
13m 8s ← 曲のリスト
9m 6s
8m 12s
% ← 出力の終了

3. 考え方
 詳しいことは問題文に述べてないので、常識的に考えて問題を解いてみた。
 一番録音時間の長いカセットテープは120分だと思う。それはA面+B面での録音時間。片面ではその半分しか録音できない。また、曲の数は最大30とした。

本問題にBFS(幅優先探索)を使った。

構造体
 typedef struct {
  char no; /* 曲の通し番号 */
  char side; /* A面かB面か */
  int a, b; /* A面とB面の録音時間 */
  int prev; /* 前へのポインタ */
 } QUE;
と定義し、1曲目はA面録音として、2曲目以降はA面に、またはB面に録音するように探索キューを展開していく。

つまり、n曲目においては、検索キューに存在しているn-1曲目までの組合せすべてに対し、次の操作を経て、再びキューに入れる。

que[y].no = n;  /* n番目の曲 */
que[y].side = 'A';  /* A面に録音する */
que[y].a = que[x].a + recordTimen;  /* A面での録音時間 */
que[y].b = que[x].b;  /* B面での録音時間 */
que[y].prev = x;  /* 前へのポインタ */
que[y+1].no = n;  /* n番目の曲 */
que[y+1].side = 'B';  /* B面に録音する */
que[y+1].a = que[x].a;  /* A面での録音時間 */
que[y+1].b = que[x].b + recordTimen;  /* B面での録音時間 */
que[y+1].prev = x;  /* 前へのポインタ */

すべての曲の探索キューを作成した後、短いテープの順に、A面もB面も録音時間に収まるものが探索キューにあるかどうかを調べる。

4. 感想
 DPによる方法も考えてみたが、配列はとてつもなく大きいので断念した。今回のBFS探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。

1. 問題

p986.jpg

上記のグラフにおいて、左のほうでは、高さ3でのピークが2、高さ2でのピークが2である。右のほうでは、高さ1, 2, 3でのピークはそれぞれ1である。
 グラフでは、パスは原点(0,0)から出発し、ステップ(1,1)と(1,-1)に沿って右へ移動し、最終的に(2n,0)にもどる。パスはx軸を切って下に移動することはない。
 n (1<=n<20)、および高さk (1<=k<20) でのピーク数がちょうどr (0<=r<20) であるパスの数を示せ。

2. 計算法
 本問題もDPによる方法を考える。
 高さkのところのピース数がrであるパスが右上がり(つまりステップ(1,1))で (x,y) に来た時の数を c[x][y][r][k][1] とし、右下がり(ステップ(1,-1))のパス数を c[x][y][r][k][0] とする。
 配列の大きさは c[40][21][21][20][2] になる。
 初期値 c[1][1][0][k][1] = 1 (1<=k<20)、他の要素はゼロ。
 漸化式は以下の通り。

for (x = 2; x < 40; x++) {
for (r = 0; r < 20; r++) {
for (k = 1; k < 20; k++) /* x軸上に来たパスに対し */
c[x][1][r][k][1] += c[x-1][0][r][k][0];
for (y = 1; y < 20; y++) {
for (k = 1; k < y; k++)
c[x][y-1][r][k][0] += c[x-1][y][r][k][1];
c[x][y-1][r+1][y][0] += c[x-1][y][r][k][1];
for (k = y+1; k < 20; k++)
c[x][y-1][r][k][0] += c[x-1][y][r][k][1];
for (k = 1; k < 20; k++) {
c[x][y-1][r][k][0] += c[x-1][y][r][k][0];
c[x][y+1][r][k][1] += c[x-1][y][r][k][0];
c[x][y+1][r][k][1] += c[x-1][y][r][k][1];
}
}
}
}

入力の値n, r, kに対する答えは c[n+n][0][r][k][0] である。

3. 検証用入出力データ

19 19 1
19 9 0
19 9 1
19 9 2
19 9 3
19 9 4
19 9 5
19 9 6
19 9 7
19 9 8
19 9 9
19 9 10
19 9 11
6 2 2
6 3 2
6 1 1
6 2 1
6 3 1
1
0286572
2466750
2413917
1024608
318921
81628
17003
2772
332
26
1
28
14
40
21
8

4. 感想
 DPの表現式(配列)をちゃんとつくっておけば、複雑な問題ではなさそう。

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

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

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

2 2 2 ← 授業科目数2、採用済者2人、採用予定者2人
10000 1 ← 採用済者1人目; 雇用コスト10000, 教える授業科目は1番目
20000 2 ← 採用済者2人目; 雇用コスト20000, 教える授業科目は2番目
30000 1 2 ← 採用予定者1人目; 雇用コスト30000, 教える授業科目は1番目と2番目
40000 1 2 ← 採用予定者2人目; 雇用コスト40000, 教える授業科目は1番目と2番目
0 0 0 ← 入力終了

採用済の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の漸化式は以下の通り。

for (n = 1; n <= N; n++) {
for (b = 0; b <= goal[S]; b++) {
if (p[n][b]==0 || p[n][b]>p[n-1][b])  /* 採用しないケース */
p[n][b] = p[n-1][b]
if (p[n][b2]==0 || p[n][b2]>p[n-1][b]+Cn)  /* 採用するケース */
p[n][b2] = p[n-1][b] + Cn
}
}
printf("231314736\n", p[N][goal[S]]);

上記の、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  ← 一番の問題がこちら
になる演算子がほしい!