Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM533 DIV1 HARD - Pikachu (この記事を編集する[管理者用])

Source

TopCoder SRM533 DIV1 HARD (1000pt)
Problem Statement

問題概要

N個 (30以下) の単語にピカチュー語を割り振る問題.
k番目の単語の出現頻度freq[k] (1以上1000以下) が与えられる.
k番目の単語に割りふるピカチュー語code[k]は以下を満たさなければいけない.
 code[k] は "pi", "ka", "chu" を何個か繋げてできる単語.(同じのを繋げても良い,pikapi, pikachuなどが可能)
 code[i] は code[j] のprefixになっていない.(i != j)
length(code[k]) * freq[k]の和の最小値と,最小値を達成できる割り当て方が何パターンあるかを mod 1000000009 で求める問題.

解法

メモ付き探索.freqの値はソートしておく.
最初使えるcodeは長さ0のコード1つのみとして,長さkのコードは,単語に割り振るか,長さk+2, k+2, k+3のコードを生成できると考える.
状態を,まだ割り振ってない単語の数,今使えるコードの種類として,以下のように探索していく.
 今使えるコードの種類のうち,最も長さの短いものの数をxとして,その内の何個を単語に割り振るかで場合分けする.(他はコード生成に使う)
 割り振る単語はfreqの高い方から割り振れば良い.割り振る単語の選び方のパターン数,freqが同率の場合はどれに割り振るかのパターン数を計算しながら探索する.
新しくコードを作るときは,残り単語数より多くのコードを生成しても意味無いので,作り過ぎないように適当に処理する.
以下のコードで最悪ケース0.072 sec.

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

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

#define ll long long
#define M 1000000009

int n;
int in[100];
map<vector<int>,pair<ll,ll> > dp;

ll comb[100][100];
ll fact[100];

pair<ll,ll> solve(vector<int> s){
  int i,j,k;
  int rest, n, can, m, mx, mi;
  pair<ll,ll> res = make_pair(1000000000000LL, 0LL), tmp;
  ll pat, add;

  if(dp.count(s)) return dp[s];

  rest = s[0];
  n = s.size() - 1;
  if(rest==0) return make_pair(0LL, 1LL);
  if(n==0) return res;

  can = (rest - n + 1) / 2;
  if(can < 0) can = 0;

  REP(k,1,n) if(s[k+1]!=s[1]) break;

  rep(i,min(can,k)+1){
    if(rest - (k-i) < 0) continue;

    vector<int> next;
    pat = comb[k][i];
    pat = (pat * fact[k-i]) % M;
    
    m = rest - (k-i);
    mx = mi = m;
    while(mx+1 < rest && in[m]==in[mx+1]) mx++;
    while(mi-1 >= 0   && in[m]==in[mi-1]) mi--;
    pat = (pat * comb[mx-mi+1][mx-m+1])%M;

    next.push_back(rest-(k-i));
    REP(j,k,n) next.push_back(s[1+j]);
    rep(j,i) next.push_back(s[1]+2), next.push_back(s[1]+2), next.push_back(s[1]+3);
    sort(next.begin()+1, next.end());

    add = 0;
    rep(j,k-i) if(rest-1-j >= 0) add += in[rest-1-j] * s[1];

    tmp = solve(next);
    tmp.first += add;
    tmp.second = (tmp.second * pat) % M;

    if(res.first > tmp.first) res = tmp;
    else if(res.first == tmp.first) res.second += tmp.second;
  }

  return dp[s] = res;
}

class Pikachu {
public:
vector <int> bestEncoding(vector <int> freq) {
  int i,j,k;
  vector <int> res, send;
  pair<ll,ll> hoge;

  if(freq.size() % 2 == 0) freq.push_back(0);

  fact[0] = 1;
  REP(i,1,100) fact[i] = (fact[i-1] * i)%M;

  rep(i,100) comb[0][i] = 0;
  rep(i,100) comb[i][0] = 1;
  REP(i,1,100) REP(j,1,100) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j])%M;

  n = freq.size();
  rep(i,n) in[i] = freq[i];
  sort(in, in+n);

  send.push_back(n);
  send.push_back(0);
  dp.clear();
  hoge = solve(send);

  res.push_back(hoge.first);
  res.push_back(hoge.second);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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