Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-20SRM395 (Practice)

SRM 395 StreetWalking

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

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

コーディングフェーズ

  • 縦横ナナメに進める。
  • 方針検討
    • 以下の2パターン検証する
      • 斜めにmin(X, Y)進み、その後で直進する
      • 全部直進する
  • サンプル合わない。
    • んー?
    • 斜めにmin(X, Y)進んだ後でも、斜めに進んだほうが得なケースがある
    • 上記3パターンの最小値を返すよう実装。
      • コーディングに手間取る・・・
  • サンプル通った
    • 自分ルールであと5分は提出しない。
    • プログラムを見直す。
      • コーディングのミスを発見。気付いてよかった・・・
  • 出した

public class StreetWalking {

	public long req(long X, long Y, long w, long s) {
		X = Math.abs(X);
		Y = Math.abs(Y);
		long ans = 0;
		long total = 0L + X + Y;
		long mintimeA = total * w;
		
		long maxs = Math.min(X, Y);
		long lefts = Math.max(X, Y) - Math.min(X, Y);

		long mintimeB = lefts * w + maxs * s;
		ans = Math.min(mintimeA, mintimeB);
		
		if (lefts >= 1) {
			long first = Math.min(X, Y) * s;
			if (lefts % 2 == 0) {
				ans = Math.min(ans, first + lefts * s);
			} else {
				ans = Math.min(ans, first + (lefts - 1) * s + w);
			}
		}
		return ans;
	}
	
	
	public long minTime(int X, int Y, int w, int s) {
		long mintime = req(X, Y, w, s);
		{
			int[] dx = {1, 0, -1, 0};
			int[] dy = {0, -1, 0, 1};
			for (int d = 0 ; d < 4 ; d++) {
				mintime = Math.min(mintime, req(X+dx[d], Y+dy[d], w, s) + w);
			}
		}
		
		{
			int[] dx = {1, 1, -1, -1};
			int[] dy = {1, -1, 1, -1};
			for (int d = 0 ; d < 4 ; d++) {
				mintime = Math.min(mintime, req(X+dx[d], Y+dy[d], w, s) + s);
			}
		}
		
		return mintime;
	}

}