本番思いつかなかったパターンがあったので、こりゃSmallも通るわけないよね。
https://code.google.com/codejam/contest/8234486/dashboard#s=p3
問題
ある円柱型のドラムの側面は、縦R行、横C列からなるグリッドに分けられている。
各マスには数値が書かれている。
「各マスには、隣接マス中に同じ数字が書かれたマスがその数字と同じだけある」
という条件を満たす数値のパターンが何通りあるか答えよ。
ただし、ドラムを円柱の軸に沿って回転させたとき同じパターンになるものは、同一と考える。
解法
Rは2以上、Cは3以上のため、各マスに書かれる数値は1～3の何れかである。
登場するパターンは、以下の何れかである。
- 1. 3だけで構成される2行のパターン(横方向は1マス周期)
33333... 33333...
- 2. 2だけで構成される1行のパターン(横方向は1マス周期)
2222....
- 3. 1,2で構成される2行のパターン(横方向は3マス周期)
122122122... 122122122...
- 4. 1,2で構成される2行のパターン(横方向は6マス周期)
112222112222112222... 222112222112222112...
- 5. 1,2で構成される3行のパターン(横方向は4マス周期)
221222122212... 121212121212... 122212221222...
このパターンを元に、行ごとにDPでパターン数を列挙していく。
ただし以下の3点を状態として管理していく必要がある。
- パターン2～5のを縦に並べると、1や2のマスが2,3個以上隣接してしまうので、これらは縦には並べられない。
- よって、パターン1とパターン2～5は交互に並べるよう、直前のパターンがどちらか管理する必要がある。
- パターン3～5はCがそれぞれの周期の倍数でなければ適用できない。
- 回転して同じになるパターンは重複して数えないようにする。
- これには、ここまでのパターンが何マス周期かを管理して処理する必要がある。
- ここまでのパターンの周期をP、最後に追加しようとしているパターンの周期をQとすると、最後に追加したパターンにより全体の周期はLCM(P,Q)となり、また最後のパターンの置き方はGCD(P,Q)通りとなる。
int R,C; ll mo=1000000007; ll dp[105][2][25]; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>R>>C; ZERO(dp); dp[0][0][1]=dp[0][1][1]=1; FOR(i,R) { FOR(j,25) { // 22222 (dp[i+1][0][j] += dp[i][1][j]) %= mo; // 122122 // 122122 if(C%3==0) (dp[i+2][0][3*j/__gcd(3,j)] += __gcd(3,j)*dp[i][1][j]) %= mo; // 112222 // 222112 if(C%6==0) (dp[i+2][0][6*j/__gcd(6,j)] += __gcd(6,j)*dp[i][1][j]) %= mo; // 2122 // 2121 // 2221 if(C%4==0) (dp[i+3][0][4*j/__gcd(4,j)] += __gcd(4,j)*dp[i][1][j]) %= mo; // 3333 // 3333 (dp[i+2][1][j] += dp[i][0][j])%=mo; } } ll tot=0; FOR(i,25) tot+=dp[R][0][i]+dp[R][1][i]; _P("Case #%d: %d\n",_loop,tot%mo); }
まとめ
面白い問題作るなぁ。
