ジャンルＡの問題は， 単純な探索プログラムで十分速く解ける． 実際， ほとんどのチームの s5.c プログラムが， その方針に沿って無難に解いていた． そこでここでは， ジャンルＣ（一部，ジャンルＢ） における各チームの探索手法を見ていくことにしよう．
なお，
以下で次の記号を用いる：
また，
各チームの作ったプログラムはチーム名で呼ぶことにする
（watanabe は出題責任者作のプログラム）．
(1)石の数を推定した上での探索
石の選び方は 2の40乗 通りもあり， とてもすべてを探索するわけにはいかない （クレイ C916 でも数時間かかってしまう）． そこで， 探索範囲を限定する方法が必要になるのだが， その一つが， 選ぶ石の数を限定して探索する方法．
たとえば， ジャンルＡの問題（5 個の石からできる重さ）は， 単純な探索法でも速く解ける． これは 5 個の石の選び方40から5とる組合せ が十分小さいからだ． そこでジャンルＣでも， 石の個数を推定し， その範囲内で解を探せば全数探索よりはるかに速い （石の個数は， たとえば「target ÷ 平均の重さ」で推定できる）． この方針は， kawagoe, apcc, watanabe がとっている．
もちろん， この方法の弱点は， 石の数が 20 個に近くなった場合に出てくる． いくら石の個数を限定しても， その数が 20 に近くなると全数探索と変わりなくなるからだ （選ぶ石の数が， たとえば 35 だった場合には， 選ばなかった石を求めればよい． この手法はほとんどすべてのチームが採用していた）． たとえば， ジャンルＢの問題（10 個の石からできる重さ）でも， 単純な方法では数分かかってしまう． そこで高速化が必要になってくる．
そのために， たとえば， apcc, watanabe がとった方法は， 最後の 5 つの選択によって得られる重さをすべて表にとっておく方法だ （この考え方は， manmaru, duckbill と同じなので， 後で再び説明する）． こうすると， 最後の 5 つの選択は非常に速く決まるので， 10 個選ぶ計算が， 単純な方法で 5 個選ぶ計算にかなり近くなる． もちろん， 最後の 6 つ，7 つ，... と表を大きくすれば， それだけ速いのだが， 今回のメモリの制限内では 5 つまでが精一杯のところだった （watanabe の場合には， CPU の数だけコピーが必要だったので 4 つまでが限界）． したがって， 石の数が 15 個以上（35 個以下）になると， 少なくとも単純な方法で 10 個選ぶの程度の時間がかかるため， 非常に苦しくなってしまったのだ．
一方 kawagoe は， 無闇に 10 個選ぶのではなく， ある種の探索方針に基づいて選んでいる． これについては (3) で再び述べることにしよう． (2)全数探索
それでも勇敢に全数探索に挑んだチームがあった． 何と上位 2 チームは， 選ぶ石の数などおかまいなし， 基本的にはすべての可能性を探す方針で勝利を獲得したのである．
もちろん， 何らかの工夫が必要だ． manmaru と duckbill の上位 2 チームは， やはり表を作るという戦法をとったのである．
簡単にその概略を説明しよう． まず， 石を初めの 20 個と後ろの 20 個の 2 グループに分ける． そして後ろの 20 個からできる重さをすべて計算し表 utbl に入れておく． 探索では， 始めの 20 個のそれぞれの選び方に対し， 部分和 sum を求め， target - sum が utbl にあるかを調べる． もしあれば， 始めの 20 個の選び方は正しかったことになる． 一方， 後ろの 20 個の選び方だが， 実は utbl をうまく作れば， そのどこに target - sum があったか， つまり utbl[i] == target - sum となる i から， 逆に 20 個の選び方を復元することができる （詳しくは「優勝チームのプログラム」を参照）．
この方法の計算時間について考えてみよう． 始めの 20 個を選ぶやり方が 2の20乗 通りあるので，
そこで duckbill は， utbl をソートしておき， 二分岐探索で表を調べている． こうすると log_2 2^20 = 20 ステップで探索できる． 一方， manmaru は次のような賢い方法をとった．
表 utbl の各要素 utbl[i] を 2400000 で割った余りを考えると，
同じ余りを持つものが高々 3 つしかない
（本当に 3 つになるかは疑問！！）．
たとえば，
余りが 2478 となるものが
utbl[103], utbl[13489], utbl[2345689]
だったとしよう．
この 3 つを 2 次元の表 {¥tt atbl} にとっておく．
つまり，
実はこの方法は， 「ハッシュ法」と呼ばれ， 計算機科学ではよく使われている． しかし， もしチーム manmaru の諸君が自分たちであみだしたのなら， 大喝采ものである． （ところで， なぜ 2400000 という数を出したのか， ちょっとわからなかった． それから， これで割ると同じ余りが 3 つ以上にならないかどうか， かなり疑問が残るのだが．．．）
ところで (1) で， メモリの関係から 6 個の石の選び方の表は作れないと述べた． それなのに 20 個の石の選び方の表が作れるのはなぜか？ 答えは簡単． 2の20乗 <40から6をとる組合せ、 だからだ． ちなみに， 私（出題責任者）は， ろくに考えもせず $2^{20}$ ははるかに大きな数と思い込んでいた． これが失敗のもと！ 赤恥をかいた原因である． (3)その他の探索
その他にも探索範囲を狭めようという努力がいろいろとみられた． 主な考え方は， 石の重さをうまく使って， なるべく可能性のないものは探索範囲から削ってしまうというもの． たとえば， slowdown は， 石の重さを評価して探索の枝刈りをしている． また， kawagoe は重い石から選び方を決めるが， 一端決めた後は， 軽い石の方から選択の仕方を変えるようにしている． これがどの程度有効なのかはっきりしないが， 少なくとも今回の問題に対してはうまくいったようだ． kawagoe に雰囲気が似ていて， しかも“不思議と”（失礼！）うまくいくのが depend の探索法． この depend の探索法を少しみてみよう．
チーム depend のプログラムは， 石の数を限定しない， いわゆるノージャンル型． その探索法については， 説明するより直接プログラムを見た方が早いだろう． 次に示すのは探索部分のプログラム． 一番外側のループ while (rest) を抜けたときに， 配列 dat で 1 が立っているところが答え． ただし“答え”といっても， 石の番号ではなく， ソートした列 ss における番号である．
for (i=0; i<40; i++) dat[i] = 0;
rest = target;
while (rest){
for (i=0; i<40; i++) if (sum[i] >= s) break;
while(ss[i] > rest) {
for(; !dat[i]; i++);
for(; dat[i]; i++) {dat[i] = 0; rest += ss[i];}}
dat[i] = 1;rest -= ss[i];}
（注）sum[i] = ss[0] + ... + ss[i]
たしかに， この探索で見落しはないことはわかるが， なぜこれが効率良く探せるのかは不明． 皆さん， 各自で考えてみて下さい．
満点をとれるかとれないかは， 探索手法が決めてだったが， さらに計算時間を圧縮するには， パラレル化，ベクトル化が非常に有効だった． とくに manmaru はベクトル化を有効に使っていた．
先ほど述べたように， manmaru, duckbill は， 非常に大きな表を前もって用意し， それによって探索のスピードを上げている． ところが， この表をまともに計算すると約 20 秒ほどかかってしまう． そこで， duckbill は， 表を定数として持ち込むことを考えた （何でもありなのだから，これも立派な戦略である）． しかし， 表を全部定数として持つと， プログラムが大きくなりすげてコンパイラできなくなってしまう． そこで duckbill は， 表の大部分を定数として持ち， 残りの部分だけを計算する， という手法をとった．
それに対し manmaru は， まともに表を計算する正攻法をとったのである． 彼らはこれを非常にシンプルなループで実現させることで， クレイ C916 のベクトル化（そしてパラレル化）の能力を最大限に活かしたのである． まさに優勝にふさわしいプログラムだったのだ！
ところで， パラレル化に関しては， どのチームもあまり有効な手法をとっていなかった （不完全ながら nada-{a,b} は試みているが．．．）． さすがに CPU 9 個をどう使いこなすかまで考える余裕がなかったようだ． たとえば， 先の manmaru も， コンパイラにパラレル化を任せる形のプログラムで， 積極的にパラレル化している訳ではない （まあ， する必要もあまりなかったのだが）． これについては今後の研究課題として， あまり説明しないでおこう．