Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-20SRM345 (Practice)

マラソンマッチが終わったので練習再開。

問題結果ポイントその他
250PathfindingAccepted134.08場合分け
500StoneGameAccepted398.14数学
1000ByteLandOpened0.00グラフ

SRM 345 Pathfinding

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

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

  • 探索で解こうと思った
    • 無理だった
  • 結局場合分けした。
    • xとyは対称性を持つので片方が負の場合だけを考えれば良い
  • 解法の検討に色々迷走したので時間がかかってしまった。
public class Pathfinding {
	public int getDirections(int x, int y) {
		int dx = Math.abs(x);
		int dy = Math.abs(y);
		
		if (x >= 0 && y >= 0) {
			if (dx % 2 == 1 && dy % 2 == 1) {
				return dx + dy + 2;
			}
			return dx + dy;
		} else if (x <= 0 && y <= 0) {
			if (dx % 2 == 0 && dy % 2 == 0) {
				return dx + dy + 4;
			}
			return dx + dy + 2;
		}
		
		if (x > 0) {
			int t = x;
			x = y;
			y = t;
		}
		
		dx = Math.abs(x);
		dy = Math.abs(y);
		if (dx % 2 == 1 && dy % 2 == 0) {
			return dx + dy + 2;
		}
		return dx + dy;
	}
}

SRM 345 StoneGame

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

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

  • 手で実験してみる
    • これ、総取りできるか、全部相手に取られるかのどちらかなのでは
      • 石の総数の偶奇で決まる気がする(奇数なら総取りできる)
  • でも、石の数が1の場合はまずそちらを取った方がいい
    • 複数ある場合は当然価値が高いものを取った方がいい
    • 相手も当然価値が高いものを優先して取るはず
  • 石の数が1の山をすべて取り終えたときゲームが始まる
  • 書いたらサンプル合った。
    • 証明はできないが正しい気がするのでそのまま出した
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class StoneGame {

	public int getScore(int[] treasure, int[] stones) {
		int len = stones.length;
		List<Integer> cango = new ArrayList<Integer>();
		
		int etotal = 0;
		int etreas = 0;
		for (int i = 0 ; i < len ; i++) {
			if (stones[i] == 1) {
				cango.add(treasure[i]);
			} else {
				etotal += stones[i];
				etreas += treasure[i];
			}
		}
		Collections.sort(cango);
		Collections.reverse(cango);
		
		int canget = 0;
		int cl = cango.size();
		for (int i = 0 ; i < cl ; i += 2) {
			canget += cango.get(i);
		}
		if (cl == len) {
			return canget;
		}
		
		if (cl % 2 == 1) {
			etotal -= 1;
		}
		if (etotal % 2 == 1) {
			canget += etreas;
		}
		return canget;
	}
}

SRM 345 ByteLand

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

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

  • 貪欲で行ける気がするが、証明ができない
    • 距離を決めうちしてDPする系なのかな?
  • 後で解く