Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

3問のSRMライクなプログラミングコンテストが行われる.制限時間は75分.
 1問目を解くのにかかった時間をtとして,1問目を解いて得られる点数は p[0]-2t 点
 2問目を解くのにかかった時間をtとして,2問目を解いて得られる点数は p[1]-4t 点
 3問目を解くのにかかった時間をtとして,3問目を解いて得られる点数は p[2]-8t 点
どの順番から問題を解いても良いし,解かなくても良い.
各問題を解くのに必要な時間が与えられる.
また,運が与えられ,それを1消費することで,1問選んでその問題を解くのに必要な時間を-1分できる.(必要時間は0以下にはできない)
達成できる最大点数を求める問題.運は100以下.

解法

全探索.
運の割り振り方を全部試して,どの問題を解くかを全部試す.
どの問題を解くかだけ探索すれば,運の割り振り方はgreedyでも良い.

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 SRMCodingPhase {
public:
int countScore(vector <int> points, vector <int> skills, int luck) {
  int i,j,k;
  int a,b,c;
  int res = -1;
  int dec[3] = {-2, -4, -8};
  int tot, score, tm[3];

  rep(a,luck+1) rep(b,luck+1){
    c = luck - a - b;
    if(c < 0) continue;

    rep(i,3) tm[i] = skills[i];
    tm[0] -= a;
    tm[1] -= b;
    tm[2] -= c;
    rep(i,3) if(tm[i] < 1) tm[i] = 1;
    
    rep(k,1<<3){
      tot = score = 0;
      rep(i,3) if(k&1<<i){
        tot += tm[i];
        score += points[i] + dec[i] * tm[i];
      }
      if(tot > 75) continue;
      if(score > res) res = score;
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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