Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

曲の初めは速くて,曲の終わりは速い,そういう曲がff曲 (1000以下) ある.
曲の初めは速くて,曲の終わりは遅い,そういう曲がfs曲 (1000以下) ある.
曲の初めは遅くて,曲の終わりは速い,そういう曲がsf曲 (1000以下) ある.
曲の初めは遅くて,曲の終わりは遅い,そういう曲がss曲 (1000以下) ある.
アルバムに収録するにあたって,
 曲の終わりが速い曲の後ろには,曲の初めは速い曲でなくてはいけなく,
 曲の終わりが遅い曲の後ろには,曲の初めは遅い曲でなくてはいけなく,
 曲の始めが速い曲が1曲でもあるなら,アルバムの最初の曲の初めは速くなければいけない.
最大で何曲アルバムに収録できるかを求める問題.

解法

最初も最後も速い曲とか,最初も最後も遅い曲は,使える時にとりあえず使ってしまえば良い.
後は,シミュレーションでO(曲数)でも,解析的に求めてO(1)でもどっちでも良い.
以下のコードはできるだけ場合分けを少なくする目的でシミュレーション.

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

class RockStar {
public:
int getNumSongs(int ff, int fs, int sf, int ss) {
  int res = 0;
  string now;

  now = "fast";
  if(ff+fs==0) now = "slow";

  for(;;){
    if(now=="fast"){
      res += ff; ff = 0;
      if(!fs) break;
      res++; fs--; now = "slow";
    } else {
      res += ss; ss = 0;
      if(!sf) break;
      res++; sf--; now = "fast";
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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