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

反省

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

まとめ

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

そんじゃーね!

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

2011-02-07

SRM496Div1

| 19:14 | はてなブックマーク - SRM496Div1 - qnighy[黄色]

250 ColoredStrokes

Div2で練習したので略。

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

public class ColoredStrokes {
	public bool isR(char ch) {return ch=='R' || ch=='G';}
	public bool isB(char ch) {return ch=='B' || ch=='G';}
	public char at(string[] picture,int y,int x) {
		try { return picture[y][x]; } catch (Exception) {return '.';}
	}
	public int getLeast(string[] picture) {
		int h = picture.Length;
		int w = picture[0].Length;
		int count = 0;
		for(int y = 0; y < h; y++) {
			for(int x = 0; x < w; x++) {
				if(!isR(at(picture,y,x-1)) && isR(at(picture,y,x))) count++;
				if(!isB(at(picture,y-1,x)) && isB(at(picture,y,x))) count++;
			}
		}
		return count;
	}
}

ACRushの解答見たらビット演算使ってた。

500 OneDimensionalBalls

数直線上にn個の点があり、前方向か後方向に互いに等しい正の速度で等速運動している。ある時点とそれより後のある時点の2回の写真を撮ったが、2回目のときはダミーを追加した。2枚の写真が与えられたとき、その写真の条件を満たす2枚間の点の対応関係は何通りあるか。

まず、2回の間で各点がどれだけの距離を移動したかの候補をリストアップしてunique。そうすると、2部グラフの最大マッチングの数え上げになるが、一直線上なので上手いこと走査すると簡単に計算できる。

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

public class OneDimensionalBalls {
	public long countValidGuesses(int[] firstPicture, int[] secondPicture) {
		Arrays.sort(firstPicture);
		int[] times = new int[secondPicture.length];
		for(int i = 0; i < secondPicture.length; i++) {
			times[i] = Math.abs(secondPicture[i]-firstPicture[0]);
		}
		Arrays.sort(times);
		long cnt = 0;
		for(int i = 0; i < times.length; i++) {
			if(0<i && times[i-1]==times[i]) continue;
			if(times[i] == 0) continue;
			int tim = times[i];
			boolean[] vis = new boolean[firstPicture.length];
			long local_cnt = 1;
			for(int j = 0; j < firstPicture.length; j++) {
				if(vis[j]) continue;
				vis[j] = true;
				int pos = firstPicture[j];
				boolean fst = Arrays.binarySearch(secondPicture,pos-tim)>=0;
				int dups = 2;
				while(Arrays.binarySearch(secondPicture,pos+tim)>=0 && Arrays.binarySearch(firstPicture,pos+tim+tim)>=0) {
					dups++;
					pos += tim*2;
					vis[Arrays.binarySearch(firstPicture,pos)] = true;
				}
				boolean snd = Arrays.binarySearch(secondPicture,pos+tim)>=0;
				if(fst && snd) local_cnt *= dups;
				if( (!fst) && (!snd) ) local_cnt = 0;
			}
			System.out.println(tim+" : "+local_cnt);
			cnt += local_cnt;
		}
		return cnt;
	}
}
反省

Setを使えばもっと簡単にできた。

950 YetAnotherHamiltonianPath

文字列を頂点とするグラフがある。頂点AB間の距離はlen(A)^2+len(B)^2-len(LCP(A,B))^2で与えられる。(ただしLCPは最長共通接頭辞)ここで頂点0から頂点1までの最短ハミルトン路を計算せよ。

まず明らかに、len(A)^2やlen(B)^2は経路に関係なく同じ個数だけ取り除かれるので、len(LCP(A,B))^2の和を最小化すればいいことがわかる。直感的にいって、できるだけ共通接頭辞の長い経路を通るのがよいと思われる。問題は、始点と終点がよく共通しているにもかかわらず、途中でその共通性を壊さなければいけない場合である。

あまりちゃんとした証明は行わなかったが、始点または終点ともっともよく共通している頂点を選択し、それを新しい始点または終点とする、というアルゴリズムで行ったら上手くいった。

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

int cplen(const string& s1, const string& s2) {
	int len = (int)min(s1.size(),s2.size());
	for(int i = 0; i < len; i++) {
		if(s1[i] != s2[i]) return i;
	}
	return len;
}

struct YetAnotherHamiltonianPath {
	int leastCost(vector<string> label) {
		int cost = 0;
		for(int i = 0; i < (int)label.size(); i++) {
			cost += (i<2?1:2) * label[i].size() * label[i].size();
		}
		// printf("initial cost: %d\n",cost);
		string s1 = label[0];
		string s2 = label[1];
		vector<bool> vis(label.size());
		vis[0] = vis[1] = true;
		int viscount = label.size()-2;
		while(0 < viscount) {
			// printf("%s - (%d) - %s\n", s1.c_str(), viscount, s2.c_str());
			int maxval = -1;
			int maxid = -1;
			for(int i = 0; i < (int)label.size(); i++) {
				if(vis[i]) continue;
				int val = max(cplen(s1,label[i]),cplen(s2,label[i]));
				if(maxval < val) {
					maxval = val;
					maxid = i;
				}
			}
			vis[maxid] = true; viscount--;
			cost -= maxval*maxval;
			if(cplen(s1,label[maxid]) > cplen(s2,label[maxid])) {
				s1 = label[maxid];
			} else {
				s2 = label[maxid];
			}
		}
		cost -= cplen(s1,s2)*cplen(s1,s2);
		return cost;
	}
};

