Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

うなぎを切って,ちょうど長さ10の破片をできるだけたくさん作る問題.
要素数N (50以下) の整数列が与えられる.(各要素は0以上1000以下)
maxCut回以下だけ,次の操作ができる.(maxCutは1000以下)
ある要素xを取り除いて,0より大きくxより小さい整数yを選び,2つの要素x-yとyを加える.
最終的に,10の数の最大値を求める問題.

解法

greedy.
yとしては10以外を選ぶ必要はない.
x-yとして10になると1回得するので,できるだけその回数を増やしたい.
10の倍数で,小さいものから切っていく,10の倍数がなければ何でもいいから切っていく.
どのうなぎまで処理したか,切れる残り回数を状態としてDPしても良い.O(50*1000^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 Cut {
public:
int getMaximum(vector <int> len, int cut) {
  int i,j,k,n;
  int res = 0;

  sort(len.begin(), len.end());
  n=len.size();
  
  rep(i,n) if(len[i]%10==0){
    for(;;){
      if(len[i] == 0) break;
      if(len[i] == 10){ res++; len[i]--; break; }
      if(cut==0) break;
      len[i] -= 10; cut--; res++;
    }
  }

  rep(i,n){
    for(;;){
      if(len[i] < 10) break;
      if(cut==0) break;
      res++; cut--; len[i]-=10;
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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