はじめに
本家『「解けない問題」を知ろう』では、NP完全や決定不能などの問題が紹介されています。
しかし、これらの問題はオンラインジャッジなどで出題されることはほとんど無いか、
出題されても全探索や動的計画法/メモ化探索、分枝限定法などで解けるような小さいサイズの問題が多いでしょう。
しかし、世の中にはこれらの理論上解けない、もしくは解けなそうな問題以外にも、「解けない問題」が存在します。
この記事では、どのような問題がそのような「解けない問題」かを紹介します。
なお、この記事中の例題においては、以下のことを仮定します。
- 実行時間制限は1秒
- メモリは十分使用できる
- 問題文や入力中の数値は全て十進数 (これを仮定しないと、世の中の多くの問題が「解けない問題」になってしまいます)
「解けない問題」の例
制約が大きすぎる
例題
M×Nのグリッドが与えられ、各マスに非負整数が割り当てられている。
左上のマスから出発し、右下のマスに行くまでに通るマスに割り当てられている数の和を最大にしたい。
1回で行けるのは下に1マスまたは右に1マスのみである。
グリッドの外に出ることはできないが、それ以外は常に下にも右にも移動できる。
通るマスに割り当てられている数の和を最大にした時の和を求め、十進数で1行で出力せよ。
入力
入力はN+1行からなる。
1行目には、正の整数M, Nがこの順番で、1個の半角空白を区切りとして与えられる。
2行目～N+1行目には、グリッドに書かれている数値がそれぞれ1個の半角空白を区切りとしてM個与えられる。
y+1行目に書かれている左からx個目の数値が、グリッドの上からy番目、左からx番目のマスに割当られている数である。
出力
左上のマスから右下のマスに行くまでに通るマスに割り当てられている数の和の最大値を1行で出力せよ。
サンプル入力
3 3
1 1 5
2 1 1
2 2 1
サンプル出力
9
嘘解法
# include <stdio.h>
# include <stdlib.h>
int main(void) {
int M, N;
int *grid;
int x, y;
/* 入力を読み込む */
if(scanf("%d%d", &M, &N) != 2) return 1;
grid = malloc(sizeof(int) * M * N);
if (grid == NULL) return 1;
for (y = 0; y < N; y++) {
for (x = 0; x < M; x++) {
if (scanf("%d", &grid[y * M + x]) != 1) return 1;
}
}
/* 動的計画法で求める */
/* 左端の処理 */
for (y = 1; y < N; y++) {
grid[y * M + 0] += grid[(y - 1) * M + 0];
}
/* 上端の処理 */
for (x = 1; x < M; x++) {
grid[0 * M + x] += grid[0 * M + (x - 1)];
}
/* それ以外の部分の処理 */
for (y = 1; y < N; y++) {
for (x = 1; x < M; x++) {
int u = grid[(y - 1) * M + x]; /* 上から来る */
int l = grid[y * M + (x - 1)]; /* 左から来る */
grid[y * M + x] += (u >= l ? u : l); /* 和が小さくない方を選ぶ */
}
}
printf("%d\n", grid[(N - 1) * M + (M - 1)]);
free(grid);
return 0;
}
なぜ解けないか
この問題においては、M, Nの範囲は正の整数としか書かれておらず、
グリッドの各マスに書かれている数は非負整数としか書かれていない。
すなわち、正の整数全てに対応する必要がある。
ということは、当然100000×100000とか、
100000000000000000000000000000×100000000000000000000000000000とかのサイズにも対応しなけばならない。
これらはおそらく現代のコンピュータでは不可能であろう。
解ける例題
M×Nのグリッドが与えられ、各マスに非負整数が割り当てられている。
左上のマスから出発し、右下のマスに行くまでに通るマスに割り当てられている数の和を最大にしたい。
1回で行けるのは下に1マスまたは右に1マスのみである。
グリッドの外に出ることはできないが、それ以外は常に下にも右にも移動できる。
通るマスに割り当てられている数の和を最大にした時の和を求め、十進数で1行で出力せよ。
入力
入力はN+1行からなる。
1行目には、正の整数M, Nがこの順番で、1個の半角空白を区切りとして与えられる。
2行目～N+1行目には、グリッドに書かれている数値がそれぞれ1個の半角空白を区切りとしてM個与えられる。
y+1行目に書かれている左からx個目の数値が、グリッドの上からy番目、左からx番目のマスに割当られている数である。
制約
- M, Nは1以上1000以下の整数
- 各マスに割り当てられている数は0以上100以下の整数
出力
左上のマスから右下のマスに行くまでに通るマスに割り当てられている数の和の最大値を1行で出力せよ。
サンプル入力
3 3
1 1 5
2 1 1
2 2 1
サンプル出力
9
モデル化が不十分
例題
整数nが与えられる。サイコロを2個振った時、出た目の和がnになる確率を求め、既約分数で求めよ。
ただし、分母が1の時は整数で出力せよ。
入力
入力は1行からなり、整数nが与えられる。
制約
- nは1以上12以下の整数
出力
サイコロを2個振った時、出た目の和がnになる確率を1行で出力せよ。
サンプル入力1
1
サンプル出力1
0
サンプル入力2
2
サンプル出力2
1/36
嘘解法
# include <stdio.h>
int gcd(int x, int y) {
int r;
while (y > 0) {
r = x % y;
x = y;
y = r;
}
return x;
}
int main(void) {
int n;
int i, j, cnt, g;
if (scanf("%d", &n) != 1) return 1;
cnt = 0;
for (i = 1; i <= 6; i++) {
for (j = 1; j <= 6; j++) {
if (i + j == n) cnt++;
}
}
g = gcd(cnt, 36);
if (g == 36) printf("%d\n", cnt / 36);
else printf("%d/%d\n", cnt/g, 36/g);
return 0;
}
なぜ解けないか
「サイコロ」というだけでは、何面ダイスなのかわかりません。
また、各面が出る確率の分布もわかりません。
解ける例題
1回振ると、1以上6以下の6個の整数の中から1個の目が独立に等確率で出るサイコロを用意する。
整数nが与えられる。このサイコロを1回、2個振った時、
出た目の和がnになる確率を求め、既約分数で求めよ。
ただし、分母が1の時は整数で出力せよ。
入力
入力は1行からなり、整数nが与えられる。
制約
- nは1以上12以下の整数
出力
このサイコロを1回、2個振った時、出た目の和がnになる確率を1行で出力せよ。
サンプル入力1
1
サンプル出力1
0
サンプル入力2
2
サンプル出力2
1/36
終わりに
このような「解けない問題」に嘘解法を提出してたまたま正解と判定されても、
それはたまたまテストケースが弱かっただけで、問題が解けたわけではありません。
しかし、コンテストなどの状況においては、嘘解法でも通りそうだと判断したら、
とりあえず嘘解法を提出し、得点を得ることも重要な戦術である。