Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2013-02-10

[]JOI本選2013オープンコンテスト 18:25 はてなブックマーク - JOI本選2013オープンコンテスト - TopCoderの学習のお時間


突然のオープンコンテストでうれしいイベント。


1


交互になってる区間を調べて…とやろうとしたら交互の判定が少し面倒。

全体を最初に010101...とxorとってやると、01が交互になっている区間→同じ数字が並んでいる区間 と言い換えられて考えるのが楽になる。

あとは隣り合った3つ以下の区間で長さの合計が最大のものが答え。

1度デバッグ出力残したまま提出してWAしてしまった


1ってこんな難しいんだっけ


2


いかにもDP

偶数番目と奇数番目で使う文字が違うのでDP用の配列を2つ用意した。1つでもできるとは思う。



3


時間きつそうなのでC++で。

ただの最短路じゃないかと思ってダイクストラ書いてたら全然通らない。60点しか取れず。

隣接するノードにだけじゃなくて到達可能なノード全部に枝を張ってたのでそれが原因かもしれないが、TLEだけじゃなくてWAもあるので通らない原因はほかにもあるのだろう


4


dp[i][j]:=i文字目まで見たときに、リーチのものがj個ある状態での最大ミニ塔作成個数 でDPした。

N^2で50点。


状態としてリーチのもの(先頭2個まで集めたミニ塔)の個数だけ覚えておけばいいのは、先頭1個だけの作成途中ミニ塔がいくつあるかは単純に「i文字目までのI,Jの数-作成したミニ塔の数*2-リーチの個数」で出せるので考えなくても良いから。

それと、Oが出てきたときにあえて使わないことで状況がよくなることはないから。


5


部分点狙いのO(N^2)に絞って考えた。

ひとまず2つを入れ替えるというのは置いておいて、i番目の数字をj番目に置いたときに交換回数の変化がどうなるかを全部調べる。

これは1つのiについてjを1ずつずらしながら累積和取っていったら計算量O(N)でできるので全体O(N^2)。

あとはこれを使って、位置iと位置jの数字を入れ替えたときの交換回数の変化がO(1)で計算できるので全体でO(N^2)。

30点(Javaで書いたらTLEで20点しか取れなかったのでC++にしたら30点になった)。


合計


100+100+60+50+30=340点

オープン参加中4位/40人くらい


3問目ではまってしまって4・5をあまり考えられなかったのが残念。

こういうお楽しみコンテストのときは、デバッグに時間使うよりも面白そうな問題を考えた方が良いかな…

2012-12-08

[]第2回WUPC 20:34 はてなブックマーク - 第2回WUPC - TopCoderの学習のお時間

  • F
    • 部分点が設定されていないのでアルゴリズムの問題じゃなくて実装hardなのかなあ→じゃあ自分でもうまくいくとFirstAccept狙えるかも
    • ということでまず開く
    • てきとーに最短路やるだけにしか見えない
    • サクサク書いて出すとWAになった
    • 問題文を読み直すと、連続して同じ方向に進めないという制約を忘れていることに気づく
    • 方向の情報も状態に加えて再提出するとAC
    • たまたま同じ問題を狙ってた人がいなかったみたいでファーストアクセプト取れた
  • G
    • ブロックの数が多いので、特定の高さの所にどのブロックがあるかはSegmentTreeで高さ情報を管理して得ることにする
    • ライブラリ化してなかったので頑張って実装する
    • 出力のせいで一度TLEしただけですんなり通った。バグりやすそうな問題だけどこれはうれしい
  • H
    • ひとまず座標圧縮して駅の個数をMのオーダーにする
    • U・N・C・O区間の左端が小さい順に列車をソートしてDPする
    • dp[i][j][k]: 1〜iの列車を使って、1〜j番の駅には2つ以上の列車が止まって、j+1〜k番の駅には1つの列車が止まるような選び方の数
      • 追記:これだとMLEするのでiのところは2にして偶奇で切り替えるアレをやる
    • ひたすらWAって部分点すら全然通らない
    • ナイーブ解法と比較してみると、列車がないため訪問できないとしないといけない部分の座標が座標圧縮したときに潰れて無視されていることに気づいた
    • 列車の始点・終点の前後の座標も考慮対象に加えるとTLE→ちょっと定数倍高速化してAC
  • A
    • やる
  • B
    • 一瞬DPしそうになったけど、 Xが連続する個数/3 を加えていけばOK
  • C
    • やる
    • 全体を回転させたらすっきりできそうだけど長方形だと面倒かなーと思って、とてもださいコードを書いてしまった
  • D
    • 大きい順に詰める
      • 5、4+1、3+2+1、2+1、1
    • 頑張って漏れないよう数える
  • E
    • ループがない森の場合は、枝を1つ消すとかならず独立なグループが1つ増えるので、コストが小さいものから貪欲に消せば良い
    • ループがある場合、ループ内の枝を消す場合と消さない場合とで場合分けした
      • ループ内の枝を消す場合、ループ内の枝で一番コストが小さいものを消して、あとは森として扱う
      • ループ内の枝を消さない場合は、ループ以外の枝だけからコスト少ない順に消す
    • バグバグだったがなんとか終了間際に直せた
  • I
    • 読んだだけ
    • パッと見ではいもす法に見えるが…

