読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Yandex.Algorithm 2013 qualification round

Programming Contest

http://codeforces.com/blog/entry/7825
http://algorithm.contest.yandex.com/
http://algorithm.contest.yandex.com/contest/307/problems/

Yandexなのでロシアっぽく「наоя т」さんで参戦してます(読みはnaoya tです)

開催中(24時間)ならいつ始めても良いけれど、持ち時間は1時間40分。
カウントダウンが始まるので、問題を開いてからツイートしたりとか余裕かましててはいけない。(いけなかった)

全6問(A〜F)のうちA,Bは正解。Cは途中まで考えたけれど効率悪い方法しか書けず諦め。Dはすっ飛ばして、制限時間ギリギリにsubmitしたEがWA。Fは意味が分からなかった。

時間切れの後も自由にsubmitして練習できる仕組み。便利だけど問題流出可能…

All who have registered for the Yandex.Algorithm competition can take part in the qualification round. The 2,000 best contestants who have solved at least one problem will advance to the elimination stage.

http://codeforces.com/blog/entry/7825

て言うけどStandingsを見る限り2000人も参加してなくね?(1問もsubmitしていない人の数が入ってないからか)

というわけで、QRは多分通ってると思う

D. Infinite Sum

時間切れの後に解いた問題Dの無限級数の和、+∞にならないケースは全て有理数で表現できるのが面白かった。(こういうのProject Eulerにもあったかも=前にやった事あるかも)
S = 1/b + 2^a/b^2 + 3^a/b^3 + ...
について、無限部分が消去できるまで S - S/b を繰り返して行くと、残った項の係数が
Eulerian number http://oeis.org/A123125 になるので、Eulerian number を係数にもつbの多項式を作り、最初に繰り返したS-S/bを逆算して約分すると答えになる。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

typedef long long ll;

// Eulerian numbers
map<int,ll> Amm; // memoization
ll A(int n, int m){
  // assert(n > m);
  int k = (n << 16) | m;
  if (Amm.find(k) != Amm.end()) return Amm[k];
  ll anm = (m == 0 || m == n-1 || n <= 2)
      ? 1
      : (n-m) * A(n-1, m-1) + (m+1) * A(n-1, m);
  return Amm[k] = anm;
}

inline ll ipow(ll n, ll a) { // n^a
  ll x = 1;
  rep(i, a) x *= n;
  return x;
}

ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

void solve(int a, int b){
  double sum = 0.0;
  for (int n=1; n<10000; ++n) {
    double d = pow((double)n, (double)a) / pow((double)b, (double)n);
    if (d > 1.0e12 || d < 1.0e-9) break;
    sum += d;
  }

  if (b == 1) {
    printf("infinity\n");
    return;
  }

  vector<ll> ai(a, 0);
  rep(i,a) ai[i] = A(a,i);

  // b{1 4 1 0} / (b-1)^(a+1)
  ll denom = ipow(b-1, a+1);
  ll numer = 0;
  for (ll i=0,x=b; i<a; ++i,x*=b) {
    numer += x * ai[i];
  }
  ll g = gcd(numer, denom);
  printf("%lld/%lld\n", numer/g, denom/g);
}

main(){
  int a, b; cin >> a >> b;
  solve(a, b);
}