Topcoder SRM560 DIV1 TomekPhone

Calendar Clock iconCalendar Clock icon

topcoder

目次

# 問題

https://community.topcoder.com/stat?c=problem_statement&pm=12296

ガラケーのようにキーボードのキー数がアルファベットの数よりも大きい可能性のある状況で、あるテキストをすべてタイプするための最小の総タイプ数を答える問題です.

# 入力

{ f_1, f_2, ..., f_N }
{ k_1, k_2, ..., k_M }
  • f_i - 入力テキスト中のアルファベットiの出現回数です.
  • k_i - キーボードのキーiに割り当てられるアルファベット数です.

それぞれの配列の長さは1以上50以下です.

# 出力

あるテキストをすべてタイプするための最小の総タイプ数を出力してください.
タイプ不可能な場合は-1を出力してください.

例えばadefが打てるキー1とzyxが打てるキー2のみがある場合、aをタイプするには1度のタイプで済み、fをタイプするには4度のタイプが必要です.
テキストがfyの場合は合計で6度のタイプが必要になります.

# 入出力例

{ 11,23,4,50,1000,7,18 }
{ 3,1,4 }
1164

# 解説

アルファベットとキーボード上のキーの最も効率的なマッピングを考える問題です.

50 x 50の組み合わせ数なのでO(2N)O(2^N)の全探索の計算量では間に合いません.
それ以下であれば間に合いそうです.

問題の性質をよく考えてみると、頻度の高い順に空いている最も距離の近い位置に配置していっても全くペナルティは無いことが分かります.
では同じ距離である場合はどのキーを選んだら良いでしょうか.
答えは残りの割当可能な位置が最も少ないキーです.
割当可能な位置が多くて最後の位置に近づくほどタイプするが増えるので価値は下がります.
価値が低い位置には出現頻度が低いアルファベットを割当るべきです.

# 計算量

アルファベットの数をFFとすると、

O(F)

# 解答

Topcoderに提出するフォーマットのクラスです.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
class TomekPhone {
public:
  int minKeystrokes(vector<int> &frequencies, vector<int> &keySizes) {
    int F = frequencies.size(), K = keySizes.size(), count = 0;
    // 頻度の高いキーほど前半に消費すれば少ないタイプ数で済む
    sort(span_all(frequencies));
    reverse(span_all(frequencies));
    // 多くのキーを処理出来るものは価値が高いので先に消費する
    sort(span_all(keySizes));
    vector<int> keyUsed(K, 0);

    int key_i = 0, f_i = 0;
    while (f_i < F) {
      int f = frequencies[f_i];
      if (keyUsed[key_i] < keySizes[key_i]) { // キーkey_iにまだ未割り当ての位置が残っているか
        count += f * (keyUsed[key_i] + 1); // タイプ数 = 出現回数 x キーの位置
        keyUsed[key_i]++; // そのキーのkey_i番目を割り当て済みとする
        key_i = (key_i + 1) % K; // 次のキー. 位置0のキーがすべて割当済みなら位置1に移動する
        f_i++;
      } else {
        key_i = (key_i + 1) % K;
        if (keyUsed[key_i] >= keySizes[key_i]) return -1; // 割当可能な位置が無くなったらタイプ不可能.
      }
    }

    return count;
  }
};

リモートフリーランス。ウェブサービス、スマホアプリエンジニア。
東アジアを拠点に世界を移動しながら活動してます!

お仕事のご依頼・お問い合わせはこちら

コメント