2012-12-03

[]UTPC2012 01:54 はてなブックマーク - UTPC2012 - TopCoderの学習のお時間


practice

4個目のケースの問題文を前から1文字ずつ推測しようとして、WAとREとTLEとMLEで分岐させようとしたらMLEを意図的に発生させるのが難しくて挫折した(単純にでかい配列取るとREになる)

というか3分岐でも4分岐でもアルファベット1文字決めるのに3回のサブミットが必要なのは一緒だから気にしなくてよかった


本番

オンサイトで参加した。隣の席だったりんごさんが2Lの緑茶をおもむろに取り出して威嚇してきた


  • F
    • 部分点が???になってて面白そうだったのでまず見てみたけどすぐには方針立たないので次へ
  • E
    • きっと反例あるんだろうけどとりあえず二分探索で投げてみた→やっぱりWA
    • どうせ嘘解法なんだから時間制限いっぱいまで調べるようにしておけば良かった
  • A
    • やる
  • B
    • 後ろから
  • C
    • 完全グラフを想像すると、Nが大きい場合には絶対に森にならないというのはイメージできる
    • Nが小さいときはクエリを毎回処理する。エッジの本数で森かどうか自明にわからない場合はDFSで判定
    • DFSがバグってて時間かかってしまった
    • あとTLEケースもあったので普通の隣接行列じゃなくてBitSetで持って高速化した
    • けどTLEの原因はDFSがバグってたせいもあるはずなので、高速化しないといけなかったどうかは不明
  • D
    • 1つの辺を見ると回転角度θは分かるので
    • 不動点を(X,Y)とするとそれを中心に1/2倍してθ回転するアフィン変換を計算すると連立方程式になる
    • と思って計算してたら式がグロい感じになったので逃亡
  • G
    • スタンダードな組み合わせ+DP
    • いろいろバグってしまったけどサンプルが強かったので一発AC
  • E
    • 適当な上限から時間いっぱい調べるのを書いて部分点をもらう
  • F
    • なぜか最初a==26だと思い込んでて、任意のハッシュ値を持つ文字列を作るの可能やーん、とか思ってた。アホだ
    • 半分全列挙に近いアイディアでやった
    • 5文字の文字列を全部生成してハッシュ値とともにメモっとく。26^5≒10^8なので、最悪のb=10^9のときでも1/10くらいの確率で、ランダムに作った文字列をメモっておいた文字列のうちどれかと組み合わせて特定のハッシュ値にできる
    • 実際は5文字を全生成するとTLEしそうなので、4文字だけ全生成しておいてあとの1文字の分は毎回調べれば良い
    • これで提出したら190点になった
    • (あとで)全体の文字列のハッシュ値が0になるものを探していたけれど、bがaの累乗の場合はどうやっても0にならない場合があると気づいた
    • のでハッシュ値を1になるようにしてみたら今度は198点…
    • あと1ケースが何なのかよくわからない
  • D
    • 一応部分点だけ取っとく
  • L
    • 部分点は普通に木DPすれば良い
    • dp[i][j]で、ノードiの値をj以下にするのに必要な最小操作回数を表す
    • jの値は-200〜200くらいまで考えとけば十分のはず
    • 木の与え方が親切でうれしい
  • E
    • 適当な下限から時間いっぱい調べるのを書くが、残り時間少なくて焦っていたので賢くない方法になってしまい正解できず

