0からはじめる計算幾何学 第03回 パソコン甲子園の問題に挑戦する
日本の ICPC の幾何問題は、世界のそれと比べてレベルが高いという話を聞いたことがあります。
日本が幾何を得意としているのかどうか私には分かりかねますが、ここでふと、パソコン甲子園にも面白い幾何の問題があったことを思い出しました。
今日はパソコン甲子園2005本選問題28「ケーキ屋」を紹介しましょう。
問題はパソコン甲子園公式サイトの例題ページにて公開されていますが、こちらにも転載します。
ケーキ屋さんが、まちまちな大きさのロールケーキをたくさん作りました。 あなたは、このケーキを箱に並べる仕事を任されました。 ロールケーキはとてもやわらかいので、他のロールケーキが上に乗るとつぶれてしまいます。 ですから、全てのロールケーキは必ず箱の底面に接しているように並べなければなりません。 並べ替えると必要な幅も変わります。
ファイルから、n個のロールケーキの半径・・・・・・・・と箱の長さを読み込み、それぞれについて、箱の中にうまく収まるかどうか判定し、並べる順番を工夫すると箱に入る場合は "OK"、どう並べても入らない場合には "NA" を出力して終了するプログラムを作成してください。
ロールケーキの断面は円であり、箱の壁の高さは十分に高いものとします。 ただし、ロールケーキの半径は3以上10以下の整数とします。 つまり、ケーキの半径に極端な差はなく、図 (b) のように大きなケーキの間に小さなケーキがはまり込んでしまうことはありません。 また、ケーキの個数 n は12個以下とします。
ケーキを箱に詰めていくとき、その横幅をどう求めるかがこの問題の肝となります。 計算方法がすぐに思い浮かんだ人は、なかなかの数学力を持っているのではないかと思います。 私の場合ですが、隣に幾何学の得意な友人がいたので彼にアウトソーシングしたところ、見事に計算式を弾き出してくれました。
箱の中でn個のケーキc1, c2, ..., cnを並べたとき、その横幅は、
(c1の半径) + (c1とc2の中心の横方向の距離) + (c2とc3の中心の横方向の距離) + ... + (cn-1とcnの中心の横方向の距離) + (cnの半径)
として表されます。
箱の中で2つのケーキ c1 (半径r1), c2(半径r2) が接しているとき、それらの中心の横幅は、次のようにして求められます。
c1の中心を通り箱の底辺に平行な補助線を引き、c1とc2の中心を使って図のように直角三角形ABCを作ります。
図からABはc1とc2の高さの差、つまり半径の差となっていること、ACはc1とc2の半径の和となっていることが分かります。
これらとピタゴラスの定理を使って、 AB2 + BC2 = AC2 BC = sqrt(AC2 - AB2) BC = sqrt((r1+r2)2 - (r1-r2)2) となって、計算式が立てられました。
実装はこの通りに素直にやってもいいのですが、問題文を読むと半径は3以上10以下の整数と書いてありますので、あらかじめ全て求めてテーブル引きしてしまいましょう。
/* グローバル変数 */ const int maxcakesize = 10; const int mincakesize = 3; double table[maxcakesize+1][maxcakesize+1]; /* 半径 i のケーキと半径 j のケーキを並べたとき、それらの中心の 横方向の距離を求めて table[i][j] に格納する。 */ void create_table(){ for (int i=mincakesize; i<=maxcakesize; i++) for (int j=mincakesize; j<=maxcakesize; j++) table[i][j] = sqrt( (i+j)*(i+j) - (i-j)*(i-j) ); return ; } /* ケーキの半径の配列とケーキの個数を引数として受け取る。 配列の通りにケーキを詰めたときの横幅を返す。 */ double calculate(int *cake, int cakenum){ double result = (double)cake[0]; for (int i=0; i<cakenum-1; i++) result+=table[cake[i]][cake[i+1]]; result += (double)cake[cakenum-1]; return result; } |
最後にもう一つ。 問題文にはケーキの並べ方は任意と書いてありますので、可能な並べ方の中から最適解を探さなければなりません。 ケーキの個数は最大12個なので並べ方は最大12!通り考えられます。 全通り試すことが出来るとも出来ないとも言い切れない微妙な数字ですが、この大会のタイムリミットは1分あること、1通り当たりの計算量もあまり少ないことなどを考えると、全通り試していいのではないかと私は思います。
/* 計算機ε */ const double EPS = 1.0e-6; /* ケーキの半径の並び、ケーキの個数、箱の大きさを引数として受け取る。 箱に詰められるようなケーキの並べ方があるのなら "OK", そうでなければ "NG" を返す。 ( next_permutationは順列を生成する。algorithmヘッダの中で定義されている) */ string execute(int *cake, int cakenum, int boxsize){ bool result; sort(cake, cake+cakenum); do result = ( (calculate(cake, cakenum) - (double)boxsize) < EPS); while (next_permutation(cake, cake+cakenum) && !result); return (result ? "OK" : "NG"); } |
全通り試せないときのための高速化ですが、いくつかの方法が考えられます。
まず、隣り合ったケーキの大きさの差が大きくなればなるほど効率的に詰められることは明らかです。
これを使って、大きいケーキと小さいケーキを交互に選びながらバックトラックすればいくらか速くなるでしょう。
また、未証明ですが、最小の横幅となるような並べ方は次の2通りのどちらかとなりそうです。
n個のケーキの半径を昇順にソートしたものを、改めて c1, c2, ..., cn とします。
arrange1 = {..., cn-3, c3, cn-1, c1, cn, c2, cn-2, c4, cn-4, ...}
arrange2 = {..., c4, cn-3, c2, cn-1, c1, cn-2, c3, cn-4, c5, ...} |
いかがでしたでしょうか。 高校生のための問題とは言っても、ICPC国内予選の3問目と同程度の難易度の問題だと思います。
パソコン甲子園には高校1年生も参加しているのですから、あまり高度な数学の知識を必要としない問題を作ろうと作題委員の先生方は骨を折っているのではないかと推察します。 この問題はピタゴラスの定理さえ知っていればよく、むしろ数学的なひらめきと応用力が試される、良い問題だと私は思います。
（※ここで掲載したサンプルプログラムは、問題に対して必ずしも正しい答えを返すことを保障するものではありません。）
担当: 田山 (アウトソーシンガー)
