SRM 560, Division 2, Level 2 : TomekPhone

概要

トグル式で入力する携帯電話のキーボードを設計した。
キーには自由に文字を割り当てられる。
各キーに割り当てられる文字の数と、ある文章中に出現する文字の数が与えられる。
その文章をタイプするのに必要なタイプ数の最小値を求めよ。
文字を割り当て切れない場合は -1 を返却せよ。

本番中の思考

• -1 を返すパターンは出現する文字の数が割り当ての合計より多いときか
  • 先に弾けば accumulate() 使える！！！
• 出現数の多いものから優先的に割り当てる Greedy でいけそう
  • 最初はキーを pair で表そうとしたけど、そこまでの情報量は要らない
  • 必要なのは、各キーから取り出される「必要なタイプ数」だけ
  • 適当に二重ループで vector に
• 出現回数を降順、キーのタイプ数を昇順にソートして、乗じながら足せばできるな

本番中に書いたコード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

class TomekPhone
{
public:
	int minKeystrokes(vector <int> occurences, vector <int> keySizes)
	{
		const int KEYS = occurences.size(), N = keySizes.size();

		if ( accumulate( ALL( keySizes ), 0 ) < KEYS )
		{
			return -1;
		}

		vector<int> types;

		REP( i, 0, N )
		{
			REP( j, 0, keySizes[i] )
			{
				types.PB( j + 1 );
			}
		}

		sort( ALL( occurences ), greater<int>() );
		sort( ALL( types ) );

		int res = 0;

		REP( i, 0, KEYS )
		{
			res += occurences[i] * types[i];
		}

		return res;
	}
};

本番での得点

362.62 pts