手を付けなかった問題について

  • H
    • ぱっと見ではなんか区間をlogNで処理するようなややこしいデータ構造使うのだろうかと思って重く見えてしまった
  • I
    • 部分点だけならDPすればできそうに思ったけど実装しようとする気力とか時間がなかった
  • J
    • 問題文長いし、見るからにwataさんの問題でどうせ最小費用流だろうと思ったので飛ばした
  • K
    • 図形がやばそうなので飛ばした

提出履歴:http://utpc2012.contest.atcoder.jp/submissions/all?user_screen_name=tomerun


結果

  • 100 + 100 + 100 + 50 + 50 + 190 + 200 + 0 + 0 + 0 + 0 + 50 = 840
  • 総合24位/170チームくらい
  • 個人12位/150人くらい

反省とか感想とか

  • Cの単純なDFSでバグったのはやばすぎ
  • Dは解説を聞いた今でも解ける気がしない
  • Eでハマったのが痛すぎる。嘘解法なら嘘解法なりに考えて解けそうなのを出さないと
  • Fはとても楽しかった。乱択は良いものだ
  • Gはかなり得意な系統のはずだけど1時間近くかかっててひどい。サンプルがとても簡単なのととても難しいのしかなかったので、中間のを自分で用意してから書くとデバッグ速かったんではないだろうか
  • Hはちゃんと時間とって考えれば自力でできるかどうかギリギリくらいのとこなので記憶が薄れた数ヶ月後にもう一度やるべき
  • Iは面白そうなので後でやる
  • J,K,Lは鑑賞対象

2012-10-28

[]CodeSprint3 23:03 はてなブックマーク - CodeSprint3 - TopCoderの学習のお時間


https://cs3.interviewstreet.com/challenges/dashboard/#problems

ちょうどスケジュールあいてたので出てみた。

Webサイトの挙動が謎すぎて面白かった。問題は普通。


嘘解法(未証明解法)も混じってるけどいちおう満点




Exchange


交換できる関係をグラフと考えて、連結している範囲内は自由に交換できるので貪欲に

ワーシャルフロイドで推移閉包出す部分をミスってて2WA


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int K = sc.nextInt();
		int[] P = new int[K];
		for (int i = 0; i < K; ++i) {
			P[i] = sc.nextInt();
		}
		boolean[][] g = new boolean[K][K];
		for (int i = 0; i < K; ++i) {
			String line = sc.next();
			for (int j = 0; j < K; ++j) {
				g[i][j] = line.charAt(j) == 'Y';
			}
			g[i][i] = true;
		}
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < K; ++j) {
				for (int k = 0; k < K; ++k) {
					if (!g[j][k] && g[j][i] && g[i][k]) {
						g[j][k] = g[k][j] = true;
					}
				}
			}
		}
		int[] ans = new int[K];
		boolean[] used = new boolean[K];
		for (int i = 0; i < K; ++i) {
			if (used[i]) continue;
			ArrayList<Integer> pos = new ArrayList<Integer>();
			ArrayList<Integer> elem = new ArrayList<Integer>();
			for (int j = 0; j < K; ++j) {
				if (g[i][j]) {
					used[j] = true;
					pos.add(j);
					elem.add(P[j]);
				}
			}
			Collections.sort(elem);
			for (int j = 0; j < elem.size(); ++j) {
				ans[pos.get(j)] = elem.get(j);
			}
		}
		for (int i = 0; i < K - 1; ++i) {
			System.out.print(ans[i] + " ");
		}
		System.out.println(ans[K - 1]);
	}

}

Power Outage I


まず最小全域森を作って、長い辺から順に(K-連結成分の数)個取り除くと良い(ちゃんと証明してない)

