Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-13SRM375 (Practice)

mediumが残念な回。easyとhardの問題は割りと好き 49/420位

問題結果ポイントその他
250DivisibleByDigitsAccepted212.39数論
500DateFieldCorrectionAccepted309.38グラフを作る実装ゲー
1000DukeOnLargeChessBoardOpened0.00場合分け?

SRM 375 DivisibleByDigits

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

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

  • 数論ゲーきたこれ
    • 割るべき数は1〜9のどれかだから、まず出現する数字のLCMを求めてしまおう
  • 方針を考える
    • 初期状態で割り切れればそれで終了
    • そうでなければ、数字を1つずつ追加していくとして・・・
      • 10^a倍すると、残り必要な数も自動的に分かるから、それが0〜(10^a-1)に収まってるかで判定すればよさそう
  • 書けた。サンプル通った。
    • 小さめの数で変なことが起こらないか確認する。
    • 大丈夫。
  • 出した
public class DivisibleByDigits {
	public long lcm(long a, long b) {
		long g = gcd(a, b);
		return a * b / g;
	}
	
	public long gcd(long a, long b) {
		return (b != 0) ? gcd(b, a%b) : a;
	}
	
	public long getContinuation(int n) {
		String l = String.valueOf(n);
		int len = l.length();
		long d = 1;
		for (int i = 0 ; i < len ; i++) {
			int z = l.charAt(i) - '0';
			if (z >= 1) {
				d = lcm(d, z);
			}
		}
		System.out.println(d);
		if (n % d == 0) {
			return n;
		}
		long ln = n;
		for (int ad = 1 ; ad <= 15 ; ad++) {
			long df = (ln * (long)Math.pow(10, ad)) % d;
			long maxadd = (long)Math.pow(10, ad) - 1;
			if (df == 0) {
				return (ln * (long)Math.pow(10, ad));
			} else if ((d - df) <= maxadd) {
				return (ln * (long)Math.pow(10, ad)) + (d - df);
			}
		}	
		return 0;
	}
}

SRM 375 DateFieldCorrection

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

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

  • 要するに、キー配列の編集距離グラフをあげるから候補の中で編集距離が最も短いのを返してねということらしい
    • 実装ゲーすぎる・・・
  • グラフをしこしこ作る。
    • "1234567890", "qwertyuiop" ... みたいな文字列変数を用意してforで回してグラフを作る
    • 各文字同士の編集距離はワーシャルフロイド法で予め求めておく
  • 後は366候補に対して全探索。
  • サンプル通った。
    • コーナーケースチェックする気も起きない。
  • 出した。酷い問題だった
import java.util.Arrays;

public class DateFieldCorrection {

	int INF = 1000000;
	
	public void pdist(int[][] g, char a, char b) {
		int aa = encode(a);
		int bb = encode(b);
		System.out.println(g[aa][bb]);
	}
	
	public int encode(char c) {
		if ('0' <= c && c <= '9') {
			return c - '0';
		}
		if ('a' <= c && c <= 'z') {
			return 10 + (c - 'a');
		}
		if ('A' <= c && c <= 'Z') {
			return 10 + (c - 'A');
		}
		return 37;
	}
	
	
	
	public int[][] buildgraph() {
		String u1 = "1234567890";
		String u2 = "qwertyuiop";
		String u3 = "asdfghjkl";
		String u4 = "zxcvbnm";
		
		
		int[][] distance = new int[40][40];
		for (int i = 0 ; i < 40 ; i++) {
			Arrays.fill(distance[i], INF);
		}
		
		for (int i = 0 ; i < u1.length()-1 ; i++) {
			int a = encode(u1.charAt(i));
			int b = encode(u1.charAt(i+1));
			int c = encode(u2.charAt(i));
			distance[a][b] = 1;
			distance[b][a] = 1;
			distance[a][c] = 1;
			distance[c][a] = 1;
			distance[c][b] = 1;
			distance[b][c] = 1;
		}
		distance[encode('p')][encode('0')] = 1;
		distance[encode('0')][encode('p')] = 1;
		
		
		for (int i = 0 ; i < u2.length()-1 ; i++) {
			int a = encode(u2.charAt(i));
			int b = encode(u2.charAt(i+1));
			int c = encode(u3.charAt(i));
			distance[a][b] = 1;
			distance[b][a] = 1;
			distance[a][c] = 1;
			distance[c][a] = 1;
			distance[c][b] = 1;
			distance[b][c] = 1;

		}
		
		for (int i = 0 ; i < u3.length()-1 ; i++) {
			int a = encode(u3.charAt(i));
			int b = encode(u3.charAt(i+1));
			distance[a][b] = 1;
			distance[b][a] = 1;
			if (i <= 6) {
				int c = encode(u4.charAt(i));
				distance[a][c] = 1;
				distance[c][a] = 1;
				distance[c][b] = 1;
				distance[b][c] = 1;
			}
		}
		
		for (int i = 0 ; i < u4.length()-1 ; i++) {
			int a = encode(u4.charAt(i));
			int b = encode(u4.charAt(i+1));
			distance[a][b] = 1;
			distance[b][a] = 1;
		}
		for (int i = 1 ; i < u4.length() ; i++) {
			int a = encode(u4.charAt(i));
			int b = encode(' ');
			distance[a][b] = 3;
			distance[b][a] = 3;			
		}
		for (int i = 0 ; i < 40 ; i++) {
			distance[i][i] = 0;
		}
		return distance;
	}
	
	
	public String correctDate(String input) {
		int[][] graph = buildgraph();
		for (int k = 0 ; k < 40 ; k++) {
			for (int i = 0 ; i < 40 ; i++) {
				for (int j = 0 ; j < 40 ; j++) {
					if (graph[i][k] != INF && graph[k][j] != INF) {
						graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
					}
				}
			}
		}
		
		String[] mstr = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
		int[] days = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
		
		int mindist = INF;
		int minday = -1;
		String res = "";
		int len = input.length();
		for (int i = 0 ; i < 12 ; i++) {
			for (int d = 1 ; d <= days[i] ; d++) {
				String mst = mstr[i] + " " + String.valueOf(d);
				if (mst.length() == len) {
					int diff = 0;
					for (int j = 0 ; j < len ; j++) {
						int a = encode(input.charAt(j));
						int b = encode(mst.charAt(j));
						diff += graph[a][b];
					}
					if (mindist > diff) {
						mindist = diff;
						minday = i * 100 + d;
						res = mst;
					} else if (mindist == diff) {
						if (i * 100 + d < minday) {
							minday = i * 100 + d;
							res = mst;
						}
					}
				}
			}
		}
		return res;
	}
}

SRM 375 DukeOnLargeChessBoard

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

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

  • 余力があるのでhardに挑戦
  • 右 > 上 > 下 > 左 の優先順位でまだ行ってないマスに移動していく時、詰んだ時の位置を返しなさいという問題か
    • 問題名の通りフィールドがでかいのでシミュレーションは無理そう。
  • 4x4マスぐらいのフィールドを紙に書いて、手で実験してみる。
    • 規則っぽいのが見えないが、細かく場合分けしていけばいい気がする。
  • 場合分けコードを書く。
    • 端っこにいる場合は簡単だけど、真ん中にいる場合が難しい・・・
    • 偶奇で最終位置が変わる気がする
  • 分からん・・・
  • 時間切れ