SALT TREE XV (Salt)
時間制限 : 3sec / スタック制限 : 64MB / メモリ制限 : 64MB
SALT TREE XV ("salt tree the fifteenth" と読む) は二人のプレイヤーで遊ぶゲームである。最初二人には一つの木が与えられる。二人は交互に木の辺か頂点を取る。プレイヤーが辺を取った場合、単にその辺が消滅する。プレイヤーが頂点を取った場合、その頂点だけでなく頂点に接続している辺があればそれらの辺も消滅する。最後の頂点(LAST VERTEX) を取ったプレイヤーが勝者となる。
SALT TREE XV で先手が最善を尽くした場合、後手がどんな手を打っても必ず先手が勝つことが証明できる。先手としてプレイして必ず勝つプログラムを書け。
補足
頂点を一つ以上持ち、閉路を持たない連結なグラフを木という。例えば、次の三つはどれも木である。
次の三つのグラフはどれも木でない。左下のグラフと中央のグラフは閉路を持つので木ではない。右下のグラフは連結でないので木ではない。
例
次の木が与えられた場合を考える。
先手が辺(5, 7) を取ると、次のようになる。
続いて後手が頂点4 を取ると、次のようになる。
続いて先手が頂点3 を取ると、次のようになる。
入力
プログラムはsalt.in から木のデータを読み込む。salt.in は次のような構造をしている。この例は上の木に対応している。
7
3 4
5 7
4 6
2 4
1 4
1 7
1 行目には木の頂点の個数n (1 ≦ n ≦ 1000) が書かれている。木の頂点は1 からn までの整数でラベル付けされる。2 行目からn 行目までのn - 1 行には木の辺の両端の頂点の番号が書かれている。各辺はちょうど1 度ずつ出現し、出現順には意味がない。各辺はラベルの小さい頂点、大きい頂点の順に書かれる。
インターフェース
プログラムは以下のインターフェースを通して後手のプログラムと通信する。
C/C++ 版
次のようにしてインクルードファイルsaltc.h をインクルードすること。
#include "saltc.h"
プログラムはライブラリーの次の関数を呼ぶ必要がある。
void turn(int u, int v, int* ru, int* rv); 最初の二つのパラメーターは先手(あなた)の手番に行うことを指定する。u = v のときは、頂点u を取ることを意味する。u < v のときは、頂点u と頂点v を結ぶ辺を取ることを意味する。u > v であってはいけない。後の二つのパラメーターでは、後手の手番に行われたことを読み取る。ru とrv は有効なポインターでなければならず、また同じ領域を指していてはいけない。*ru と*rv は上のu, v と同じ意味を持つ。*ru > *rv となることはない。ただし、あなたが最後の頂点を取った場合は、*ru と*rv は0 となる。この場合は、他のAPI 関数を呼ばずに終了しなければならない。
saltc.o のソースファイルはsaltc.c という名前で置いてある。
プログラムは、saltc.o とsaltc.h をカレントディレクトリにコピーして、
gcc -O2 -lm salt.c saltc.o -o salt (C 言語の場合)
g++ -O2 -lm salt.cpp saltc.o -o salt (C++ の場合)
とすることでコンパイルできる。
Java 版
プログラムはライブラリーの次の関数を呼ぶ必要がある。
static int[] Saltj.turn(int u, int v); パラメーターは先手(あなた) の手番に行うことを指定する。u = v のときは、頂点u を取ることを意味する。u < v のときは、頂点u と頂点v を結ぶ辺を取ることを意味する。u > v であってはいけない。返り値はint 型のサイズ2 の配列である。この配列をr とする。r[0] とr[1] は、後手の手番に行われたことを表す。r[0] とr[1] は上のu, v と同じ意味を持つ。r[0] > r[1] となることはない。ただし、あなたが最後の頂点を取った場合は、r[0] とr[1] は0 となる。この場合は、他のAPI 関数を呼ばずに終了しなければならない。
Saltj.class のソースファイルはSaltj.java という名前で置いてある。
プログラムをコンパイルするときは、Saltj.class をカレントディレクトリにコピーしておく必要がある。
出力
プログラムは何も出力してはいけない。
動作確認用プログラム
実行ファイルを作ったら、動作確認のため、ランダムな手を返す後手のプログラムと対戦させることができる。salt-fake という名前で入っている。なお、このプログラムは頂点が15 個以下のグラフでしか動作しないようになっている。
カレントディレクトリにsalt.in を置き、
./salt-fake ./salt (C/C++ の場合)
./salt-fake java Salt (Java の場合)
のように呼び出す。
先手プログラムと後手プログラムは標準入出力を通して通信をするので、標準入出力を使うと予測のつかない結果になる可能性があることに注意せよ。
salt-fake はあくまでも受験者が動作確認のために使用できるように提供されるだけであり、実際の採点ではこれとは異なる方法で実行する可能性がある。
採点
テストデータは複数用意されている。各テストデータにつき、何度かゲームを行い、プログラムがつねに勝てばそのテストデータの分の点数を与える。プログラムがゲームのルールに照らして正しくない手を指定した場合や、ゲームに負けた場合、ゲームに勝つ前に終了した場合は、そのテストデータの点数は与えない。
コメント
最終更新：2013年02月23日 21:42