入力で1回TLE


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {

	//	static Scanner sc = new Scanner(System.in);
	static Reader input = new BufferedReader(new InputStreamReader(System.in));
	static int N, K;
	static ArrayList<Edge> edges = new ArrayList<Edge>();

	public static void main(String[] args) throws Exception {
		int T = nextInt();
		for (int i = 0; i < T; ++i) {
			N = nextInt();
			edges.clear();
			int M = nextInt();
			K = nextInt();
			for (int j = 0; j < M; ++j) {
				int a = nextInt() - 1;
				int b = nextInt() - 1;
				int c = nextInt();
				edges.add(new Edge(a, b, c));
			}
			System.out.println(solve());
		}
	}

	static String solve() {
		if (K >= N) return "0";
		UnionFind uf = new UnionFind(N);
		Collections.sort(edges);
		int connect = 0;
		int sum = 0;
		for (int i = 0; i < edges.size(); ++i) {
			Edge e = edges.get(i);
			if (!uf.find(e.from, e.to)) {
				uf.union(e.from, e.to);
				sum += e.cost;
				connect++;
				if (connect == N - K) break;
			}
		}
		if (connect == N - K) {
			return sum + "";
		} else {
			return "Impossible!";
		}
	}

	static class UnionFind {
		int[] set;

		UnionFind(int n) {
			set = new int[n];
			Arrays.fill(set, -1);
		}

		void union(int a, int b) {
			int rtA = root(a);
			int rtb = root(b);
			if (rtA == rtb) {
				return;
			}
			set[rtA] += set[rtb];
			set[rtb] = rtA;
		}

		boolean find(int a, int b) {
			return root(a) == root(b);
		}

		int root(int a) {
			if (set[a] < 0) {
				return a;
			} else {
				set[a] = root(set[a]);
				return set[a];
			}
		}

		int size(int a) {
			return -set[root(a)];
		}
	}

	static class Edge implements Comparable<Edge> {
		int from, to, cost;

		Edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}

		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	static int nextInt() throws Exception {
		int sign = 1;
		int b = input.read();
		while ((b < '0' || '9' < b) && b != '-' && b != '+') {
			b = input.read();
		}
		if (b == '-') {
			sign = -1;
			b = input.read();
		} else if (b == '+') {
			b = input.read();
		}
		int ret = b - '0';
		while (true) {
			b = input.read();
			if (b < '0' || '9' < b) return ret * sign;
			ret *= 10;
			ret += b - '0';
		}
	}

}

Power Outage II


タイブレーク問題。

スコア関数がゆとり仕様だったので、最も総コストが下がる位置に発電機を置いていく、というてきとーなgreedyで出してみたら満点になった


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

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[][] dist;
	static int[] L, G;
	static final int INF = 1 << 29;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		int M = sc.nextInt();
		dist = new int[N][N];
		for (int[] a : dist) {
			Arrays.fill(a, INF);
		}
		for (int i = 0; i < N; ++i) {
			dist[i][i] = 0;
		}
		for (int i = 0; i < M; ++i) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			dist[a][b] = dist[b][a] = sc.nextInt();
		}
		L = new int[N];
		for (int i = 0; i < N; ++i) {
			L[i] = sc.nextInt();
		}
		G = new int[N];
		for (int i = 0; i < N; ++i) {
			G[i] = sc.nextInt();
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					if (dist[j][k] > dist[j][i] + dist[i][k]) {
						dist[j][k] = dist[k][j] = dist[j][i] + dist[i][k];
					}
				}
			}
		}
		solve();
	}

	static void solve() {
		long[] cost = new long[N];
		int[] to = new int[N];
		Arrays.fill(cost, 1L << 50);
		Arrays.fill(to, -1);
		for (int i = 0; i < N; ++i) {
			long minDiff = 0;
			int minI = -1;
			for (int j = 0; j < N; ++j) {
				if (to[j] == j) continue;
				long prev = 0;
				long next = G[j];
				for (int k = 0; k < N; ++k) {
					if (dist[j][k] == INF) continue;
					prev += cost[k];
					next += Math.min(cost[k], (long) L[k] * dist[j][k]);
				}
				long diff = next - prev;
				if (diff < minDiff) {
					minDiff = diff;
					minI = j;
				}
			}
			if (minDiff < 0) {
				for (int j = 0; j < N; ++j) {
					if (dist[j][minI] == INF) continue;
					long newCost = (long) L[j] * dist[j][minI];
					if (newCost < cost[j]) {
						cost[j] = newCost;
						to[j] = minI;
					}
				}
			}
		}

		ArrayList<Integer> post = new ArrayList<Integer>();
		for (int i = 0; i < N; ++i) {
			if (to[i] == i) {
				post.add(i);
			}
		}
		System.out.println(post.size());
		for (int i = 0; i < post.size(); ++i) {
			System.out.print((post.get(i) + 1) + " ");
		}
		System.out.println();
		for (int i = 0; i < N; ++i) {
			System.out.print((to[i] + 1) + " ");
		}
		System.out.println();
	}

}

