Hatena::Grouptopcoder

qnighy[黄色]

 | 

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

まとめ

ねむい。

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

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/

 |