torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 574, Division 2, Level 1 : CityMap

概要

H \times W のグリッド状の地図の情報が文字列の配列として与えられる。
地図中の文字は '.' または英大文字である。

整数配列 POIs が与えられる。
次のような文字列 str を求めよ。
str[i] := 地図中に POIs[i] 個含まれる文字

解法

適当に数えて数字から文字を引けるようにしてから文字列を生成します。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define ITER( c ) __typeof( (c).begin() )
#define EACH( it, c ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )

#define fst first
#define snd second

class CityMap
{
public:
	string getLegend( vector <string> cityMap, vector <int> POIs )
	{
		 map<char,int> c_to_num;
		 REP( i, 0, cityMap.size() )
		 {
			 REP( j, 0, cityMap[0].size() )
			 {
				 c_to_num[ cityMap[i][j] ]++;
			 }
		 }

		 map<int,char> num_to_c;
		 EACH( it, c_to_num )
		 {
			 num_to_c[ it -> snd ] = it -> fst;
		 }

		 string res;
		 REP( i, 0, POIs.size() )
		 {
			 res += num_to_c[ POIs[i] ];
		 }
		 return res;
	}
};