nCr


142857=3^3*11*13*37なので、nCrをmod 27, mod 11, mod 13, mod 37でそれぞれ求めて中国剰余定理で合成すれば良い

素数を法としてnCrを求める方法は蟻本に載っているけど、mod 27がそのままでは無理でやっかい

英語版Wikipediaでウィルソンの定理のページを見ると、mod P だけではなくて mod P^N の場合への拡張が載っていたのでこれを使って求めた

http://en.wikipedia.org/wiki/Wilson%27s_theorem#Gauss.27s_generalization


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.math.BigInteger;

public class Solution {

	static Reader input = new BufferedReader(new InputStreamReader(System.in));
	static final int MOD = 142857;
	static int N, R;
	static final int[] ps = new int[] { 3, 11, 13, 37 };
	static final int[] bases = new int[] { 27, 11, 13, 37 };
	static final int[][] factTables = new int[ps.length][];

	public static void main(String[] args) throws Exception {
		for (int i = 0; i < bases.length; ++i) {
			factTables[i] = new int[bases[i]];
			int f = 1;
			for (int j = 0; j < bases[i]; ++j) {
				factTables[i][j] = f;
				if ((j + 1) % ps[i] != 0) {
					f *= j + 1;
				}
				f %= bases[i];
			}
		}
		StringBuilder sb = new StringBuilder();
		int T = nextInt();
		for (int i = 0; i < T; ++i) {
			N = nextInt();
			R = nextInt();
			if (R > N / 2) R = N - R;
			sb.append(solve() + "\n");
		}
		System.out.print(sb);
	}

	static int solve() {
		int[][] res = new int[4][];
		for (int i = 0; i < 4; ++i) {
			res[i] = modComb(N, R, bases[i], ps[i], factTables[i]);
		}
		int[] rem = new int[4];
		for (int i = 0; i < 4; ++i) {
			rem[i] = res[i][0];
		}
		return chineseRemainder(bases, rem);
	}

	// returns {remainder, power of p} 
	static int[] modFact(int n, int p, int base, int[] factTable) {
		if (n == 0) return new int[] { 1, 0 };
		int[] ret = modFact(n / base, p, base, factTable);
		ret[1] += n / base;
		if (n / p % 2 == 0) {
			ret[0] = ret[0] * factTable[n % p] % p;
		} else {
			ret[0] = ret[0] * (p - factTable[n % p]) % p;
		}
		return ret;
	}

	static int[] modComb(int n, int r, int p, int base, int[] factTable) {
		int[] a1 = modFact(n, p, base, factTable);
		int[] a2 = modFact(r, p, base, factTable);
		int[] a3 = modFact(n - r, p, base, factTable);
		int pow = a1[1] - a2[1] - a3[1];
		int rem;
		if (base == 3) {
			if (pow >= 3) {
				rem = 0;
			} else {
				rem = a1[0] * inv(a2[0] * a3[0] % p, p) % p;
				for (int i = 0; i < pow; ++i) {
					rem *= base;
				}
				rem %= p;
			}
		} else {
			if (pow > 0) {
				rem = 0;
			} else {
				rem = a1[0] * inv(a2[0] * a3[0] % p, p) % p;
			}
		}
		return new int[] { rem, pow };
	}

	static int solveNaive() {
		int[] count = new int[ps.length];
		for (int i = 0; i < ps.length; ++i) {
			count[i] = count(N, ps[i]) - count(N - R, ps[i]) - count(R, ps[i]);
		}
		if (count[0] >= 3 && count[1] >= 1 && count[2] >= 1 && count[3] >= 1) return 0;
		BigInteger v = BigInteger.ONE;
		for (int i = 0; i < R; ++i) {
			v = v.multiply(BigInteger.valueOf(N - i)).divide(BigInteger.valueOf(i + 1));
		}
		return v.remainder(BigInteger.valueOf(MOD)).intValue();
	}

	static int chineseRemainder(int[] mod, int[] rem) {
		int m1 = mod[0];
		int r1 = rem[0];
		for (int i = 1; i < mod.length; ++i) {
			int m2 = mod[i];
			int r2 = rem[i];
			r1 = chineseRemainder(m1, r1, m2, r2);
			m1 *= m2;
		}
		return r1;
	}

