Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-13SRM375 (Practice)

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;
	}
}