salt - SALT TREE XV Editorial /

Time Limit: 0 msec / Memory Limit: 64 MiB

AtCoder での提出方法

現在,この問題には提出できません.他のオンラインジャッジを利用してください.

配点 : 100 点

問題文

SALT TREE XV(“salt tree the fifteenth” と読む)は二人のプレイヤーで遊ぶゲームである.最初二人には一つの木が与えられる.二人は交互に木の辺か頂点を取る.プレイヤーが辺を取った場合,単にその辺が消滅する.プレイヤーが頂点を取った場合,その頂点だけでなく頂点に接続している辺があればそれらの辺も消滅する.最後の頂点(LAST VERTEX)を取ったプレイヤーが勝者となる.

SALT TREE XV で先手が最善を尽くした場合,後手がどんな手を打っても必ず先手が勝つことが証明できる.先手としてプレイして必ず勝つプログラムを書け.

補足

頂点を一つ以上持ち,閉路を持たない連結なグラフを木という.例えば,次の三つはどれも木である.

2007-salt-trees.png

次の三つのグラフはどれも木でない.左下のグラフと中央のグラフは閉路を持つので木ではない.右下のグラフは連結でないので木ではない.

2007-salt-nontrees.png

例

次の木が与えられた場合を考える.

2007-salt-step1.png

先手が辺 (5, 7) を取ると,次のようになる.

2007-salt-step2.png

続いて後手が頂点 4 を取ると,次のようになる.

2007-salt-step3.png

続いて先手が頂点 3 を取ると,次のようになる.

2007-salt-step4.png

入力

プログラムは salt.in から木のデータを読み込む.salt.in は次のような構造をしている.この例は上の木に対応している.

7
3 4
5 7
4 6
2 4
1 4
1 7

1 行目には木の頂点の個数 n (1 \leqq n \leqq 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
g++ -O2 -lm salt.cpp saltc.o -o salt

とすることでコンパイルできる(上が C 言語,下が 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
./salt-fake java Salt

のように呼び出す(上が C/C++,下が Java の場合).

先手プログラムと後手プログラムは標準入出力を通して通信をするので,標準入出力を使うと予測のつかない結果になる可能性があることに注意せよ.

salt-fake はあくまでも受験者が動作確認のために使用できるように提供されるだけであり,実際の採点ではこれとは異なる方法で実行する可能性がある.

採点

テストデータは複数用意されている.各テストデータにつき,何度かゲームを行い,プログラムがつねに勝てばそのテストデータの分の点数を与える.プログラムがゲームのルールに照らして正しくない手を指定した場合や,ゲームに負けた場合,ゲームに勝つ前に終了した場合は,そのテストデータの点数は与えない.


Source Name

JOI 2006-2007 春季トレーニング合宿 Contest Day2