	static int chineseRemainder(int m1, int r1, int m2, int r2) {
		int A = ((r2 - r1) % m2 + m2) * inv(m1, m2) % m2;
		return (A * m1 + r1) % (m1 * m2);
	}

	static int calc(int prime, int mod) {
		long ret = 1;
		for (int i = 0; i < R; ++i) {
			int num = N - i;
			while (num % prime == 0) {
				num /= prime;
			}
			ret *= num;
			int den = i + 1;
			while (den % prime == 0) {
				den /= prime;
			}
			ret *= inv(den, mod);
			ret %= mod;
		}
		return (int) ret;
	}

	static int inv(int v, int mod) {
		return pow(v, totient(mod) - 1, mod);
	}

	static int totient(int v) {
		int ret = v;
		for (int i = 0; i < ps.length && v > 1; ++i) {
			if (v % ps[i] == 0) {
				v /= ps[i];
				while (v % ps[i] == 0) {
					v /= ps[i];
				}
				ret /= ps[i];
				ret *= (ps[i] - 1);
			}
		}
		return ret;
	}

	static int pow(int v, int p, int mod) {
		if (p == 0) return 1;
		int ret = pow(v, p / 2, mod);
		ret *= ret;
		ret %= mod;
		if (p % 2 == 1) {
			ret *= v;
			ret %= mod;
		}
		return ret;
	}

	static int count(int n, int d) {
		int ret = 0;
		while (n > 0) {
			ret += n / d;
			n /= d;
		}
		return ret;
	}

	static int nextInt() throws Exception {
		int sign = 1;
		int b = input.read();
		while ((b < '0' || '9' < b) && b != '-' && b != '+') {
			b = input.read();
		}
		if (b == '-') {
			sign = -1;
			b = input.read();
		} else if (b == '+') {
			b = input.read();
		}
		int ret = b - '0';
		while (true) {
			b = input.read();
			if (b < '0' || '9' < b) return ret * sign;
			ret *= 10;
			ret += b - '0';
		}
	}

}

Bowling


最後のフレームだけ別扱いしてDP

マルチケースなのでDPテーブルは前計算しておく

オーバーフローで2WA


import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int MOD = 1000000007;

	public static void main(String[] args) throws Exception {
		long[][][] dp = new long[101][4][3101]; // 2次元目は前のフレームからの影響 {0,0}, {0,1}, {0,2}, {1,2}
		dp[0][0][0] = 1;
		for (int i = 0; i < 100; ++i) {
			for (int j = 0; j <= i * 30; ++j) {
				// strike
				add(dp[i + 1][2], j + 10, dp[i][0][j]);
				add(dp[i + 1][2], j + 20, dp[i][1][j]);
				add(dp[i + 1][3], j + 20, dp[i][2][j]);
				add(dp[i + 1][3], j + 30, dp[i][3][j]);

				// spare
				for (int k = 0; k <= 9; ++k) {
					add(dp[i + 1][1], j + 10, dp[i][0][j]);
					add(dp[i + 1][1], j + 10 + k, dp[i][1][j]);
					add(dp[i + 1][1], j + 20, dp[i][2][j]);
					add(dp[i + 1][1], j + 20 + k, dp[i][3][j]);
				}

				// open
				for (int k = 0; k <= 9; ++k) {
					for (int l = 0; l + k < 10; ++l) {
						add(dp[i + 1][0], j + k + l, dp[i][0][j]);
						add(dp[i + 1][0], j + k + l + k, dp[i][1][j]);
						add(dp[i + 1][0], j + k + l + k + l, dp[i][2][j]);
						add(dp[i + 1][0], j + k + l + k + k + l, dp[i][3][j]);
					}
				}
			}
		}
		int[][] dp2 = new int[4][61];
		for (int i = 0; i <= 10; ++i) {
			int rest = i == 10 ? 10 : 10 - i;
			boolean extra = i == 10;
			for (int j = 0; j <= rest; ++j) {
				int rest2 = rest - j;
				if (rest2 == 0) {
					extra = true;
					rest2 = 10;
				}
				if (extra) {
					for (int k = 0; k <= rest2; ++k) {
						dp2[0][i + j + k]++;
						dp2[1][i + j + k + i]++;
						dp2[2][i + j + k + i + j]++;
						dp2[3][i + j + k + i + j + i]++;
					}
				} else {
					dp2[0][i + j]++;
					dp2[1][i + j + i]++;
					dp2[2][i + j + i + j]++;
					dp2[3][i + j + i + j + i]++;
				}
			}
		}
		int T = sc.nextInt();
		for (int i = 0; i < T; ++i) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			long ans = 0;
			for (int j = M; j >= Math.max(0, M - 60); --j) {
				for (int k = 0; k < dp[0].length; ++k) {
					ans += dp[N - 1][k][j] * dp2[k][M - j];
					ans %= MOD;
				}
			}
			System.out.println(ans);
		}
	}

	static void add(long[] a, int index, long amount) {
		a[index] += amount;
		if (a[index] >= MOD) a[index] -= MOD;
	}

}

