※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

ただいま解説や画像や問題文の写し準備中
このページの解説完了度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桁を求めよ.



解法

Prologという数値計算が遅い言語で実装しても0.01セコンドの計算時間で問題が解ける動的計画法による解法を提示します。


左から右へある程度ユニットをつなげていった場合。
右に新しくつなげるとき仮にAをつなげるとしましょう。

ユニットの左側2点は結合部で色の組み合わせが一通りに固定され、残り5か所の組み合わせのみが組み合わせの増加を招きます。

  • 新しくつなげるユニット(仮にAでユニット番号An+1としますと)にとってそれまで左でA n個とB m個を何個使ったか。
  • 左側2点がなにか不明な2色で固定され一通りになり残り5点の配色は自由になる。
の2種類の情報だけが計算において意味を持ちます。

  • さらにAの右に新しくもう一つつなげるときはAをn+1個Bをm個使い何か不明な2色でその新しくつなげるユニットの左2点は一通りに拘束される。
という上と同じ計算が繰り返されることとなります。
繰り返して100個目まで到達すれば答えとなります。

これを動的計画法で実装すればあっという間に答えが出ます。
わかりづらいと思いますので図を持って説明します。


今回の問題の解説ですが事細かに解説しても、重箱の隅をつつくような解説になってしまい本質がぼやけるような気がしました。
なので今回は考え方のヒントを羅列してみることにします。
ヒントを手掛かりにご自分で考えてみてください。

図にしてみましょう。
ある程度つなげて次にABとつなげる場合重要なものは何かを図にしてみます。
順番にヒントを出します。


解法A 一番左のユニット,最初の1個目の色の組み合わせ数。

Aの場合を考えてみましょう。

図の通りに番号をふって。
点をA1~A7とし一点ずつ7個目まで色を決定していく深さ優先探索で組み合わせを考えます。
A1とA2は何らかの2色なので1984色*1983色の2通りです。

A1~A7まで色を決定していくとき
一点目に採用した色を1、2点目に採用した色を2としますと。
とりあえず何らかの2色なので採用した色を1番の色、2番の色とします。
ここまでで1984*1983通りで何らかの不明な2色を採用したということだけがここでの組み合わせで重要となるので。
[一点目の色番号、2点目の色番号、、、7点目の色番号]
という組み合わせで表現すると
[1,2,未定、未定、未定、未定、未定]が1984*1983通り決まったとなります。
残りは探索で決めます。

3点目の色は1番の色からとるか2番の色からとるかそれ以外からとるかの3通りに分岐します。
隣り合う色が同じになってはいけないので1番と同じ色になってはいけませんから2番の色か3色目の新しい色となります。
2番の色が選ばれた場合
[1,2,2,未定,未定,未定,未定]=1984*1983*1通り
まだ使ってない色を3点目に割り当てた場合それを3番の色とすると3番の色の候補は1982個あり1982個のどれかに3番の番号を割り振ると。
[1,2,3,未定,未定,未定,未定]=1984*1983*1982通りとなります。
この要領で7個めの点まで計算し、すべての組み合わせを合計すると最初の一個めをAとした場合の色の組み合わせ数が出ます。
どの配色も、次に右につなげるユニットの左端の色を一通りに決める。
最初のAの配色はどんな配色にしてもA6とA7は次のユニットの何らかの不明な2色を固定するという点ではすべて同じです。
よってすべての探索結果ででてきた組み合わせ数を集計してAを一個置いた場合の組み合わせ数としてよいと判明します。

Bでも制約が異なるだけで計算方法は同じです。

ここで求まった組み合わせ数をPermA1,PermB1とします。

追加ヒント

[1,2,3,未定,未定,未定,未定]
の次4点目の決定は
[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通り

となります。


解法B 右側に一つユニットを結合した場合の組み合わせ数の増加について。

何個か結合した後右にもう一つ付け加える場合。
ある色を考えると
[A11,A22,,,A77]=[1,2,未定,未定,未定,未定,未定]=1通り。
から残りの未定な点の組み合わせを計算することになります。
これは上で行った解法Aと同じ要領で計算できます。

ここでもとまった組み合わせ数をPermAn,PermBnとします。


具体的な計算

1個目を置いて、その右に一つずつユニットを結合して組み合わせ数を考えます。
たとえば4つ目まで結合した場合さらに一つ結合する場合を考えます。
Aを何個使ったかBを何個使ったかで考えることとなります。
これをABを使った数として(A,B)でその場合の組み合わせ数と考えると。
(4,0),(3,1),(2,2),(1,3),(0,4)
これを(3,1)=Aを3個、Bを1個結合してできるすべての組み合わせ数とします。

となりこれの右端にAかBを一つ付け足した
(5,0)(4,1),(3,2),(2,3),(1,4),(0,5)
のそれぞれ場合の組み合わせ数を4つのデータから計算できます。

解法Bで行った組み合わせ数を使えば4つ目から5つ結合したものの組み合わせが求まります。

5つ目から解法Bの組み合わせ数を使えば当然6つ目が求まり、六個めからは7個目となってこれを100個目まで繰り返すと答えが出ます。


スペシャルヒント

































一つ目のユニットを置きその右に二つ目のユニットを置く場合の変化を考えます。
(1,0)=PermA1
(0,1)=PermB1
2つ目を置くと
(2,0)=(1,0)*PermAn
(1,1)=(1,0)*PermBn+(0,1)*PermAn
(0,2)=(0,1)*PermBn

で3つ目以降もAを一つ追加するかBを一つ追加するかしかないので同じ要領で組み合わせ数を計算できます。