ただいま解説や画像や問題文の写し準備中
このページの解説完了度100％
只今中身がきちんとしているかチェック中。
Problem 194 「着色配置」 †
とユニットB
からなるグラフについて考える. ユニット同士を垂直方向の辺に沿ってくっつけてグラフにする. 下図はグラフの一例である.
(a,b,c)タイプの配置とは, 以下を満たすグラフのことである:
a 個のユニットAと b 個のユニットBからなる各頂点は色づけされていて, 最大で c 色まで使われておりどの隣接する2頂点も同じ色にはならない。
上のグラフは(2,2,6)タイプの配置の例である.
正確には c≥4 を満たす全ての c に対し, (2,2,c)タイプの配置となる.
N(a,b,c)を, (a,b,c)タイプの配置の数とする. 例えば N(1,0,3) = 24, N(0,2,4) = 92928, N(2,2,3) = 20736 である.
N(25,75,1984)の最下位8桁を求めよ.
解法
Ｐｒｏｌｏｇという数値計算が遅い言語で実装しても0.01セコンドの計算時間で問題が解ける動的計画法による解法を提示します。
左から右へある程度ユニットをつなげていった場合。
右に新しくつなげるとき仮にＡをつなげるとしましょう。
ユニットの左側２点は結合部で色の組み合わせが一通りに固定され、残り５か所の組み合わせのみが組み合わせの増加を招きます。
- 新しくつなげるユニット（仮にＡでユニット番号Ａn+1としますと）にとってそれまで左でＡ n個とＢ m個を何個使ったか。
- 左側２点がなにか不明な２色で固定され一通りになり残り５点の配色は自由になる。
の２種類の情報だけが計算において意味を持ちます。
- さらにＡの右に新しくもう一つつなげるときはAをｎ+1個Ｂをｍ個使い何か不明な２色でその新しくつなげるユニットの左２点は一通りに拘束される。
という上と同じ計算が繰り返されることとなります。
繰り返して１００個目まで到達すれば答えとなります。
これを動的計画法で実装すればあっという間に答えが出ます。
わかりづらいと思いますので図を持って説明します。
今回の問題の解説ですが事細かに解説しても、重箱の隅をつつくような解説になってしまい本質がぼやけるような気がしました。
なので今回は考え方のヒントを羅列してみることにします。
ヒントを手掛かりにご自分で考えてみてください。
図にしてみましょう。
ある程度つなげて次にＡＢとつなげる場合重要なものは何かを図にしてみます。
順番にヒントを出します。
解法Ａ 一番左のユニット,最初の１個目の色の組み合わせ数。
Ａの場合を考えてみましょう。
図の通りに番号をふって。
点をＡ1～Ａ7とし一点ずつ７個目まで色を決定していく深さ優先探索で組み合わせを考えます。
Ａ1とＡ2は何らかの２色なので１９８４色*1983色の２通りです。
Ａ1～Ａ7まで色を決定していくとき
一点目に採用した色を1、２点目に採用した色を２としますと。
とりあえず何らかの２色なので採用した色を1番の色、２番の色とします。
ここまでで1984*1983通りで何らかの不明な２色を採用したということだけがここでの組み合わせで重要となるので。
[一点目の色番号、２点目の色番号、、、７点目の色番号]
という組み合わせで表現すると
[1,2,未定、未定、未定、未定、未定]が1984*1983通り決まったとなります。
残りは探索で決めます。
３点目の色は１番の色からとるか２番の色からとるかそれ以外からとるかの３通りに分岐します。
隣り合う色が同じになってはいけないので１番と同じ色になってはいけませんから２番の色か３色目の新しい色となります。
２番の色が選ばれた場合
[1,2,2,未定,未定,未定,未定]=1984*1983*1通り
まだ使ってない色を３点目に割り当てた場合それを３番の色とすると３番の色の候補は1982個あり1982個のどれかに３番の番号を割り振ると。
[1,2,3,未定,未定,未定,未定]=1984*1983*1982通りとなります。
この要領で7個めの点まで計算し、すべての組み合わせを合計すると最初の一個めをＡとした場合の色の組み合わせ数が出ます。
どの配色も、次に右につなげるユニットの左端の色を一通りに決める。
最初のＡの配色はどんな配色にしてもＡ6とＡ7は次のユニットの何らかの不明な２色を固定するという点ではすべて同じです。
よってすべての探索結果ででてきた組み合わせ数を集計してＡを一個置いた場合の組み合わせ数としてよいと判明します。
Ｂでも制約が異なるだけで計算方法は同じです。
ここで求まった組み合わせ数をPermA1,PermB1とします。
追加ヒント
[1,2,3,未定,未定,未定,未定]
の次４点目の決定は
[1,2,3,1,未定,未定,未定]=1984*1983*1982*1通り
[1,2,3,2,未定,未定,未定]=1984*1983*1982*1通り
[1,2,3,4,未定,未定,未定]=1984*1983*1982*1981通り
[1,2,2,未定,未定,未定,未定]の次は
[1,2,2,1,未定,未定,未定]=1984*1983*1*1通り
[1,2,2,3,未定,未定,未定]=1984*1983*1*1982通り
となります。
解法Ｂ 右側に一つユニットを結合した場合の組み合わせ数の増加について。
何個か結合した後右にもう一つ付け加える場合。
ある色を考えると
[A11,A22,,,A77]＝[1,2,未定,未定,未定,未定,未定]=1通り。
から残りの未定な点の組み合わせを計算することになります。
これは上で行った解法Ａと同じ要領で計算できます。
ここでもとまった組み合わせ数をPermAn,PermBnとします。
具体的な計算
１個目を置いて、その右に一つずつユニットを結合して組み合わせ数を考えます。
たとえば４つ目まで結合した場合さらに一つ結合する場合を考えます。
Aを何個使ったかＢを何個使ったかで考えることとなります。
これをＡＢを使った数として(A,B)でその場合の組み合わせ数と考えると。
(4,0),(3,1),(2,2),(1,3),(0,4)
これを(3,1)=Aを３個、Ｂを１個結合してできるすべての組み合わせ数とします。
となりこれの右端にＡかＢを一つ付け足した
(5,0)(4,1),(3,2),(2,3),(1,4),(0,5)
のそれぞれ場合の組み合わせ数を４つのデータから計算できます。
解法Ｂで行った組み合わせ数を使えば４つ目から５つ結合したものの組み合わせが求まります。
５つ目から解法Ｂの組み合わせ数を使えば当然６つ目が求まり、六個めからは７個目となってこれを１００個目まで繰り返すと答えが出ます。
スペシャルヒント
↓
一つ目のユニットを置きその右に二つ目のユニットを置く場合の変化を考えます。
(1,0)=PermA1
(0,1)=PermB1
２つ目を置くと
(2,0)=(1,0)*PermAn
(1,1)=(1,0)*PermBn+(0,1)*PermAn
(0,2)=(0,1)*PermBn
で３つ目以降もＡを一つ追加するかＢを一つ追加するかしかないので同じ要領で組み合わせ数を計算できます。
最終更新：2013年12月14日 11:39
