Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-31

[][] Project Euler Problem 113 09:09 はてなブックマーク -  Project Euler Problem 113 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=113

要約

 正数で,各桁の数を順番に見ていった時単調増加でも単調減少でもない数をbouncy numberと呼ぶ事にする.10^{100}未満の数の中でbouncy でない数の個数を求めよ.

方針

便宜上まずは0もbouncy numberに入れて数え上げる.単調増加の数は

0001123・・・999(leading zeroも含めて100桁)

の用になるもの.これの数は横に100マス縦に9マスある格子道を左下から右上に進む進み方なので,109C9通り,

 単調減少の数は

99988877・・・000 (leading zeroがなく100桁以下)

これは9より大きい数がleading zeroの代わりにあると考えれば(これを*と書くことにする),11種類の数を重複を用いて100個並べる並べ方なので,110C10通り.

ここからモレ,ダブりを除いていく

  • 単調増加かつ単調減少
    • 正数としてvalid (000011・・11から000099・・99と****11・・11から****99・・99) (1)
    • 正数としてinvalid (00・・00)  (2)
  • 単調増加だが単調減少でない
    • 正数としてvalid
    • 正数としてinvalid (なし)
  • 単調増加でないが単調減少
    • 正数としてvalid
    • 正数としてinvalid (*00・・00, **00・・00, ・・, **・・**00, **・・**0, **・・**) (3)

(1)は2回重複して数えているのを1回に減らす.(2)は2回,(3)は1回数えているがこれらは両方除外する.従って,求める個数は

108C9 + 109C9 - 100 * 9 - 2 -  100
コード例(c++
#include <iostream>

using namespace std;

typedef long long ll;

ll n = 100;

ll comb(ll n, ll m){
  if(m == 0 || m == n) return 1;
  return comb(n-1, m-1)* n / m;
}


int main(){
  cout << comb(n + 9, 9) + comb(n + 10, 10) - 10 * n - 2 << endl;
  return 0;
}