AOJ0508 String With Rings

問題リンク String With Rings

• 解法 ?

えー、先に言っておきますと真っ当な方法でAcceptに辿りついていません。
真面目なプログラムで解きたい方の疑問には答えられません、よしなに。

以下、自分の思考の変遷をつらっと書きます。

1. 反復深化法でいこう
到達できると思う深さを決め打ちし、全開始点を試す。どの開始点でも到達できなかったらその深さ-1が答えだ、というもの。結構速く終わるんじゃないかと期待。結果はTLE

2. 反復深化法を改良しよう
毎回全開始点を試すのは無駄だ。頂点1で深さを改良できるまで改良し、深さDまで潜れることが分かったら、頂点2はD+1から始めればいいじゃないか。おお、探索回数がぐっと減るぞ！ 結果はTLE

3. グラフを縮約しよう
次数が2の頂点は縮約し、辺に重みを加えれば、探索に使う頂点数が減ってハッピーだな、と思い付く。縮約してはいけないパターンや、再帰でちょこっと例外処理を加えてなんとかサンプルを通す。提出だ！！ 結果はTLE

4. ジャッジデータを覗こう
こりゃ埒があかない。ジャッジデータを持ってきてどんだけ遅いか計測しよう。10秒ちょっとで終わる(TLEは16秒)。答えも合ってる。どういうこっちゃ？分かった。提出したものを間違えたんだ。提出。結果はTLE

5. 公式解説を見よう
「効率的な方法はないから全探索。スタックとか使うと速いかもよ」で終了。

6. 反復深化法をやめよう
意外とこれで通るんじゃないか？結果はTLE

7. 再帰をやめてスタックにしよう
スタックで書けない・・・終了

8. 他のひとのブログを見に行こう
「嘘解法」「次数が小さい頂点を探索すればいい！」「通せん・・・」などなど

9. 次数が小さい頂点だけを開始点にしよう
出現する次数の最小値と最大値の平均値以下の頂点のみを開始点にしてみる。結果はTLE

10. AOJのジャッジデータが壊れてるに違いない
ローカルとAOJでどうしてこんなに時間に差があるんだ？これはもしかするかもしれないぞ。すぐ終了するプログラムを投げよう。これでTLEだったら、運営様に報告しよう。結果はWA

11. この瞬間に自分の思考がぶっ壊れたに違いない
開始点を何とか絞りたい！どうする！？
ﾋﾟｺｰﾝ！！
ランダムに選べばいいんじゃね？

12. 乱数を使う()
使う頂点数は全体の半分で十分だろう。実行時の時間をシードにしてプログラムを走らせまくり、答えが一致するシード値を探す（←なにしてんのこの人）。見つけた提出。はぁ〜、ようやく通せたかー。　結果はTLE

13. もっと絞る
半分がだめなら3分の1にすればいいじゃない。再びシード値を探す。提出。
Accepted!!???

14. 反省する
TLEを10個くらい量産してどうにかなってましたね。これ、答えが正しくでるシード値を採用している時点で、もはやプログラムの意味がないものになってますね。
この問題をJavaで通すための効果的な絞り込みはどう行うのでしょうか。もっと実力がついたころに、リベンジしたい1問です。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

//String With Rings
public class AOJ0508 {

	List<Integer>[] e;
	int res;
	boolean[] v;
	
	void dfs(int k, int d){
		res = Math.max(res, d);
		for(int x:e[k])if(!v[x]){
			v[x] = true;
			dfs(x, d+1);
			v[x] = false;
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		Random rand = new Random(1334259345907L);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			e = new List[101];
			for(int i=1;i<101;i++)e[i]=new ArrayList<Integer>();
			boolean[] u = new boolean[101];
			while(n--!=0){
				int a = sc.nextInt(), b = sc.nextInt();
				u[a] = u[b] = true;
				e[a].add(b); e[b].add(a);
			}
			v = new boolean[101];
			res = 0;
			int[] a = new int[100];
			int id = 0;
			for(int i=1;i<101;i++)if(!e[i].isEmpty())a[id++] = i;
			//開始点を全部試すとつらいからN/3個だけランダムにチョイスして絞るという迷走っぷり
			for(int i=0;i<=id/3;i++){
				Arrays.fill(v, false);
				int s = rand.nextInt(id);
				v[a[s]] = true;
				dfs(a[s], 1);
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ0508().run();
	}
}