makeplex presents 史上最強のプログラマー検定試験提出回答

• 深さ優先探索
• 初めに待ちを固定して手に加えた状態から探索開始
• 深さ0〜3では順子・刻子を全数検査
• 深さ4では頭を全数検査
• 解となる文字列の生成ではどの順子・刻子・頭に待ちがあるかを固定して生成
• 重複した解が出力されないようsetを使用
• 途中状態をメモしたところ違うパスで同じ状況になりうるパターンが有ったためメモを破棄した
• 問題ページに掲載されている入出力データは試した
• それ以外は試していない
• 七面子は対応していない

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;

vector<vector<int> > path;
set<string> answers;

// 答えを登録する
void regist(int waiting) {
	vector<vector<int> > hand = path;
	sort(hand.begin(), hand.end());
	for (int headIndex = 0; headIndex < hand.size(); ++headIndex) {
		// 待ちを含む順子・刻子・アタマを探す
		if (find(hand[headIndex].begin(), hand[headIndex].end(), waiting) == hand[headIndex].end()) {
			continue;
		}

		// 待ちを含まない順子・刻子・アタマを文字列化する
		string s;
		for (int index = 0; index < hand.size(); ++index){
			if (index == headIndex) {
				continue;
			}

			s += '(';

			for (vector<int>::iterator it = hand[index].begin(), itEnd = hand[index].end(); it != itEnd; ++it) {
				s += (char)(*it + '0');
			}
			s += ')';
		}

		// 待ちを含む順子・刻子・アタマを文字列化する
		bool firstWaiting = true;
		s += '[';
		for (vector<int>::iterator it = hand[headIndex].begin(), itEnd = hand[headIndex].end(); it != itEnd; ++it) {
			if (firstWaiting && *it == waiting) {
				firstWaiting = false;
				continue;
			}
			s += (char)(*it + '0');
		}
		s += ']';

		// 答えとなる文字列を登録する
		// 重複は自動的に弾かれる
		answers.insert(s);
	}
}

//// メモ付き探索のキーを生成するためのハッシュ生成関数
//ll makeHash(int cards[]) {
//	ll hash = -1;
//	for (int i = 1; i <= 9; ++i) {
//		hash *= 137;
//		hash += cards[i];
//	}
//	return hash;
//}
//
//set<ll> memo;

// メモ付き探索
// ・・・にしようとしたら同じ状態で違う解というパターンが
// 有ったので泣く泣く普通の探索に・・・
void dfs(int depth, int waiting, int cards[]) {
	//const ll hash = makeHash(cards);
	//if (memo.count(hash)) {
	//	return;
	//}
	//memo.insert(hash);

	// 頭の探索
	if (depth == 4) {
		for (int head = 1; head <= 9; ++head) {
			if (cards[head] == 2) {
				vector<int> heads(2, head);
				path.push_back(heads);
				regist(waiting);
				path.pop_back();
				break;
			}
		}
		return;
	}

	// 順子の探索
	for (int start = 1; start <= 7; ++start) {
		if (cards[start] && cards[start + 1] && cards[start + 2]) {
			vector<int> triple;
			triple.push_back(start);
			triple.push_back(start + 1);
			triple.push_back(start + 2);
			path.push_back(triple);

			--cards[start];
			--cards[start + 1];
			--cards[start + 2];
			dfs(depth + 1, waiting, cards);
			++cards[start];
			++cards[start + 1];
			++cards[start + 2];
			path.pop_back();
		}
	}

	// 刻子の探索
	for (int start = 1; start <= 9; ++start) {
		if (cards[start] >= 3) {
			vector<int> triple(3, start);
			path.push_back(triple);

			cards[start] -= 3;
			dfs(depth + 1, waiting, cards);
			cards[start] += 3;

			path.pop_back();
		}
	}
}

int main() {
	string in;
	cin >> in;
	int cards[10];
	memset(cards, 0, sizeof(cards));
	for (int i = 0; i < in.size(); ++i) {
		++cards[in[i] - '0'];
	}

	// 待ちを固定して探索
	for (int waiting = 1; waiting <= 9; ++waiting) {
		// すでに四枚ある場合はスキップ
		if (cards[waiting] == 4) {
			continue;
		}

		++cards[waiting];
		dfs(0, waiting, cards);
		--cards[waiting];
	}

	for (set<string>::iterator it = answers.begin(); it != answers.end(); ++it) {
		cout << *it << endl;
	}
}

以上、よろしくお願いいたします。

makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ - http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html