Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM491 DIV1 EASY (250pt)
TopCoder SRM491 DIV2 MEDIUM (500pt)
Problem Statement (DIV1)
Problem Statement (DIV2)
SRM491 DIV1 自分の参加記録

問題概要

6面対のサイコロの作り方のパターン数を求める問題.回転して重なるなら同じとみなす.
各面にはそれぞれ異なる1~Nの数字を書き,向かい合う面の数字の和は全部一定で,それはK以上でなければならない.
DIV1では,Nは1000以下,Kは2000以下.
DIV2では,Nは50以下,Kは100以下.

解法

向かい合う数字に対してループを回して,それを達成できる組の数 choose 3を足していけば良い.
最後に,同じ数字の組でも2パターン作れるので2をかける.
達成できる組の数は数学的にO(1)で求まるが,DIV1でもNは1000以下で,O(N^2)でも構わないのでループして全部探しても良い.
以下はコードはループして全部探した.
DIV2の解法は調べてないが枝刈りしながら全探索しても間に合う? (50^6パターン)

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

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

#define ll long long

class FoxMakingDice {
public:
long long theCount(int N, int K) {
  ll i, j, k, p;
  ll res = 0;

  REP(k,K,2*N+1){
    p = 0;
    REP(i,1,N+1){
      j = k-i;
      if(j<=i) continue;
      if(j>N) continue;
      p++;
    }
    res += p*(p-1)*(p-2)/3;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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