Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-02SRM353, SRM354 (Practice)

SRM 354 DateFormat

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

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

  • 日付を4桁の数にエンコーディング
  • DPと経路復元(めんどい)をするだけ。
    • 状態は [今考えてる日付の位置][直前の日付]
      • 状態数は 2500 * 1300 ≒ 50^4 / 2 としてまぁ大丈夫でしょう。
      • そもそも使わない日付もあるんだし。(1050とか)
  • 月ごとの最大日付のインデックス指定をミスってハマる
import java.util.ArrayList;
import java.util.List;

public class DateFormat {
	int[] a, r;
	int[][] next;
	int[] daymonth = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

	public int dfs(int i, int prev) {
		if (i == a.length) {
			return 1;
		}
		if (next[i][prev] != 0) {
			if (next[i][prev] >= 1) {
				return 1;
			} else {
				return -1;
			}
		}
		
		int first = Math.min(a[i], r[i]);
		int second = Math.max(a[i], r[i]);
		boolean fv = isvalid(first) && (first > prev);
		boolean sv = isvalid(second)&& (second > prev);
		if (fv) {
			if (dfs(i+1, first) == 1) {
				next[i][prev] = first;
				return 1;
			}
		}
		if (sv) {
			if (dfs(i+1, second) == 1) {
				next[i][prev] = second;
				return 1;
			}
		}
		
		next[i][prev] = -1;
		return -1;
	}
	
	public boolean isvalid(int dat) {
		int month = dat / 100;
		if (month <= 0 || month >= 13) {
			return false;
		}
		int day = dat % 100;
		
		if (1 <= day && day <= daymonth[month]) {
			return true;
		}
		return false;
	}
	
	public String fromEuropeanToUs(String[] dateList) {
		String d = "";
		for (String x : dateList) {
			d += x;
		}
		String[] dates = d.split(" ");
		
		int len = dates.length;
		a = new int[len];
		r = new int[len];
		for (int i = 0 ; i < len ; i++) {
			String[] date = dates[i].split("/");
			a[i] = Integer.valueOf(date[0]) * 100 + Integer.valueOf(date[1]);
			r[i] = Integer.valueOf(date[1]) * 100 + Integer.valueOf(date[0]);
		}
		next = new int[len+1][1300];
		
		if (dfs(0, 0) == -1) {
			return "";
		}
		
		List<String> list = new ArrayList<String>();
		int nowi = 0;
		int nowprev = 0;
		while (nowi < len) {
			int nextdata = next[nowi][nowprev];
			int nmonth = nextdata / 100;
			int nday = nextdata % 100;
			String month = (nmonth <= 9) ? ("0" + nmonth) : ("" + nmonth);
			String day = (nday <= 9) ? ("0" + nday) : ("" + nday);
			list.add(month + "/" + day);
			nowi++;
			nowprev = nextdata;
		}
		
		String ans = "";
		for (String l : list) {
			ans += " " + l;
		}
		return ans.substring(1);
	}
}