AGC041 - C - Domino Quality
概要
N * Nのフィールド上に、1*2のサイズのドミノを1枚以上、任意の枚数置く。回転させてもいいが、ドミノ同士は重なってはいけない。
この時、ある行or列について、その上に乗ってるドミノの数をxとする。すべての行と列について、その上に乗ってるドミノの数、すなわちxは等しいようなドミノの置き方を出力せよ。複数あるのならばそのうちのどれでもよい。また、置けないのならば-1と出力する。
制約: 2 <= N <= 1000
ACするまで
1. 手元で実験をしてみると、2*2は不能で、3*3は可能である。
2. 3*3は可能ってことは、3*3を1ブロックとして、そのブロックで構成された形、すなわち3k*3kの形ならば作れる。
3. 4*4はいろいろ試すと、できるとわかる。同様に4k*4kもできる。
4. 5*5を手でいろいろ試すも見つからない。
5. コンテスト終了
6. こういうタイプの問題の定石、対角線で置くで考える。そうすると、qualityが同じ2つのブロック(1辺AとB)を対角線上に置けば、(A+B)が1辺のが作れる。
7. 頑張って全探索とかエスパーとかをすると、5*5も6*6も7*7も実はquality=3の解が存在する。(は？)
8. というわけで、quality = 3で考えると、4, 5, 6, 7は作れるので、あまり的に4x+yという形のものはすべて作れる。よって、N==2以外は全部作れるな(N==3は専用のを出力すればよい)
9. 実装をする。AC！
考察
このような構築では、下記の記事でまとめたように、
「行or列が条件を満たすものは、行or列が条件を満たすものを対角線状に置くことで新しく作れる」
この性質から、いくつかの条件を満たすミニブロックを作って、そいつらを足し合わせることで、また、より大きいのが作れそうとわかる。
今回の場合、ミニブロックを対角線状において新しく作れる条件は、「対角線状に置かれてるミニブロックすべてのQualityは同じ」である。
さて、手でも、パソコンでも全探索でも、ひとまず条件を満たすような小さいN*Nの答えを求めてみる。(全探索プログラムを後ろに添付する。N=6までならすぐに出る。N=7は40分回してもまだ出ない・・・)
そうすると、3*3, 4*4, 5*5, 6*6, 7*7にはちゃんと答えがあるとわかり、かつ4*4~7*7はみなQuality = 3だとわかる。つまり、これらをもとに、より大きいのを作ることができるということである。
ここで、あまりに着目してみる。4, 5, 6, 7はちょうど4つ連続してるので、それぞれ4で割ったあまりが0, 1, 2, 3に対応してる。
このことから、大学受験的に4x + y(0 <= y <= 3)と立式できる。(yは余り0~3に対応)。この式から、Nのあまりに応じて、基本的に対角線状に4*4を置いて、最後にあまりに対応する5*5, 6*6, 7*7を置けばよい、とわかる。
ACソースコード：
N=6までは探索の結果、N=7はあきらめて答えのを使った
Submission #9202515 - AtCoder Grand Contest 041
全探索に使ったプログラム
枝刈りがんばりましたがN=7が終わりません。全探索でN=7が出た人は私にそのソースコードをくれると嬉しいです。(Twitter: @nonpro3)
#include<iostream> #include<algorithm> #include<functional> #include<stack> #include<tuple> #include<vector> using namespace std; typedef long long ll; typedef tuple<vector<vector<int>>, int, int, int> Tp; int N; //行のクオリティを数える。列のクオリティは面倒なので関数化はしない int calc_row_quality(vector<int>& ar) { int ret = 0; if (ar[0] != 0)ret++; for (int i = 1; i < N; i++) { if (ar[i] != ar[i - 1] && ar[i] != 0) { ret++; } } return ret; } int main() { cin >> N; vector<vector<int>> b(N, vector<int>(N)); stack<Tp> S; S.push(make_tuple(b, 0, 1, -1)); while (S.size()) { auto now = S.top(); S.pop(); int i = get<1>(now) / N, j = get<1>(now) % N; int domino_cnt = get<2>(now); auto now_f = get<0>(now); int ruled_quality = get<3>(now); if (get<1>(now) == N * N) { //全部埋め終わった。 bool f = true; int quality = ruled_quality; if (quality == 0)continue; if (f && calc_row_quality(now_f.back()) != quality) { f = false; } for (int i = 0; i < N; i++) { int tmp = 0; if (now_f[0][i] != 0)tmp++; for (int j = 1; j < N; j++) { if (now_f[j][i] != now_f[j - 1][i] && now_f[j][i] != 0) { tmp++; } } if (f && tmp != quality) { f = false; } } if (f) { //printans cout << "quality = " << quality << endl; cout << "the detail is" << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (now_f[i][j] == 0)cout << "."; else cout << (char)('a' + (now_f[i][j] - 1)); } cout << endl; } cout << endl; } continue; } //1行目を埋め終わったときに、qualityを求めて、以降それで枝狩りする。 if (i == 1 && j == 0) { ruled_quality = calc_row_quality(now_f[0]); //Qualityが3である前提でいく if (ruled_quality != 3)continue; } //丁度1行埋め終わったときに、qualityを見て枝刈りをする int row_quality = (i >= 1 && j == 0 ? calc_row_quality(now_f[i - 1]) : ruled_quality); if (ruled_quality != row_quality)continue; //丁度1列埋め終わったときに、qualityを見て枝刈りをする if (i >= N - 1 && j >= 1) { int tmp = 0; if (now_f[0][j - 1] != 0)tmp++; for (int k = 1; k < N; k++) { if (now_f[k][j - 1] != now_f[k - 1][j - 1] && now_f[k][j - 1] != 0) { tmp++; } } if (tmp != ruled_quality) { continue; } } //(i, j)に何も置かない S.push(Tp(now_f, get<1>(now) + 1, domino_cnt, ruled_quality)); //(i, j)に縦で置いてみる。 if (i + 1 < N && now_f[i][j] == 0 && now_f[i + 1][j] == 0) { now_f[i][j] = domino_cnt, now_f[i + 1][j] = domino_cnt; S.push(Tp(now_f, get<1>(now) + 1, domino_cnt + 1, ruled_quality)); now_f[i][j] = 0, now_f[i + 1][j] = 0; } //(i, j)に横で置いてみる。 if (j + 1 < N && now_f[i][j] == 0 && now_f[i][j + 1] == 0) { now_f[i][j] = domino_cnt, now_f[i][j + 1] = domino_cnt; S.push(Tp(now_f, get<1>(now) + 1, domino_cnt + 1, ruled_quality)); now_f[i][j] = 0, now_f[i][j + 1] = 0; } } return 0; }
一言
7*7を手で作った人、頭の中がわからない。
