Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

斜め45度傾いた正方形の真ん中から,端に移動するまでのパスの数を求める問題.

解法

適当にDPした.
パスカルの三角形が4つあると思えば簡単に書ける.

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

class WordPattern {
public:
ll countWords(string word) {
  int i,n=word.size();
  ll dp[500];

  if(n==1) return 1;
  
  dp[0]=0;
  REP(i,1,500) dp[i]=dp[i-1]*2 + 4*2;

  return 4 + dp[n-2];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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