読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 110 - Meta-Loopless Sorts

-問題概要

Pascalソースコードを出力するソースコードを書けという問題です。
メタプログラミングといってもいいのかな?
条件としては変数名をアルファベットとして宣言し、readlnを使って入力処理。
繰り返し分を使わずにif文のみでソートを行うプログラムを出力せよという問題です。

-解法

insertion sort、挿入ソートを使って実装します。
挿入ソートの実装にはstd::listを使うと要素の挿入、削除がO(1)で便利です。
a,b,cがlistにソートされて保持されているとき、dをどこに挿入するかを全パターン試す、という感じです。
再帰を使ったバックトラック法を使って全列挙しましょう
計算量はO(n!)です。出力数が等しいのでこれ以上枝刈りできません。

-ソースコード

ansのほうのクリアを最初にするのを忘れていたため何度かTLEになってました。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define rti(i,b) for(auto (i)=(b).rbegin();(i)!=(b).rend();++(i))
#define LL long long
#define all(b) (b).begin(),(b).end()

#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line  getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num


#define space(n) printf("%*c",n,' ');
typedef list<char> LC;
LC bag;
LC ans;

void print_list(LC &arg){
	printf("%c", arg.front());
	itr(i, arg)if (i != arg.begin())printf(",%c", *i);
}

void solve(LC::iterator x,int indent){
	++x;
	if (x == bag.end()){
		space(indent); cout << "writeln(";
		print_list(ans);
		cout << ")" << endl;
	}
	else{
		itr(i, ans){
			space(indent);
			if (i != ans.begin())printf("else ");
			printf("if %c < %c then\n", *x, *i);
			i = ans.insert(i, *x);
			solve(x, indent + 2);
			i = ans.erase(i);
		}
		ans.push_back(*x);
		space(indent); printf("else\n");
		solve(x, indent + 2);
		ans.pop_back();
	}
}


int main(void){
	int n,m;
	cin >> n;
	rT(i, n){
		if (i)cout << endl;
		bag.clear();
		ans.clear();
		cin >> m;
		rT(i, m){
			bag.push_back('a' + i);
		}
		cout << "program sort(input,output);" << endl;
		cout<< "var" << endl;
		print_list(bag);
		cout << " : integer;" << endl;
		cout << "begin" << endl;
		space(2); cout << "readln(";
		print_list(bag);
		cout << ");" << endl;
		LC::iterator it = bag.begin();
		ans.push_back(*it);
		solve(it, 2);
		cout << "end." << endl;
	}
	return(0);
}