AOJ2027 Reading a Chord

問題リンク Reading a Chord

• 概要

M個のトーンからなる音がなるようなコードを全て列挙せよ。ただし、各トーンのオクターブの高さは考慮しなくてよい。
コードは図1にある通りである。
コードに任意のテンションをつけることができる。例えば、(-9)というテンションを付けると、ベース音から1半音高い音を更に鳴らすことができる。ただし、(-5)と(+5)だけは特別で、これはベース音から7半音高い音を半音下げ、上げする(7半音高い音はならない)。

• 解法

BNF記法があったりしますが、ちょっとしたこけおどしでやることは単純な全探索です。
ベース音を決め、そのベース音のコードを全て試します。更に、それで目的の音が出せないならばテンションを全て付けるのを試します。
トーンの音はCから順に0, 1, 2と数字と思えば、相対位置を使って処理を書くことができます。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Reading a Chord
public class AOJ2027 {

	boolean ok(boolean[] a, boolean[] b){
		for(int i=0;i<12;i++)if(a[i]!=b[i])return false;
		return true;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		String[] tones = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
		String[] add = {"","7","M7","m","m7"};
		int[][] adds = {{4,7},{4,7,10},{4,7,11},{3,7},{3,7,10}};
		String[] tension = {"","-9","9","+9","-11","11","+11","","-13","13","+13"};
		int T = sc.nextInt();
		while(T--!=0){
			int n = sc.nextInt();
			boolean[] t = new boolean[12];
			for(int i=0;i<n;i++){
				String c = sc.next();
				for(int k=0;k<12;k++)if(tones[k].equals(c)){
					t[k] = true; break;
				}
			}
			List<String> res = new ArrayList<String>();
			for(int b=0;b<12;b++)for(int a=0;a<5;a++){
				boolean[] r = new boolean[12];
				r[b] = true;
				for(int k:adds[a])r[(b+k)%12] = true;
				if(ok(r, t)){
					res.add(tones[b]+add[a]); continue;
				}
				for(int k=1;k<11;k++){
					if(k==7)continue;
					int x = (b+k)%12;
					boolean p = r[x];
					r[x] = true;
					if(ok(r, t))res.add(tones[b]+add[a]+"("+tension[k]+")");
					r[x] = p;
				}
				r[(b+7)%12] = false; r[(b+18)%12] = true;
				if(ok(r, t))res.add(tones[b]+add[a]+"(-5)");
				r[(b+18)%12] = false; r[(b+8)%12] = true;
				if(ok(r, t))res.add(tones[b]+add[a]+"(+5)");
			}
			if(res.isEmpty())System.out.println("UNKNOWN");
			else{
				for(int i=0;i<res.size();i++)System.out.print(res.get(i)+(i==res.size()-1?"\n":" "));
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ2027().run();
	}
}