Editorialによると、UdH-WiNGeRによる解答が美しい。これは、文字列をソートした順に辿る閉路のコストを求めた後に、0から1の間の辺の重みを除く。


まとめ

やっぱり、よく考えてからコーディングしたほうが…

そんじゃーね!

nqfcftypbunqfcftypbu2011/02/27 22:35qyJesi <a href="http://bxzaqboxfinw.com/">bxzaqboxfinw</a>, [url=http://jdozspyohzgc.com/]jdozspyohzgc[/url], [link=http://zhktgvfkhfcr.com/]zhktgvfkhfcr[/link], http://tsgmogjzvcxx.com/

2011-02-06

SRM495Div2

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

Summary

shiftless[現在黄色]が最強だった回らしい。超準急ですねわかります

250 CarrotBoxesEasy

(にんじんの個数,-箱の番号)が最大の箱から1本食べる。これをK回繰り返す。最後に食べたにんじんの入っていた箱の番号。

「シンプルなシミュレーション」「箱をにんじんの個数(>)でソート」なども考えられるが、にんじんの個数100から下げつつ舐めて、その内部で箱番号を舐めるのが一番簡単だと思う。

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

public class CarrotBoxesEasy {
	public int theIndex(int[] carrots, int K) {
		int count = 0;
		for(int i = 99; i >= 0; i--) {
			for(int j = 0; j < carrots.Length; j++) {
				if(i < carrots[j]) count++;
				if(count == K) return j;
			}
		}
		return -1;
	}
}

525 ColorfulCards

狭義単調増加なn以下の自然数の列がある。各項目が素数かどうかだけがわかっている。数列の各項について、特定できるならその値を与えろ。

これは迷わず、「篩→上限と下限を設定」。シャクトリメソッド。

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

public class ColorfulCards {
	public int[] theCards(int N, String colors) {
		char[] cc = new char[N+1];
		cc[1] = 'B';
		for(int i = 2; i <= N; i++) cc[i] = 'R';
		for(int i = 2; i <= N; i++)
			if(cc[i] == 'R')
				for(int j = i*i; j <= N; j+=i)
					cc[j] = 'B';
		int[] ret = new int[colors.length()];
		int num = 1;
		for(int i = 0; i < colors.length(); i++) {
			while(cc[num] != colors.charAt(i)) num++;
			ret[i] = num++;
		}
		num = N;
		for(int i = colors.length()-1; i >= 0; i--) {
			while(cc[num] != colors.charAt(i)) num--;
			if(ret[i] != num--) ret[i] = -1;
		}
		return ret;
	}
}

1000 HexagonPuzzle

六角形のマス目が三角形状に存在し、マス目は互いに区別する。そのうち指定されたマスは取り除く。残ったマスの中で、互いに隣接する3マスの間で巡回swap操作を行えるとき、初期状態から到達しうる盤の状態数のモジュロ。

これは、まず、巡回swap操作でたどり着けるマス目をUnion-Findでグルーピングする。各グループ内は、2のパリティーを持つことが容易にわかる。なので、各グループごとにn!/2を計算して積を求める。

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

struct UF {
	vector<int> p;
	UF(int n):p(n,-1) {}
	int rt(int x) {return p[x]<0?x:(p[x]=rt(p[x]));}
	bool isrt(int x) {return x==rt(x);}
	int siz(int x) {return -p[rt(x)];}
	bool eq(int x,int y) {return rt(x)==rt(y);}
	void cat(int x,int y) {
		x=rt(x), y=rt(y);
		if(x==y) return;
		if(p[x]<p[y]) swap(x,y);
		p[y]+=p[x];
		p[x]=y;
	}
};

const int MOD = 1000000007;
struct HexagonPuzzle {
	int theCount(vector<string> board) {
		int n = board.size();
		UF uf(n*n);
		long long cnt = 1;
		for(int y = 0; y+2 < n; y++)
			for(int x = 0; x <= y; x++)
				if(board[y+2][x+1]=='.' && board[y+1][x]=='.' && board[y+1][x+1]=='.')
					uf.cat((y+2)*n+(x+1),(y+1)*n+x), uf.cat((y+2)*n+(x+1),(y+1)*n+(x+1));
		for(int y = 0; y+1 < n; y++)
			for(int x = 0; x <= y; x++)
				if(board[y][x]=='.' && board[y+1][x]=='.' && board[y+1][x+1]=='.')
					uf.cat(y*n+x,(y+1)*n+x), uf.cat(y*n+x,(y+1)*n+(x+1));
		for(int y = 0; y < n; y++)
			for(int x = 0; x <= y; x++)
				if(uf.isrt(y*n+x) && uf.siz(y*n+x)>1)
					for(int i = 3; i <= uf.siz(y*n+x); i++) cnt = cnt*i%MOD;
		return (int)cnt;
	}
};

まとめ

ねむい。

案外妥当にコーディングできてる気がする。

SRM496Div2

| 17:39 | はてなブックマーク - SRM496Div2 - qnighy[黄色]

250 AnagramFree

文字列集合をアナグラムで割ったときの個数。

「文字列の出現頻度を数え上げる」または「文字列内の文字列をソートして数え上げ」。

前者はC#においては配列の辞書順比較が存在しないため難しい。後者がお得のようだ。

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

public class AnagramFree {
	public int getMaximumSubset(string[] S) {
		for(int i = 0; i < S.Length; i++) {
			char[] cc = S[i].ToCharArray();
			Array.Sort(cc);
			S[i] = new string(cc);
		}
		Array.Sort(S);
		int count = 1;
		for(int i = 1; i < S.Length; i++) {
			if(S[i-1] != S[i]) count++;
		}
		return count;
	}
}

500 ColoredStrokes

横に赤く線を引くか、縦に青く線を引く。結果のマップが与えられたとき、最小ストローク数を求めよ。

赤と青は独立して数えればよい。シンプルな区間数え上げになる。

JavaはcharAtとか書くのが面倒だよねー。

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

public class ColoredStrokes {
	public boolean isR(char ch) { return ch=='R' || ch=='G'; }
	public boolean isB(char ch) { return ch=='B' || ch=='G'; }
	public int getLeast(String[] picture) {
		int h = picture.length;
		int w = picture[0].length();
		int count = 0;
		for(int x = 0; x < w; x++) {
			for(int y = 0; y < h; y++) {
				if((x==0 || !isR(picture[y].charAt(x-1))) && isR(picture[y].charAt(x))) count++;
				if((y==0 || !isB(picture[y-1].charAt(x))) && isB(picture[y].charAt(x))) count++;
			}
		}
		return count;
	}
}

1000 PalindromfulString

M文字の回文部分文字列をK種類もつようなN文字の文字列を数え上げろ。

僕の戦略は以下のとおり。

包除原理の拡張を用いることで、「N-M+1種類ある部分文字列のうち少なくとも決められたもの全てが回文になるような文字列の個数」の数え上げに帰着できる。

それは、Union-Findで必要な同値条件を数え上げ、独立に動かせる文字を26の指数に置けばよい。

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

long long negcomb(long long a, long long b) {
	a--; b--;
	if(a > b) return 0;
	long long x = 1;
	for(long long i = 0; i < b-a; i++) {
		x = -x * (b-i) / (i+1);
	}
	return x;
}

struct UF {
	int rtcnt;
	vector<int> p;
	UF(int n):rtcnt(n),p(n,-1) {}
	int rt(int x) {return p[x]<0?x:(p[x]=rt(p[x]));}
	bool isrt(int x) {return rt(x)==x;}
	void cat(int x, int y) {
		x=rt(x); y=rt(y);
		if(x==y) return;
		rtcnt--;
		if(p[x]<p[y]) swap(x,y);
		p[y] += p[x];
		p[x] = y;
	}
};

struct PalindromfulString {
	long long count(int N, int M, int K) {
		for(int y = 0; y < 5; y++) {
			for(int x = 0; x < 5; x++)
				printf("%3lld, ",negcomb(y,x));
			printf("\n");
		}
		long long cnt = 0;
		int n = N-M+1;
		for(int i = 0; i < (1<<n); i++) {
			UF uf(N);
			for(int j = 0; j < n; j++) {
				if((i>>j)&1) {
					for(int k = 0; k < M; k++) {
						uf.cat(j+k, j+M-1-k);
					}
				}
			}
			long long pp = negcomb(K, __builtin_popcount(i));
			for(int i = 0; i < uf.rtcnt; i++) pp*=26;
			cnt += pp;
		}
		return cnt;
	}
};
反省

解説によると、どの文字どうしが等しくてどの文字どうしは異なるかをあらわすグルーピングの組合せは全探索で数えられる程度しかないので、それらについて26Pnの総和を求めればよいだけらしい。

全探索の有効活用。ちぃ覚えた。

まとめ

ねむい。

あと、C#のArrays.Sortで80000程度以上の要素を比較するのは危険だということを研究していました。→https://gist.github.com/813142

xgwkffxxgwkffx2011/02/27 20:10W85Grp <a href="http://yipbnhvjunvp.com/">yipbnhvjunvp</a>, [url=http://gxgxyqnixacr.com/]gxgxyqnixacr[/url], [link=http://mmjhqkcmkdkm.com/]mmjhqkcmkdkm[/link], http://fvwfjuhdzkvi.com/