Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-24SRM364 (Practice)

easyに時間かかったけどmediumがそこそこ速く出せた。2完早解きゲー

問題結果ポイントその他
300PaintballAccepted182.53実装ゲー
500PowerPlantsAccepted405.86ダイクストラ
1000YankeeSwapOpened0.00ゲーム?

SRM 364 Paintball

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

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

  • やるだけっぽい
    • バグらないようにオブジェクト指向っぽく実装
  • サンプル合わない。
    • 仲間を倒した場合得点マイナスになるのか
    • 直した
  • サンプル通った。出した。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Paintball {

	public class Team implements Comparable<Team> {
		String name;
		List<Player> players;
		int score = 0;
		Team(String n){
			name = n;
			players = new ArrayList<Player>();
		}
		public List<String> teamString(){
			List<String> ret = new ArrayList<String>();
			ret.add(name + " " + score);
			for (Player p : players) {
				ret.add("  " + p.name + " " + p.score);
			}
			return ret;
		}
		public int compareTo(Team o) {
			if (score == o.score) {
				return name.compareTo(o.name);
			}
			return o.score - score;
		}
		public void doSort() {
			Collections.sort(players);
		}
	}
	
	public class Player implements Comparable<Player> {
		Team team;
		String name;
		int score;
		Player(String n, Team t) {
			score = 0;
			name = n;
			team = t;
			t.players.add(this);
		}
		void splattered(Player another) {
			if (team.name.equals(another.team.name)) {
				score -= 1;
				team.score -= 1;
			} else {
				score += 1;
				another.score -= 1;
				team.score += 1;
				another.team.score -= 1;
			}
		}
		public int compareTo(Player arg0) {
			if (score == arg0.score) {
				return name.compareTo(arg0.name);
			}
			return arg0.score - score;
		}
	}
	
	
	public String[] getLeaderboard(String[] players, String[] messages) {
		Map<String, Team> tmap = new HashMap<String, Team>();
		List<Team> teams = new ArrayList<Team>();
		Map<String, Player> pmap = new HashMap<String, Player>();
		for (String p : players) {
			String[] data = p.split(" ");
			if (!tmap.containsKey(data[1])) {
				tmap.put(data[1], new Team(data[1]));
				teams.add(tmap.get(data[1]));
			}
			Player pl = new Player(data[0], tmap.get(data[1]));
			pmap.put(pl.name, pl);
		}
		
		
		for (String mes : messages) {
			String[] data = mes.split(" ");
			Player a = pmap.get(data[0]);
			Player b = pmap.get(data[2]);
			a.splattered(b);
		}
		
		
		Collections.sort(teams);
		List<String> standings = new ArrayList<String>();
		for (Team t : teams) {
			t.doSort();
			standings.addAll(t.teamString());
		}
		String[] ret = new String[standings.size()];
		for (int i = 0 ; i < standings.size() ; i++) {
			ret[i] = standings.get(i);
		}
		return ret;
	}
}

SRM 364 PowerPlants

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

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

  • 2^16の状態を持ちながらダイクストラするだけ。
  • numPlants以上のplantsが生きてればいい(丁度でなくてもいい)ので注意
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PowerPlants {

	int INF = 10000000;
	
	class State {
		int stat;
		int cost;
		State(int s, int c) {
			stat = s;
			cost = c;
		}
	}
	
	public int minCost(String[] connectionCost, String plantList, int numPlants) {
		int len = connectionCost.length;
		int[][] graph = new int[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				char c = connectionCost[i].charAt(j);
				if ('0' <= c && c <= '9') {
					graph[i][j] = c - '0';
				} else {
					graph[i][j] = 10 + c - 'A';
				}
			}
 		}
		
		int[] dp = new int[1<<len];
		Arrays.fill(dp, INF);
		
		
		int initptn = 0;
		for (int i = 0 ; i < len ; i++) {
			if (plantList.charAt(i) == 'Y') {
				initptn |= (1<<i);
			}
		}
		dp[initptn] = 0;
		
		Queue<State> q = new PriorityQueue<State>(4000000, new Comparator<State>(){
			public int compare(State arg0, State arg1) {
				return arg0.cost - arg1.cost;
			}
		});
		q.add(new State(initptn, 0));
		
		while (q.size() >= 1) {
			State s = q.poll();
			for (int i = 0 ; i < len ; i++) {
				if ((s.stat & (1<<i)) == 0) {
					int mcost = 10000;
					int mwake = -1;
					for (int j = 0 ; j < len ; j++) {
						if ((s.stat & (1<<j)) >= 1) {
							if (mcost > graph[j][i]) {
								mcost = graph[j][i];
								mwake = j;
							}
						}
					}
					if (mwake >= 0) {
						int tc = mcost + s.cost;
						int ts = s.stat | (1<<i);
						if (dp[ts] > tc) {
							dp[ts] = tc;
							q.add(new State(ts, tc));
						}
					}
				}
			}
		}
		
		int mcost = INF;
		for (int i = 0 ; i < (1<<len) ; i++) {
			if (Integer.bitCount(i) >= numPlants) {
				mcost = Math.min(mcost, dp[i]);
			}
		}
		return mcost;
	}
}

SRM 364 YankeeSwap

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

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

  • シミュレーションするだけ?
    • そんなことはなかった
    • 自分が良いものを手に入れるためには悪いものと交換されてはならない。
      • 誰と交換すべきかは先読みする必要がある
  • 待てよ。よく考えると一番最後の人は必ずベストなものが手に入るはず。
    • 逆から考えていけばいいのかな?
    • いや、それだけじゃ誰と交換すべきかはわからない
      • 最後の人にとって一番いいものを誰が持ってるか分からないので
  • 制約が N <= 20 なのが気になる・・・
    • N! は無理だけど 2^20 なら大丈夫?
    • 各人が欲しい物を手に入れたかどうかで探索?