Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-17SRM397 (Practice)

ぐぬぬ・・・

205/560位

問題結果ポイントその他
250SortingGameAccepted200.66全探索
500SumOfPowersOpened0.00数学ゲー?漸化式に落としこむ?
1000 HouseProtectionUnopened0.00見てない

SRM 397 SortingGame

|  SRM 397 SortingGame - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 397 SortingGame - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8745


コーディングフェーズ

  • 連続する k 個の数字を選び、ひっくり返す
    • {1, 2, ..., n} にする最小手数を求めよ
  • 1から順番に固定する?
    • うーん最適かどうか怪しい気がする。でも合ってるような気もする
  • 神にすがる思いで制約を見る
    • n <= 8 !! これなら全探索できる!
  • 幅優先探索する
    • 状態は数列で、高々 8! <= 40,320
    • ある状態から可能な操作をしたあとの数列を全部キューに突っ込む
    • 一度見た状態はメモしておいてパスする
    • ループを抜けた時、メモに目的の数列が入ってればそのターン数、無ければ-1
  • できた。
    • サンプル通った。
    • 念のため制約を確認
      • k>=2 だし大丈夫
    • 最大ケースを確認
      • ({8,7,6,5,4,3,2,1}, 2)で0.2s。OK
    • forの条件を1つ緩くして配列外アクセスエラーが出るか確かめる
      • ちゃんとエラーになってくれた。OK
  • おそらく大丈夫でしょう。提出

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class SortingGame {

	
	public List<Integer> tolist(int[] a) {
		List<Integer> l = new ArrayList<Integer>();
		for (int i : a) {
			l.add(i);
		}
		return l;
	}
	
	
	public class State {
		int[] list;
		int turn;
		State(int[] l, int t) {
			list = l;
			turn = t;
		}
	}
	
	public int fewestMoves(int[] board, int k) {
		Map<List<Integer>, Integer> mv = new HashMap<List<Integer>, Integer>();
		List<Integer> obj = new ArrayList<Integer>();
		
		int n = board.length;
		for (int i = 1 ; i <= n ; i++) {
			obj.add(i);
		}
		
		
		Queue<State> q = new ArrayBlockingQueue<State>(100000);
		q.add(new State(board, 0));
		
		while (q.size() >= 1) {
			State s = q.poll();
			int[] f = s.list;
			List<Integer> fl = tolist(f);
			if (mv.containsKey(fl)) {
				continue;
			}
			mv.put(fl, s.turn);
			
			for (int i = 0 ; i <= n-k ; i++) {
				int[] newb = f.clone();
				for (int j = i ; j < i+k/2 ; j++) {
					int z = (i+k-1)-(j-i);
					int tmp = newb[z];
					newb[z] = newb[j];
					newb[j] = tmp;
				}
				q.add(new State(newb, s.turn+1));
			}
		}
		
		
		if (mv.containsKey(obj)) {
			return mv.get(obj);
		}
		return -1;
	}
}

SRM 398 SumOfPowers

|  SRM 398 SumOfPowers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 398 SumOfPowers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8725


コーディングフェーズ

  • うわー、数学ゲーだ
    • f(n,k) = 1^k + 2^k + ... + n^k とおく
  • 式をこねくり回してみる・・・
    • f(n,k+1) = n * f(n,k) + f(n-1,k+1) - n * f(n-1, k) を得た
      • うーん、kが一方的に減っていかないと嬉しくない・・・
  • 気を取り直してとりあえず常套手段、f(n,k) を紙に書き出してみる

n\k1234567
11111111
2359173365129
361436982767942316
4103010035413004890・・・
  • うーむ、全然見えてこない
  • 詰んだ
    • MODの性質を利用するのかな?全然分からん
  • 時間切れ。

その後

  • editorialを読む。
  • 言われてみれば自然な発想だ・・・
    • 行列の形に持ち込めば累乗はlognで計算できるもんね

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SumOfPowers {
	long MOD = 1000000007;
	
	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]) % mod;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}
	
	public int value(int n, int k) {
		long[][] ncr = new long[100][100];
		ncr[0][0] = 1;
		for (int i = 1 ; i < 100 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1]) % MOD;
			}
		}
		
		long[][] tbl = new long[k+2][k+2];
		tbl[0][0] = 1;
		for (int i = 1 ; i < k+2 ; i++) {
			tbl[0][i] = ncr[k][i-1];
		}
		for (int i = 1 ; i < k+2 ; i++) {
			for (int j = i ; j < k+2 ; j++) {
				tbl[i][j] = ncr[k+1-i][j-i];
			}
		}
		
		long[][] tbln = pow(tbl, n-1, MOD);
		long ans = 0;
		for (int i = 0 ; i < k+2 ; i++) {
			ans = (ans + tbln[0][i]) % MOD;
		}
		return (int)ans;
	}
}