Concatenated Palindrome


manacherのアルゴリズムとか使わないといかんのかなぁと思いつつ、とりあえずTLE解を出しておくか、と提出してみたら通った

新しい文字列を作りまくらない、という程度の効率化はしている


import java.util.Arrays;
import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int N, M;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		M = sc.nextInt();
		String[] strs = new String[N];
		SubStr[] forward = new SubStr[N];
		SubStr[] backward = new SubStr[N];
		for (int i = 0; i < N; ++i) {
			strs[i] = sc.next();
			forward[i] = new SubStr(strs[i], 0, true, M);
			forward[i].index = i;
			backward[i] = new SubStr(strs[i], M - 1, false, M);
			backward[i].index = i;
		}
		Arrays.sort(forward);
		Arrays.sort(backward);
		System.out.println(Math.max(solve(forward, backward), solve(backward, forward)));
	}

	static int solve(SubStr[] pre, SubStr[] suf) {
		int ans = 0;
		for (int i = 0; i < N; ++i) {
			int pos = Arrays.binarySearch(pre, suf[i]);
			int lo, hi;
			if (pos < 0) {
				lo = -pos - 2;
				hi = -pos - 1;
			} else {
				lo = hi = pos;
			}
			if (lo >= 0 && pre[lo].index == suf[i].index) {
				--lo;
			}
			if (hi < N && pre[hi].index == suf[i].index) {
				++hi;
			}
			if (lo < 0) lo = 0;
			if (hi >= N) hi = N - 1;
			for (int j = lo; j <= hi; ++j) {
				if (pre[j].index == suf[i].index) continue;
				ans = Math.max(ans, count(suf[i], pre[j]));
			}
		}
		return ans;
	}

	static int count(SubStr s1, SubStr s2) {
		int pos = countMatch(s1, s2);
		SubStr[] sa = new SubStr[M - pos];
		for (int i = pos; i < M; ++i) {
			sa[i - pos] = new SubStr(s1.str, s1.start + i * s1.diff, s1.diff == -1, i - pos + 1);
		}
		SubStr rest = new SubStr(s1.str, s1.start + pos * s1.diff, s1.diff == 1, M - pos);
		for (int i = sa.length - 1; i >= 0; --i) {
			if (countMatch(rest, sa[i]) == sa[i].len) {
				return pos * 2 + sa[i].len;
			}
		}
		return pos * 2;
	}

	static int countMatch(SubStr s1, SubStr s2) {
		int i = 0;
		for (; i < Math.min(s1.len, s2.len); ++i) {
			if (s1.str.charAt(s1.start + i * s1.diff) != s2.str.charAt(s2.start + i * s2.diff)) return i;
		}
		return i;
	}

	static class SubStr implements Comparable<SubStr> {
		String str;
		int start;
		int diff;
		int len;
		int index;

		SubStr(String s, int start, boolean forward, int len) {
			this.str = s;
			this.start = start;
			this.diff = forward ? 1 : -1;
			this.len = len;
		}

		public int compareTo(SubStr o) {
			int p1 = this.start;
			int p2 = o.start;
			for (int i = 0; i < Math.min(this.len, o.len); ++i) {
				if (this.str.charAt(p1) < o.str.charAt(p2)) {
					return -1;
				}
				if (this.str.charAt(p1) > o.str.charAt(p2)) {
					return 1;
				}
				p1 += this.diff;
				p2 += o.diff;
			}
			if (this.len < o.len) return -1;
			if (this.len > o.len) return 1;
			return 0;
		}
	}

}

Random number generator


