Hatena::Grouptopcoder

qnighy[黄色]

 | 

2011-02-09

SRM495Div1

| 22:18 | はてなブックマーク - SRM495Div1 - qnighy[黄色]

275 ColorfulCards

Div2で練習したので省略

// Passed System Test
using System;
using System.Collections.Generic;

public class ColorfulCards {
	public int[] theCards(int N, string colors) {
		char[] c = new char[N+1];
		for(int i = 0; i <= N; i++) c[i] = i<2 ? 'B' : 'R';
		for(int i = 2; i <= N; i++)
			if(c[i] == 'R')
				for(int j = i*i; j <= N; j+=i)
					c[j] = 'B';
		int[] ret = new int[colors.Length];
		int n = 1;
		for(int i = 0; i < colors.Length; i++) {
			while(c[n] != colors[i]) n++;
			ret[i] = n++;
		}
		n = N;
		for(int i = colors.Length-1; i >= 0; i--) {
			while(c[n] != colors[i]) n--;
			if(ret[i] != n--) ret[i] = -1;
		}
		return ret;
	}
}

500 CarrotBoxes

N個の箱があり、ハズレが1つ当確率で存在することがわかっている。箱の中には他の箱がハズレかどうかの情報が入っている場合があり、どの箱にどの箱の情報が入っているかはわかっている。最適な戦略で箱を開けていったときに、ハズレを引き当てる前にハズレの箱を特定できる確率を答えよ。

確率難しい…

今ここにn個(n>1)の箱が未開封で残っていたとする。ある箱を開けることにすると、以下の3通りが考えうる。

  • 今開けた箱がハズレ。(確率1/n)→失敗で終了
  • 今開けた箱は当たりで、その箱から得られる情報を辿ることによりハズレが特定できた。(確率n-a-1/n)→成功で終了
  • 今開けた箱は当たりで、その箱から得られる情報を辿ることにより、残りa個の中にハズレがあることがわかった。(確率a/n)→未開封a個で継続

また、箱が1個残った場合は終了である。

仮に箱が1個残った場合にも継続しないといけないとすると、帰納的に考えて、m個を開封することにより全貌が把握できると、確率m/nで成功することがわかる。これは強連結成分分解(Warshall-Floydでできる)して入向辺を持たない頂点を数え上げればよい。

さて、ここで箱が1箱残った場合は終了できるので、全ての箱についてそれを除きつつ上記の操作を試し、最小値をとればよい。

// Passed System Test
import java.util.*;

public class CarrotBoxes {
	public double theProbability(final String[] information) {
		final int N = information.length;
		int mincnt = N;
		for(int out = 0; out < N; out++) {
		
			boolean[][] wf = new boolean[N][N];
			for(int i = 0; i < N; i++)
				for(int j = 0; j < N; j++)
					if(i!=out && j!=out && information[i].charAt(j)=='Y') wf[i][j] = true;
			for(int k = 0; k < N; k++)
				for(int i = 0; i < N; i++)
					for(int j = 0; j < N; j++)
						if(k!=out && i!=out && j!=out && wf[i][k] && wf[k][j]) wf[i][j] = true;
			
			boolean[] rep = new boolean[N];
			for(int i = 0; i < N; i++)
				for(int j = 0; j < N; j++)
					if(i!=out && j!=out && wf[i][j] && wf[j][i]) { rep[j] = true; break; }
			
			int count = 0;
			for(int i = 0; i < N; i++) {
				if(i==out) continue;
				if(!rep[i]) continue;
				boolean isTop = true;
				for(int j = 0; j < N; j++) {
					if(j==out) continue;
					if(wf[j][i] && !wf[i][j]) isTop = false;
				}
				if(isTop) count++;
			}
			mincnt = Math.min(mincnt, count);
		}
		return (double)(N-mincnt)/N;
	}
}

Petrも同じ発想だったのでこれでいいのだろう。

975 StrangeElevator

H階ある建物において、次のようなエレベーターを考える:N個の箱が連結されているもので、箱間の相対的な位置関係は一定。エレベーターは停止位置がH/N個に決まっていて、各階にはちょうど1つの箱のみが止まるようになっている。このような条件を満たすエレベーターの個数をmodで数え上げろ。

組合せ難しい…

簡単に言えばメモ化再帰。ここではAとBの二種類の数え上げを考えた。

Aは「H,Nの条件を満たす組合せ全て」

Bは「最も下にある箱が、1階と2階の両方に止まるような組合せ」

どちらも、H/NとNの約数の組を列挙する。具体的には、(■■□□□□)のようなセットに対応する。このセットを1つの箱と見なすことで、再帰的に数え上げられる。

まあ要するに面倒くさい。

// Passed System Test
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;


const int MOD = 1000000007;

map<pair<pair<int,int>,bool>,long long> memo;
long long count_up(int R, int N, bool isB) {
	pair<pair<int,int>,bool> dpid = make_pair(make_pair(R,N),isB);
	map<pair<pair<int,int>,bool>,long long>::iterator it = memo.find(dpid);
	if(it != memo.end()) return it->second;
	
	vector<int> rs;
	for(int r = 1; r*r <= R; r++) {
		if(R%r > 0) continue;
		rs.push_back(r);
		if(r != R/r) rs.push_back(R/r);
	}
	vector<int> ns;
	for(int n = 1; n*n <= N; n++) {
		if(N%n > 0) continue;
		ns.push_back(n);
		if(n != N/n) ns.push_back(N/n);
	}
	long long cnt = 1;
	for(int rid = 0; rid < (int)rs.size(); rid++) {
		for(int nid = 0; nid < (int)ns.size(); nid++) {
			int r = rs[rid];
			int n = ns[nid];
			if(r==R) continue;
			if(n==1) continue;
			if(isB && n==N) continue;
			cnt = (cnt + count_up(r,n,true))%MOD;
		}
	}
	return (memo[dpid]=cnt);
}

struct StrangeElevator {
	int theCount(int H, int N) {
		if(H%N != 0) return 0;
		return (int)count_up(H/N,N,false);
	}
};

Petrのコードを見ると、無駄にクロージャみたいなコードになっててきもかった。確かに約数列挙とかそのほうが書きやすいけど…

反省

せっかく書いたコードを、メモ化もしないで提出するのは極めて不注意

まとめ

そろそろコーディング時間を考えたほうがいいかもしれない。

そんじゃーね!

wntxmiwntxmi 2011/02/28 05:43 prtLql <a href="http://tkehfokbtfwo.com/">tkehfokbtfwo</a>, [url=http://wzrlurmhxkep.com/]wzrlurmhxkep[/url], [link=http://xzrysunlquyz.com/]xzrysunlquyz[/link], http://hmujtnnplomy.com/

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/qnighy/20110209
 |