Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Round 2 MEDIUM - RepresentableNumbers (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 2 MEDIUM (500pt)
Problem Statement
Open 2010 Algorithm Round 2 自分の参加記録

問題概要

与えられた正整数X以上で,2つのtotally oddな整数の和で書ける最小の数字を求める問題.
totally oddとは,各桁が全て奇数.
Xは100000000以下.

解法

100000000以下のtotally oddな正整数は50万個ぐらいしかないので,列挙して,ソートして,尺取メソッドする.
または,0か1だと2つの奇数の和で表すと繰り上がりしないといけない,などといった条件を考えて,Adhocに2つのtotally oddな整数の和で書けるかどうかを判定して,書けないかぎりincreaseしていくなどでも解ける.
以下のコードは尺取メソッド.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

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

int lis[1000000], size;

void gen(int depth,int now){
  int i;
  
  if(depth && depth<=8) lis[size++] = now;
  if(depth==8) return;

  rep(i,5) gen(depth+1, now*10 + i*2+1);
}

class RepresentableNumbers {
public:
int getNext(int X) {
  int i,j,k;
  int res=2000000000;

  size=0;
  gen(0,0);

  sort(lis,lis+size);

  j=0;
  rep(i,size){
    while(lis[i]+lis[j] < X) j++;
    while(j && lis[i]+lis[j-1] >= X) j--;
    if(res > lis[i]+lis[j]) res = lis[i]+lis[j];
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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