Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/28

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

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

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

lurhlpgihxdlurhlpgihxd2012/07/10 21:512sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

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