組合せ問題は得意のほうではありません.それでも問題を解かないといけないので,自己流を紹介します.真似る人はいないと思いますが,邪道であることは確かでしょう.

例で説明すると判り易いので,ほやほやの問題を取り上げます.

組合せ問題: #10884 Persephone
N 本の長さ 1m の棒でエリア(牧場)の周りを囲む.周長を N だとすると,囲むパターンは何通りあるか.

ほかにも制限条件がいくつかあるので,本文を確認されたい.結局のところ,ごちゃごちゃ余計な条件でもつけないと,出題者も計算できないのが正直なところかもしれません.あるいは,計算式に合わせて問題が作成されていたということでしょう.

さて,紙に書いて,ルール(計算式)を探るところからスタートします.
N の値が奇数の場合では囲めないことにすぐ気づきました.偶数の N=2 でもダメで,N=4で単位正方形を1つやっと作れます.N=6では回転させると,計2パターンが得られます.

N=8のケースでは答えが問題の説明文にあったので,自分で考える必要がなくなります.

N=10.問題が解けるかどうか,それにかかっていることがいままでの経験で分かっていましたので,まじめに探しました.約10分そこそこで28パターンあることに突き詰めました.

ここからは完全に自己流.いわば,ネットの力をフルに利用する訳です.オンライン整数列大辞典(米国AT&T研究所) を開いて,数字列を打ち込みます.

そのサイト,一見地味の存在ですが,知る人ぞ知る大御所.とくに組合せ問題等,手持ちの数値列の規則や数式を知りたいならば,まず一度は訪ねてみるべきところ.

さて,N=4 から N=10 までの答え 1, 2, 7, 28 を入れると,多くのシーケンスが現れてきて,ひと安心.なにも出てこないと当然答えが見つからないわけで,別な方法を考えるしかありません.

それぞれのシーケンスの名称や,コメント,参照リンク先を検討して,ターゲットを定めます.

IDナンバーA002931 は良さそうに見えますが,計算式がないので,取りあえずパス.

もっと魅力的なシーケンスは IDナンバー A005436 でした.
名称も Number of convex polygons of length 2n on square lattice というもので,いい感じ.早速そこに紹介されている計算式 a(n) = (2n+11)4^n -4(2n+1)C(2n,n) に従って,問題の入出力にある N=100 を電卓で計算してみました.残念ながら答えは合わない!

ほかのシーケンスについてもチェックしましたが,良さそうなものはなく,あきらめようかなと思いました.

ところが,Convex Polyomino というリンク先で,Convex Polyomino の分類を見ながら,今回の問題に関連性のあるものを物色していたら,上に書いた計算式の適用方法に自分が間違っていたことに気づきました.

Expanding the generating function shows that the number of convex polyominoes having perimeter 2n+8 is given by

つまり,N=100 あるいは N=50を代入するのではなく, N=46 と代入して使わないといけなかったのです.N=46に直して計算してみたら,答えが一致したので,計算式がこれでゲット.

あとは多倍長整数を使ってプログラムを書くだけ.なぜ多倍長整数が必要かというと,N=100に対応する答えは,問題の説明文に書いた通り,357215388993130669706869321408 という大きさ.30桁の値なので,現時点での Gnu C の計算できる最大整数 18446744073709551615 (=264-1),20桁) を越えてしまったからです.

具体的には,個々のN (N <= 100) について以下のように計算します.
   N = 奇数 なら,答えは 0 (ゼロ).
   N = 2以下の値なら,答えも 0.
   N = 4 なら,答えは 1.
   N = 6 なら,答えは 2.
   N = 8 以上ならば,上記の計算式に n = (N-8)/2 と代入して計算し,答えを出す.

計算式において,4のべき乗 4n と組合せ数 (2n)!/(n!*n!) についてはつぎの漸化式を使って求めます.
   4のべき乗 ⇒ F(n) = F(n-1)*4  for n >= 1
             F(0) = 1
   組合せ数 ⇒ C(n) = C(n-1) * 2(2n-1)/n  for n >= 1
            C(0) = 1

#10884 Persephone. UVa Online Judge C source program

プログラムを公開していいかどうかは少し迷いましたが,いいでしょう.どちらかというと,多倍長整数関数(このサイトですべて公開済み)の使い方は勉強になると思いますので.ちなみに,自作の多倍長整数関数は最高速とは言い切れませんが,決して遅くはありません.UVaでのスピード競争にはほとんどの場合(多倍長整数関数が必要とするケースですが)勝っていました.また,沢山のUVaプログラムに使用してきたので,関数の信頼性にも問題ないと思います.

問題をこれで解いたわけですが,数時間のプログラミング・コンテストのなかで,解けるひとがいるかどうか,とても知りたいです.コンテストですので,ネットは当然使えません.いろいろな組合せ問題の計算式をいっぱい書き込んだ参考書等を持ち込めばいいかもしれませんが,こんな書籍って存在するものでしょうか.また,多倍長整数の関数(とくに割算)が結構長いので,ソースリストを事前に用意したとしても,コンテスト会場で正しくコンピュータに打ち込むのも一苦労だろう.

余談ですが,日常 Google を使っていて,不便だなぁと感じたのはやはり数式の検索.使う変数や書き方が違っていても,数式が出てくると大変便利.どうしても無理なら,使う変数の文字や数式の構造等の入力にルールを決めてもしょうがないと思いますが,そういうサービスを期待するのは無理というものなのかな.

例えば,上の計算式.x = 0, 0.1, 0.2, 0.3, …, 300 の値について計算したいが,計算式があるのかないのか,とても知りたいのです.整数の場合の x については既に計算式は分かったけれども.

いつの日になれば,こんな式も Googling できるでしょう.

Comments are closed.

Post Navigation