Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2332-24d53968
この記事にトラックバックする(FC2ブログユーザー)

SRM560 DIV1 EASY/DIV2 MEDIUM - TomekPhone (この記事を編集する[管理者用])

Source

TopCoder SRM560 DIV1 EASY (250pt)
TopCoder SRM560 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

ケータイの文字入力.
文字の種類は50種類以下あって,それぞれの出現回数 (各1000回以下) が与えられる.
キーの数は50種類以下あって,それぞれのキーに割り当てられる最大文字数が与えられる.
各キーには,それぞれ1回押すと出てくる文字,2回押すと出てくる文字,…を割り当てることができる.
割り当てを自由にしてよいので,文字を全部入力するのに,必要なキーを押す回数の最小値を求める問題.
割り当て不可能ならそれを指摘する.

解法

出現頻度の高い順に,押すキー回数の小さいほうから割り当てる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class TomekPhone {
public:
int minKeystrokes(vector <int> oc, vector <int> ks) {
  int i,j,k,st;
  int res = 0;

  st = 0;
  sort(oc.rbegin(), oc.rend());

  rep(i,100){
    rep(j,ks.size()){
      if(ks[j] <= i) continue;
      if(st==oc.size()) continue;
      res += (i+1) * oc[st++];
    }
  }

  if(st < oc.size()) res = -1;
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2332-24d53968
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。