Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/28

TopCoder Open 2010 Algorithm Qualification Round 3 SumRectangle

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10948&rd=14278

問題

二次元の表の一番左の列と一番上の行の値が与えられている.あるセルの値は下と右下と右のセルの和になっている.表の一番右下の値を求める.

アプローチ

特に工夫は必要なし.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define sz(a) int((a).size())

using namespace std;

int m[10][10];

int getCorner(vector <int> leftColumn, vector <int> topRow)
{
	int nl = leftColumn;
	int nt = topRow;
	
	Rep(j,nl)
		m[j][0] = leftColumn[j];
	Rep(i,nt)
		m[0][i] = topRow[i];
	
	For(j,1,nl) For(i,1,nt)
		m[j][i] = m[j-1][i-1] - m[j][i-1] - m[j-1][i];
	
	return m[nl-1][nt-1];
}

TopCoder Open 2010 Algorithm Qualification Round 3 WhatsThisChord

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10927&rd=14278

問題

ギターの弦を押さえる時にどのコードになるのかを求める問題.6つの弦のどのフレットを押さえるのかが数値で与えられる.特に 0 なら開放弦,-1 なら弾かない,である.どの音の Major か Minor なのかを判定する.

アプローチ

全探索でも全く問題ないが,コードが汚くなる.

とりあえず押さえる弦を配列に突っ込んで 12 の剰余を取って unique をかけて正規化する(*1).ここで要素が 3 つでなければ終了.3 つの場合,その後ろにそれぞれ 12 を足した値を追加しておくと(*2)後のコード判定がすっきりして楽になる(*3).

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

typedef vector<int> VI;

#define pb push_back
#define sz(a) int((a).size())

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define Unique(v) \
	sort((v).begin(),(v).end());\
	v.resize(unique((v).begin(),(v).end())-(v).begin());
	
int s[6] = {4,9,2,7,11,4};
string name[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};

string classify(vector<int> chord)
{
	VI c;
	Rep(i,6) if(chord[i]>=0)
		c.pb((chord[i]+s[i])%12);
	// (*1)
	Unique(c);
	
	if(sz(c)!=3)
		return "";
	
	// (*2)
	Rep(i,3)
		c.pb(c[i]+12);
	
	// (*3)
	Rep(i,3)
	{
		if(c[i+1]-c[i]==4 && c[i+2]-c[i+1]==3)
			return name[c[i]]+" Major";
		if(c[i+1]-c[i]==3 && c[i+2]-c[i+1]==4)
			return name[c[i]]+" Minor";
	}
	
	return "";
}

TopCoder Open 2010 Algorithm Qualification Round 3

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10929&rd=14278

問題

横 W 縦 H の芝生をダイアモンドカッターが切っていく.カッターの初期位置と,移動方向のプログラムが与えられたときに,芝生が何分割されているかを答える.

アプローチ

ある位置の芝生の左が切れているかどうかのフラグと上が切れているかどうかのフラグを用意しておき,プログラムを走らせて切っていき,最後に領域を数える.

領域を数えるのは再帰スタック,深さ優先)だと最悪 10^6 になるのでオーバーフローする.queue を使って幅優先探索を行う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

bool cutu[1024][1024];
bool cutl[1024][1024];
bool glass[1024][1024];

queue<PII> q;

int pieces(int W, int H, int startx, int starty, vector <string> program)
{
	Rep(j,H+1) Rep(i,W+1)
		cutu[j][i] = cutl[j][i] = glass[j][i] = false;
	Rep(i,W+1)
		cutu[0][i] = cutu[H][i] = true;
	Rep(j,H+1)
		cutl[j][0] = cutl[j][W] = true;
	
	int x = startx;
	int y = starty;
	
	Rep(pp,sz(program)) Rep(p,sz(program[pp]))
	{
		switch(program[pp][p])
		{
		case 'U':
			cutl[--y][x] = true;
			break;
		case 'D':
			cutl[y++][x] = true;
			break;
		case 'L':
			cutu[y][--x] = true;
			break;
		case 'R':
			cutu[y][x++] = true;
			break;
		}
	}
	
	int c = 0;
	Rep(j,H) Rep(i,W) if(!glass[j][i])
	{
		c++;
		q.push(mp(i,j));
		while(!q.empty())
		{
			PII co = q.front(); q.pop();
			int x = co.first;
			int y = co.second;
			if(glass[y][x])
				continue;
			glass[y][x] = true;
			if(!cutu[y][x])   q.push(mp(x,y-1));
			if(!cutu[y+1][x]) q.push(mp(x,y+1));
			if(!cutl[y][x])   q.push(mp(x-1,y));
			if(!cutl[y][x+1]) q.push(mp(x+1,y));
		}
	}
	
	return c;
}

DiegoDiego 2012/07/10 00:56 The pucrahses I make are entirely based on these articles.

rcomsiercomsie 2012/07/10 15:55 WkGRgf <a href="http://ndjqpxpaabuy.com/">ndjqpxpaabuy</a>

lurhlpgihxdlurhlpgihxd 2012/07/10 21:51 2sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

sxyqsmsxyqsm 2012/07/12 12:11 UCCj2u <a href="http://srlypizeryby.com/">srlypizeryby</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yuyarin/20100528