Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-20SRM345 (Practice)

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