まずA<Bに正規化する。

C<A<BとA<C<BとA<B<C<A+BとA+B<Cで場合分けして紙上で計算


import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int N = sc.nextInt();
		for (int i = 0; i < N; ++i) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int C = sc.nextInt();
			solve(Math.min(A, B), Math.max(A, B), C);
		}
	}

	static void solve(long A, long B, long C) {
		if (A + B <= C) {
			System.out.println("1/1");
			return;
		}
		long num, den;
		if (C < A) {
			num = C * C;
			den = 2 * A * B;
		} else if (C < B) {
			num = 2 * C - A;
			den = 2 * B;
		} else {
			num = 2 * C * (B + A) - A * A - B * B - C * C;
			den = 2 * A * B;
		}
		long gcd = gcd(num, den);
		System.out.println(num / gcd + "/" + den / gcd);
	}

	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

}

2012-06-04

[]IPSC2012 23:33 はてなブックマーク - IPSC2012 - TopCoderの学習のお時間

http://ipsc.ksp.sk/contests/ipsc2012/results/

uwiさんとkomiyaさんとのチームyaranaidakeで参加


経過


  • 開始。おもい
  • ひとまず自分が最初に問題文を開けたので最初から読む。Aはやるだけだったのでやる
    • A1,A2 AC
  • 次にBを読もう…と思ったら問題文も入力もなくて「何このエスパーゲー…?」と早速IPSCの洗礼を受ける
  • とりあえず空ファイル提出だけやって次へ
  • Cを読むとeasyは簡単なDPだったのでやる
  • そうこうしてたらF1がuwiさんによって解かれていた
  • Jが、mp3を与えられてなんかやる問題らしい。uwiさんが絶対音感を発揮して一瞬で通した(ファーストアクセプト)。ぱない
    • J1,J2 AC
  • Dを読んでみたら超めんどい業務系データ処理ゲーだったので逃げてIを見てみる
  • ハッシュ値から元の文字列を復元する問題みたいだけどそれ以上の見当が付かない
  • エスパーゲーのBが結構解かれていたのでやってみる
  • komiyaさんがMに取り組んでいて、行列式がどうこうという話をuwiさんとしている。ついて行けないので黙々Bを試行錯誤する
  • とりあえず提出してみてエラーメッセージから条件を読み取る、というタイプの問題だった。ICFPC2010みたいな
  • 初見のインパクトがいやらしいだけで、やってみればそんな難しくなかった
    • B1,B2 AC
  • 個人的にはeasyよりhardのほうが簡単だった
  • komiyaさんがM1を手作業で解いて通していた。これもまたIPSCの醍醐味
  • F2がまだ通ってなかったのでやる。嘘解法気味だったけど出すとあっさり通った
  • 次に問題文3ページもあってまだ誰もやってなかったKへ
  • 読んでるうちに他のメンバーによってE1とG1が通される
  • K最初わけがわからなかったけど、落ち着いて考えてみたら侵入先の部屋の鍵のことはガン無視してマスターキーを作ればいいだけだった。国語ゲーだ
    • K1,K2 AC
  • Kを通したと同時に、16分間計算し続けていたuwiさんのマシンがG2の答えを出したらしい
  • 国内最強のRabbit Unagiチームを一時追い抜いて盛り上がる
  • Iを考えたけどbrute-forceくらいしかやることが思いつかない…。最近ksnctfやってたのに
  • そうこうしてたらuwiさんがD1を通す
  • あとはkomiyaさんと一緒にC2を考えたりIでエンディアン変えてbrute-forceしてみたりしたけどだめだった
  • ラスト100分で1点しか取れなかった…残念

結果


  • 22点/39点中
  • 37位/650チームくらい

感想


Iが解けなかったのがかなり痛い…。あとLに誰も手を付けなかったのはちょっともったいなかったかも。

赤コーダー×3でも37位とは世界は広いなあ。


Iは、みんなWeb上のツールでハッシュ値をクラックしようとしてたので、コンテスト終盤にはハッシュ値をググったら答えが出てくる状態になってたらしいw

やっぱりCTF系では「わからなかったらググれ」は基本だ


チームを組んでコンテスト参加するのは初めてでした。

協力しながら作業表を埋めていくのが面白かった。

しかし3人いても全部の問題に取り組むというのは相当うまくマネジメントしないと難しいですね…