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

1. 問題
 基底Nの整数がビューティフル(Beautiful)というのは、0~N-1の数値がすべて使われ、隣り合う桁の数値の差が1ということ。例えば、9876543210は基底10でのビューティフルナンバーだ。
 基底N (2<=N<=10) と桁数M (0<=M<=100) が与えられた時、M桁以下のすべてのビューティフルナンバーの総数を示せ。

2. いくつかの実例
 N=2, M=4に対するビューティフルナンバーは、10, 101, 1010の3つ。
 N=3, M=7に対しては、210, 2101, 21010, 21012, 210101, 210121, 2101010, 2101012, 2101210, 2101212, 21210, 212101, 2121010, 2121012, 2121210, 101012,1010121,1012, 10121, 101210, 1012101, 101212, 1012121, 1210, 12101, 121010, 1210101, 121012, 1210121, 121210, 1212101の31個がビューティフルナンバーだ。
 N=10, M=10に対するビューティフルナンバーは 9876543210の1つ。

3. 計算方法
 ここでは、DPによる方法を考える。
 m桁目に数値nである数字の数は a[m][n][b](大きさはa[101][10][1024])とする。bは1~m桁までの各数値に対応するビットパターン。1<=m<=100, 0<=n<10, 0<b<=1024。

  a[m+1][n][b|bp[n]] = a[m][n+1][b] + a[m][n-1][b]

  bp[10] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };
  初期値 a[1][n][bp[n]] = 1 for 1<=n<10

基底がN, 桁数がちょうどMのビューティフルナンバーの数を c[M][N] とすると、

p11472.jpg

  full[11] = { 0, 0, 3, 7, 15, 31, 63, 127, 255, 511, 1023 };

最終的に、問題の解答を得る。

    scanf("231314736-2082935264", &N, &M);
if (M < N) puts("0");
else if (M == N) puts("1");
else if (N == 2) printf("231314736\n", M-1);
else {
int ans = 0;
for (m = 1; m <= M; m++) ans = (ans + c[m][N]) % 1000000007;
printf("231314736\n", ans);
}

4. 検証用入出力データ

18
2 50
3 50
4 50
5 50
6 50
7 50
8 50
9 50
10 50
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100
49
167772006
181208395
203197534
856300377
756922568
423236469
509230823
322172256
99
494806323
187470286
778091614
151286785
265624146
626153492
829010450
958872830

5. 感想
 わりと正解率の高い問題だが、自分ではそれなりに考えた。もっと簡潔な解き方があるかもしれない。

1. 問題
 15桁もの巨大整数に関する素因数分解の問題。つまり、整数N(1<N≦1016)を素因数分解し、以下のフォーマットに従って結果表示すること。
 60 = 2^2 * 3 * 5
 36 = 2^2 * 3^2
 10007 = 10007
 入力データ数は800以下、許される実行時間は15秒以内。/p>

2. 考え方
 解けたひとが少ないので、難問かな。でも、とにかくトライしてみよう。

 まだ解けないでいる。

1. 問題
 32ビット符号付き整数が3つ与えられ、どんな3角形になるかを判定せよ。
 出力(画面表示)はつぎのどれかになる。
  Invalid 3角形にならない
  Equilateral 正3角形
  Isosceles 2等辺3角形
  Scalene その他の3角形

2. 考え方
 難しくない問題だが、3角形の3辺をa, b, cとすると、3角形になる条件
  a+b>c  b+c>a  c+a>b  a,b,c>0
を利用すればいいだろう。

3. 感想
 簡単な問題だが、整数型にlong long intを使おう。

1. 問題
 整数Nが2つ以上の異なる素数で割り切れるのであれば、最大素因数(LPD: Largest prime divisor)が存在する。NのLPDを探せ。Nの大きさは14桁以下。
 LPDが存在しなければ、出力を-1とする。

2. いくつかの例
 2は素数2でしか割り切れないので、そのLPDは存在しない。
 6は素数2, 3で割り切れるので、LPD=3。
 100は素数2, 5で割り切れるので、LPD=5。
 9は素数3でしか割り切れないので、そのLPDは存在しない。
 -385は素数5, 7, 11で割り切れるので、LPD=11。

3. 考え方
 与えられたNの大きさ。14桁もあるので、どう対処するかが大きな問題。
 結果的に言えたのは、この問題に限っては、一番単純な素因数分解法でやることだ。
 勿論、今回はたまたまうまく行っただけで、14桁の整数のLPDを高速に求めることは、そう簡単ではないはず。

