AOJ2082 Goofy Converter

問題リンク Goofy Converter

• 概要

N, MとN個のLiが与えられる。全ての i (0 <= i < N)について
Li = Σ(i <= j < i+M)Kj
が成り立つような長さN+M-1の{0,1}ビット列Kが存在するか。存在するならばそれのうちいずれか1つを、無ければGoofyと答えよ。
1 <= N <= 1000
1 <= M <= 12
0 <= Li <= M

• 解法

Kはつまり、インデックスiから始まる長さMの区間に登場する1の数がLiと等しくなるという意味となります。
つまり、最初のM個の0, 1を決めてしまえば、その後のKiは自動的に決まることになります。
全てのiについてKiが正しく求まったらそれが答えです。全通り試して見つからないならGoofyです。

• ソース

import java.util.Scanner;

//Goofy Converter
public class AOJ2082 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt();
			if((n|m)==0)break;
			int[] a = new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			String res = "Goofy";
			for(int S=0;S<1<<m;S++){
				StringBuilder sb = new StringBuilder();
				int s = 0, h = 0;
				boolean f = true;
				for(int k=0;k<m;k++){
					sb.append((S>>k)&1);
					if(((S>>k)&1)>0)s++;
				}
				if(s!=a[0])continue;
				for(int i=1;i<n&&f;i++){
					if(sb.charAt(h++)=='1')s--;
					if(a[i]==s)sb.append("0");
					else if(s+1==a[i]){
						sb.append("1"); s++;
					}
					else f=false;
				}
				if(f){
					res = sb.toString(); break;
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2082().run();
	}
}