Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-06-19TCO10 Algo Round1

ラウンド1敗退。

結果

問題結果ポイントその他
第一問(250pt)Passed System Test202.08アルファベットが全何文字かド忘れした
第二問(500pt)Failed System Test0.00無駄に防衛4回成功してた
第三問(1000pt)Unopened0.00見てない

Rating: -36(1298 > 1262)

TCO Round1 第一問(250点)

| TCO Round1 第一問(250点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - TCO Round1 第一問(250点) - hama_DU@TopCoderへの道

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

  • 一文字ずつの比較でOK。
  • 文字同士が13以上離れていたらaにする
  • それ以外なら小さい方にする
public class EqualizeStrings {
  public String getEq(String s, String t) {
    if (s.equals(t)) {
      return s;
    }
    int size = s.length();
    String str = "";
    for (int i = 0 ; i < size ; i++)
    {
      int dist = Math.abs(s.charAt(i) - t.charAt(i));
      if (dist < 13) {
        if (s.charAt(i) < t.charAt(i)) {
          str += String.valueOf(s.charAt(i));
        } else {
          str += String.valueOf(t.charAt(i));
        }
      } else {
        str += "a";
      }
    }
    return str;
  }
}

TCO Round1 第二問(500点)

| TCO Round1 第二問(500点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - TCO Round1 第二問(500点) - hama_DU@TopCoderへの道

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

  • X>Y>X>Yってやってったら最強だよなぁ
    • rを超えた時点で途中からやりなおすのは?→実装方法が思いつかない。
  • これって部分問題にできないだろうか?
    • r = X += Y としたいから、r をXとYに分割する。
    • でその XとYの組は、X += Y(旧)、Y += X(旧) の二通りで作れる。
    • 延々と逆探索してけばどっちかが 0以下になるっしょ! → この時点で残り時間15分。

コーナーケースっぽいのを書いて土壇場提出!残り30秒!間に合ったー!

以下は提出時点でのコード。class Stateってなんぞw


public class TwoRegisters {
 
  public String[][] memo;
 
  String min_f = "Z";
 
  public String dp(int depth, int x, int y) {
    if (!min_f.equals("Z") && depth > min_f.length()) {
      return null;
    }
    if (x <= 0 || y <= 0 || depth > 1000) return null;
    if (x == 1 && y == 1) {
      return "";
    }
 
    String str1 = dp(depth + 1, x, y - x);
    String str2 = dp(depth + 1, x - y, y);
 
    String ret;
    if (str1 == null){
      if (str2 == null) {
        ret = null;
      } else {
        ret = str2 + "X";
      }
    } else {
      if (str2 == null) {
        ret = str1 + "Y";
      } else {
        if (str1.compareTo(str2) > 0) {
          ret = str1 + "Y";
        } else {
          ret = str2 + "X";
        }
      }
    }
    if (ret != null) {
      // memo[x][y] = ret;
    }
    return ret;
  }
 
  public String minProg(int r) {
    if (r == 1) return "";
    if (r == 2) return "X";
    if (r == 3) return "XX";
 
    int ct = r / 2;
    for (int i = 1 ; i < ct ; i++) {
      int a = ct - i;
      int b = r - a;
      String f = dp(0, a, b);
      if (f != null) {
        if (f.length() < min_f.length() || min_f.equals("Z")) {
          min_f = f;
        } else if (f.length() == min_f.length() && f.compareTo(min_f) < 0) {
          min_f = f;
        }
      }
    }
    for (int i = 1 ; i < ct ; i++) {
      int a = r - ct + i;
      int b = r - a;
      String f = dp(0, a, b);
      if (f != null) {
        if (f.length() < min_f.length() || min_f.equals("Z")) {
          min_f = f;
        } else if (f.length() == min_f.length() && f.compareTo(min_f) < 0) {
          min_f = f;
        }
      }
    }
    return min_f + "X";
  }
  public class State {
    int depth;
    String inst;
 
  }
}

r = 9 で落ちた。また、r = 5でも正しくない結果が出ることが確認できた。

なぜなら、a = 4、b = 5のパターンが検証できないため。

ループ条件を見直し、コードを整理してSystestに通ったのがこちら。

public class TwoRegisters {
	String min_f = "Z";

	public String dp(int depth, int x, int y) {
		if (!min_f.equals("Z") && depth > min_f.length()) {
			return null;
		}
		if (x <= 0 || y <= 0 || depth > 100) return null;
		if (x == 1 && y == 1) {
			return "";
		}

		String str1 = dp(depth + 1, x, y - x);
		String str2 = dp(depth + 1, x - y, y);

		if (str1 == null && str2 == null) {
			return null;
		}
		if (str1 == null) {
			return str2 + "X";
		}
		if (str2 == null) {
			return str1 + "Y";
		}
		if (str1.compareTo(str2) > 0) {
			return str1 + "Y";
		} else {
			return str2 + "X";
		}
	}

	public String minProg(int r) {
		if (r == 1) return "";
		if (r == 2) return "X";
		if (r == 3) return "XX";

		int ct = r / 2;
		for (int i = 0 ; i <= ct ; i++) {
			int a = ct - i;
			int b = r - a;
			String f = dp(0, a, b);
			if (f != null) {
				if (f.length() < min_f.length() || min_f.equals("Z")) {
					min_f = f;
				} else if (f.length() == min_f.length() && f.compareTo(min_f) < 0) {
					min_f = f;
				}
			}
			int temp = a;
			a = b;
			b = temp;
			f = dp(0, a, b);
			if (f != null) {
				if (f.length() < min_f.length() || min_f.equals("Z")) {
					min_f = f;
				} else if (f.length() == min_f.length() && f.compareTo(min_f) < 0) {
					min_f = f;
				}
			}
		}
		return min_f + "X";
	}
}