4. 感想
 エラトステネスのふるいを利用しようとしたが、全然ダメだった。
 最終的に提出したプログラムの実行時間が0.090秒になったが、プログラムの内容に納得していない。
 なお、同じ入力値の計算を2度とやらないために、ハッシュテーブルを利用して、計算済の結果を保存しておいた。こちらも本来は要らないものかも。

1. 問題
 特殊隊員たちが決められた建物からスタート。彼らが分かれて、隣接道路を使い、隣の建物に到達しその建物を爆破する。ただし、最後にまたある決められた建物に彼らが戻ってこないといけない。隣接道路の移動時間は1時間単位とし、全部の建物を破壊するのに必要な最小移動時間を算出せよ。

2. 入力データの意味
 理解を深めるために、以下の例を考える。

4  ← 建物の数N(≦100)
3  ← 隣接道路の数R
0 1  ← 建物uとvをつなぐ道路あり(0≦u, v<N)
2 1
1 3
0 3  ← スタートする建物s と集合する建物e

この例での答えは4だ。グラフを見れば容易に納得するだろう。

p11463.jpg

 つまり、建物0からスタートし、建物1に到着し破壊する。建物3は集合地なので、まず建物2に到着して破壊した上、また建物1の地点に戻ってくる。最後に建物3につく。
 移動時間は0→1→2→1→3の4になる。

3. 考え方
 すべてのノード(建物)nに対し、スタートノードsからの最短距離x(n)と、エンドノードeからの最短距離y(n)を求める。
 すべてのnに対し、x(n)+y(n)の最大値が答えになるのだ。

最短距離を求めるのに、以下のような横型探索を使う。

道路に相当する隣接行列a[100][100]では、ノードu, vに道路あれば、
   a[u][v]=a[v][u]=1。
スタートノードsからの最短距離を配列dis[n](つまり、上記のx(n)に相当)とする。

(1) 初期値:すべてのノードnに対し、dis[n]=-1。
(2) スタートノードsに対し、dis[s]=0、sをキューに入れる。
(3) キューからノードを取り出す。ノードがなければ横型探索終了。ノードあれば、ノード名をnとする。
(4) すべてのノードm(0<=m<N)に対し、
  dis[m]=dis[n]+1 if a[n][m]==1 かつ dis[m]<0
  ノードmをキューに入れる。

横型探索終了した時点で、dis[n]にスタートノードsからの最短距離が記録される。

同じことをエンドノードeに対しても行う。

4. 感想
 1回目の提出ではバグあったが、2回目ではAC。実行時間は0.400秒だった。0.300秒に上げたいけど、それ以上のいいアイデアは浮かんでこない。

テクニック的に上げるなら、scanf()をやめるぐらいかな。気を取り直して、データ入力に自作の関数を使い、3回目の提出では0.1000秒に上がった。現時点では2位。

1. 問題
 年齢 (1~99) を表すデータが与えられて、それらを昇順でソートしろ。
 なお、データ数は2000000まで。利用できるメモリ上限は2MBまで。

2. 考え方
 問題自身は簡単だが、使用できるメモリは2MBしかないので、サイズ100の(int型)配列だけを用意し、入力データのそれぞれの度数をそこに入れておく(足していく)。
 配列に記録されているそれぞれのindexを、配列の先頭からprintf()すればOKになるはず。

3. 例
 たとえば、入力

5
5 3 5 3 4

に対して、各データの度数を表す配列は
 a[1]=0, a[2]=0, a[3]=2, a[4]=1, a[5]=2, a[6]…a[99]=0
になり、配列の先頭から、3, 3, 4, 5, 5 とそれぞれの存在している要素のindexだけを表示する。

4. 感想
 1回目の提出では実行時間が1.020秒。入出力にscanf()、printf()を使ったせいだと思う。それらをgetchar(), putchar()に直して、2回目に提出して、0.450秒になった。1位との差はまだまだだが、一応これでおしまい。もっと早くするには、fread(), fwrite()を使うようだが、めんどくさい。

スピードをそれほど望まなければ、難しい問題ではないが、メモリ上限に気を配るべきだろう。

新しいブログシステムの使い方を確認するためにも、UVa問題を解いてみる。

1. 問題
 整数a, b (0<a?b?100000) が与えられて、その間に含まれている平方数の数を答えろ。

