２次試験再現答案（2013年度分）[TRIC-006-03]
2013年度分の２次試験の問題を入手したので、こちらに回答を載せる。
※あくまで自分の解き方・考え方を書いたものであり、答えを保証するものではありません。
目次
情報工学 ハードウェア
【回答】
準備中...
【総評】
【解説】
情報工学 ソフトウェア
【回答】
6-A
(1)
3クィーン問題：0
4クィーン問題：2
(2)
int migidame(int vec[], int i, int j) {
if (vec[i] == vec[j]) return 1;
else return 0;
}
int migiuedame(int vec[], int i, int j) {
if (vec[i]+i == vec[j]+j) return 1;
else return 0;
}
int migishitadame(int vec[], int i, int j) {
if (vec[i]-i == vec[j]-j) return 1;
else return 0;
}
(3)
| vec[0] |
vec[1] |
vec[2] |
vec[3] |
j |
| 0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
0 |
1 |
| 0 |
2 |
0 |
0 |
2 |
| 0 |
3 |
0 |
0 |
2 |
| 0 |
3 |
1 |
0 |
3 |
| 1 |
0 |
0 |
0 |
1 |
| 1 |
3 |
0 |
0 |
2 |
| 1 |
3 |
0 |
0 |
3 |
| 1 |
3 |
0 |
2 |
4 |
| 2 |
0 |
0 |
0 |
1 |
| 2 |
0 |
0 |
0 |
2 |
| 2 |
0 |
3 |
0 |
3 |
| 2 |
0 |
3 |
1 |
4 |
| 3 |
0 |
0 |
0 |
1 |
| 3 |
0 |
0 |
0 |
2 |
| 3 |
0 |
2 |
0 |
3 |
| 3 |
1 |
0 |
0 |
2 |
以上、全17回
(4)
プログラムでは列の左側から検索を行っているが、検索の途中の段階で
アタリが発生した場合、それより右の検索を省略している。
省略できる根拠として、アタリが発生している状態にどのように
クィーンを加えても、既に発生しているアタリの解消にはならないからである。(124字)
(5)
int kotaenokazu(int vec[], int j) {
int count;
count = 0;
int i;
if (j >= N) return 1;
for (i = 0; i < N; i++) {
vec[j] = i;
if (ok(vec, j)) count = count + kotaenokazu(vec, j+1);
}
return count;
}
(6)
int ok(ATARI a, int j) {
if ((a.migi & (1<<j)) || (a.migiue & (1<<j+1)) || (a.migishita & (1<<j-1)))
return 0;
else return 1;
}
(7)
ATARI next(ATARI a, int k) {
a.migi = a.migi | (1<<k);
a.migiue = (a.migiue>>1) | (1<<k);
a.migishita = ((a.migishita<<1)&((1<<N)-1)) | (1<<k);
return a;
}
(8)
高速化する前のプログラムでは、ok関数は並べられたクィーン同士のアタリを
個別に判定するため、要素数nに対してO(n)の計算量が必要になる。
高速化した後のプログラムでは並べられたクィーンを1回の計算でまとめて
おこなうため、ok関数の計算量はO(1)に改善されている。
ok関数を呼び出す側の計算量は変わらず、行と列ごとに処理を行うため
計算量はO(n^2)となる。1回の処理につき1回のok関数が呼ばれるため、
全体の計算量はO(n^3)→O(n^2)に改善されている。(224字)
【総評】
【解説】
6-A
(1)
後の問題にも記述があるように、N=3の時は解を持たない。
N=4の時の解は以下の2通り。
(2)
特にこれといった注意点は無い。
(3)
地道に数える。ミスをしているかもしれない。
「nqueen関数の引数の値を全て列挙することにより答えよ」という書き方は
不親切極まりない（配列のポインタの値を書けば良いのでしょうかね）ですが、
出題者の意図を汲み取ると回答のような書き方で良いと思われる。
(4)
if (ok(vec, j)) nqueen(vec, j+1);
の前半のif文が計算量の削減を行っている部分である。
全数チェックをする(最悪の計算量で計算する)のであれば、
nqueenを先に呼んで全てのクィーンを確定させた上でok関数を呼ぶ。
(5)
基本的にはnqueen関数を参考にする。
print(vec)が条件を満たすvecに到達した場合の処理となるため、
それを1を返すよう処理を置き換えれば良い。
再帰から戻った際には、戻り値(条件を満たすパターンの数)を全て足せば良い。
(6)
問題文に沿って考える。
migi関数は考えればすぐに分かる。
migiue, migishitaはどこまでの処理をこの関数内で行うか悩ましいが、
次に出題されるnext関数で右上、右下に「ずらす」処理をやると考え、
ここでは純粋にANDを取って、どこかのビットが立っていれば
アタリが発生していると考えれば良い。
(7)を記述した後に、初期状態(migi=migiue=migishita=0の状態)を考え、
その際にmigiueとmigishitaではANDを取る際に1つずらさないと
正しい計算にならないことに気付いたため、回答を修正した。
(7)
基本的に問題文に書かれていることをそのままコードに変換するだけで良い。
(8)
回答を書いた後に気がついたのだが、ok関数の呼び出し元の計算量は
O(n^2)ではなくO(n!)なのではないだろうか。
問題文にもそのように書かれていたし。
最終更新：2013年06月10日 00:35
