アルゴリズムの問題にチャレンジした

12月です。いろんなAdventCalendarがあって、楽しませてもらってます。今回はその中でも、id:hama_DUさんの記事 http://d.hatena.ne.jp/hama_DU/20111204 の問題がRTで流れてきて、興味を持ったので、勝手に挑戦してみようと思います(迷惑だったら言ってください、消します)。べ、べつに他に書くネタが無いからってわけじゃないよ?

できた

最初にできたコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

int main()
{
	int input = -1;

	const int d_min = 1;
	const int d_max = 25;

	while( input != 0 )
	{
		std::cin >> input;

		std::array< int, d_max > array = {};

		if( input != 0 )
		{
			std::vector< int > vect;

			for( int i = 0; i < input; ++i )
			{
				int num = 0;
				std::cin >> num;
				vect.push_back( num );
			}

			std::sort( vect.begin(), vect.end() );

			int max = vect.back();

			{
				const int max_count = std::count( vect.begin(), vect.end(), max );

				for( int i = 0; i < max_count; ++i )
				{
					auto it = std::min_element( & array[ max - 1 ], & array[ d_max - 1 ] + 1 );
					++( * it );
				}
			}

			for( auto it = vect.rbegin(), end = vect.rend(); it != end; ++it )
			{
				if( * it < max )
				{
					max = * it;

					const int max_count = std::count( vect.begin(), vect.end(), max );

					for( int j = 0; j < max_count; ++j )
					{
						auto it = std::min_element( & array[ max - 1 ], & array.back() + 1 );
						++( * it );
					}
				}
			}
			std::cout << * std::max_element( array.begin(), array.end() ) << std::endl;
		}

	}
	return 0;
}

大体30分位( + std::arrayの仕様(&array[ size ] のassert )に悩まされること長し)。とても遅い(アルゴリズム的な意味でも)。
毎回全探索していますね。ソートして、どんな日でもいい人ではなく、一番条件の厳しい人から順番に、"条件内で一番空いている日"を毎回探しています。

改良した

あまりに効率の悪いコードです。もうちょっと効率よくできそうです。

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

int main()
{
	int input = -1;

	const int d_min = 1;
	const int d_max = 25;

	while( input != 0 )
	{
		std::cin >> input;

		std::array< int, d_max > array = {};

		if( input != 0 )
		{
			std::vector< int > vect;

			for( int i = 0; i < input; ++i )
			{
				int num = 0;
				std::cin >> num;
				vect.push_back( num );
			}

			std::sort( vect.begin(), vect.end() );

			for( auto it = vect.rbegin(), end = vect.rend(); it != end; ++it )
			{
				bool find = false;
				for( std::size_t i = *it - 1, size = array.size(); i < size - 1; ++i )
				{
					if( array[ i ] < array [ i + 1 ] )
					{
						++array[ i ];
						find = true;
						break;
					}
				}

				if( ! find )
					++array.back();
			}
			std::cout << * std::max_element( array.begin(), array.end() ) << std::endl;
		}

	}
	return 0;
}

10行ほど短くなりましたね。こっちのほうが速いです。条件内で一番後ろから、可能な限り公平に分散できるようにしました。条件内で、全ての日が同じ人数で埋まっていれば最後の日に、そうでない場合は、奥から順に埋まっていくので、手前の日から見て行って、次の日よりも人数が少ない日に人を配置します(もちろん、条件内で)。

最後に

特にまとめも思い浮かびませんが、解いていて楽しかったです。後は、改良したコードをすぐに思いつけるようになりたいですね！