2. 例2つ
 a=1, b=4の時に、含まれている平方数は1, 4の二つなので、答えは2になる。
 a=1, b=10の時に、含まれている平方数は1, 4, 9の3つなので、答えは3になる。

3. 考え方
 a=1, b=nに対する解答 f(n) が分かれば、本問題の答えは f(b)-f(a-1) になるので、f(n)についての解答を考えることにする。

100000の平方根は316。平方数は高々316しかないので、サイズ100000の配列を用意し、数えていけばうまくいくはず。

つまり、以下の漸近式が使える。

f(0) = 0
f(k) = f(k-1) +1 if k is a square number
f(k) = f(k-1) if k isn't any square numbers

4. テストデータとその結果

1 4
1 10
1 1
2 2
10 10
100000 100000
1 100000
10000 100000
100 10000
0 0
2
3
1
000316
217
91

5. 感想
 とても簡単な問題。

毎年恒例ACM/ICPC(ACM大学対抗プログラミングコンテスト)の世界大会が今年も行なわれたが、変わったのが今回は日本での初開催(千葉県浦安市のヒルトン東京ベイ、3月12~16日)。日本からは京都大学、東京大学、埼玉大学の3チームが出場し、地元の利を生かした日本チームの活躍が期待されたところ。

コンテストは、3人1組でチームを作り、与えられた課題に対してプログラムを作成する形で行なわれる。問題は計10題出題され、制限時間は5時間。使用できるプログラミング言語はC/C++、Java。なお問題はすべて英語で出題される。最も多くの問題に正解したチームが優勝となり、正解数が同じだった場合は問題の回答にかかった時間が最も短かったチームが優勝となる。

Pascal言語は使用言語から外され、これからプログラミング言語を学習するひとは気をつけよう。

コンテストの結果は以下の通り。

 1位 ワルシャワ大学(ポーランド)
 2位 清華大学(中国)
 3位 サンクトペテルブルグ光学・精密機械大学(ロシア)
 4位 マサチューセッツ工科大学(アメリカ)
 5位 ノボシビルスク国立大学(ロシア)
 6位 サラトフ国立大学(ロシア)
 7位 トゥエンテ大学(オランダ)
 8位 上海交通大学(中国)
 9位 ウォータールー大学(カナダ)
 10位 モスクワ国立大学(ロシア)
 11位 オークランド大学(ニュージーランド)
 12位 カリフォルニア工科大学(アメリカ)

アメリカ、ロシア、中国の名門(工科)大学が勝ち残り、流石だ。

ちなみに、日本3チームの成績は、京都大学14位、東京大学26位、埼玉大学44位、実力からしてそんなもんだろう。プログラミングコンテストという言葉すら知らない大学の教授や情報系大学生が日本にあまりにも多い。工科大学といえば、日本では東工大となるわけだが、チームすら送り込めず、参加資格なし。こんな危機的状況に対し、文科省も情報処理学会も大学関係者も知らん振り、新聞もテレビも一切報道なし。

コンテストに用いられた問題は ここ にある。チャレンジしたい方はどうぞ。

プログラムの高速化について書きます。

UVaに現時点では2千題近いプログラミング問題が出題されています。プログラミングを楽しみながら稼ぎたいひとはTopCoderというサイトを利用するのもいいでしょう。

書いたプログラムの良し悪しは評価基準それぞれですが、プログラムの正確性、高速性、信頼性、可読性、メンテナンスのしやすさ等がよく評価基準に用いられると思います。

ここではもっとも比較しやすいプログラムの高速性を考えます。

2つのプログラムを同時に走らせて、先に終了するほうが速い。そういう観点からすると、高速性の比較がやりやすく、UVa でもランキングを決めるパラメータとして採用されています。

ちなみに、プログラムの正確性を判定するのは難しく、一般的には判定不能と証明されています。UVaでも言い方として「正解」というのではなく、「Accepted=受け入れられた、受理された」というレベルでわれわれの送ったプログラムを評価しています。(後にいくらでも実は前の判定が間違えていたとかの言い訳にするための逃げ道だというひともいますが。)

ほかに比較しやすいパラメータはメモリの使用量、ソースプログラムの長さ、等もあります。北京大学のPKU (acm.pku.edu.cn) ではソースの長さが競っていますが、あまり感心しません。ソースプログラムの可読性が著しく損なわれる恐れが大いにあると思います。1バイトでも短くしたいがために、変数名を1文字にしたり、スペースを全くソースに入れないことを平気でやってしまいますから。