Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-30

[][][] TopCoder Single Round Match 501 Div1 04:32 はてなブックマーク -  TopCoder Single Round Match 501 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:23:06.293Challenge Succeeded0.00
5000:43:32.380Opened0.00
1000--0.00
Challenge..0.00

部屋(Room 10) 14位,全体 487位

Rating : 1494 → 1396 (-98)

前回うまくいったのに調子をのったせいか,足下をすくわれました。

250 FoxPlayingGame

問題文

 (要ログイン)TopCoder Statistics - Problem Statement

要約

 初期値 0 点からゲームを行う。ゲーム中行動 A を nA 回行い,行動 B を nB 回行う。A, B を行う順序は自由に決めて良い。行動 A を行うと,今の持ち点が pA/1000.0 点増え,行動 B を行うと持ち点が pB/1000.0 倍される。ゲーム終了時に得られる点数の最大値を求めよ。nA, nBは 0 以上 50 以下,pA は -10000 以上 10000 以下,pB は -2000 以上 2000 以下。

方針

 きちんと自分で計算式を立てて答えを求めようとすると,場合分けが大変になる。

  pA が正か負かと pB の絶対値が 1000 以上か以下かで場合分けにより,大雑把には「連続 A → 連続 B」か「連続 B → 連続 A 」かが決まることが,サンプル例を見るとわかる。しかしこれだけだと不十分で,例えば B で「連続 A → 連続 B」行った結果,答えが負になった場合,B を 1 回前倒しして「B → 連続 A → 連続 B」とすれば答えを正に出来る。このような調節は,必要かどうかは nB の偶奇に,出来るかどうかは nB が 1 以上かによる。

 

コード例(c++,コンテスト外)
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

class FoxPlayingGame {
public:
  double theMax(int na, int nb, int pa, int pb) {
    double ans = 0;
    if(pb > 1000 || pb < -1000){
      if(pa >= 0){
	ans+= pa * na/(double) 1000;
	if(pb > 0) 
	  for(int i = 0;i<nb;i++){
	    ans *= pb/(double)1000;
	  }
	else
	  for(int i = 0;i<(nb/2)*2;i++){
	    ans *= pb/(double)1000;
	  }
	return ans;
      }else{
	if(pb > 0){
	  return pa * na/(double) 1000;
	}else{
	  if(nb == 0)
	    return  pa * na / (double) 1000;
	  ans+= pa * na / (double) 1000;
	  if(nb % 2 ==0) nb--;
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	  return ans;
	}
      }
    }else{
      if(pa >= 0){
	return  pa * na / (double) 1000;	
      }else{
	if(nb == 0)
	  return  pa * na / (double) 1000;	
	ans += pa * na / (double) 1000;	
	if(pb > 0){
	  for(int i = 0;i<nb;i++){
	    ans *= pb / (double)1000;
	  }
	  return ans;
	}else if(pb == 0){
	  return 0;
	}else 
	  return pb * ans / (double)1000;
      }
    }
  }
};

下のコードは実際に自分が提出して Challenge されたものです。Challengeの練習にどうぞ。実際のケースはここに記載されています:TopCoder | Login

(このコードは正しくありません)
// Challenged Case
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>
 
using namespace std;
 
class FoxPlayingGame {
  typedef long long ll;
public:
  double theMax(int na, int nb, int pa, int pb) {
    double ans = 0;
    if(pb > 1000 || pb < -1000){
      if(pa >= 0){
        ans+= pa * na / (double) 1000;
        if(pb > 0)
          for(int i = 0; i < nb; i++){
            ans *= pb / (double)1000;
          }
	else
	  for(int i = 0; i < (nb/2)*2; i++){
	    ans *= pb / (double)1000;
	  }
	return ans;
      }else{
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0;i<nb;i++){
	    ans *= pb / (double)1000;
	  }
	ans+= pa * na / (double) 1000;
	return ans;
      }
    }else{
      if(pa >= 0){
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	ans += pa * na / (double) 1000;  
	return ans;
      }else{
	ans += pa * na / (double) 1000;  
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0; i < ((nb-1)/2) * 2 + 1;i++){
	    ans *= pb / (double)1000;
	  }
	return ans;
      }
    }
  }
};

500 FoxAverageSequence

問題文

 (要ログイン)TopCoder Statistics - Problem Statement

要約

 数列 A (0-indexed,長さは有限) が次の条件を満たす時,beautiful sequence という。

  • 各々の値は 0 以上 40 以下
  • A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.(各値はそれ以前の数の算術平均以下)
  • A[i] > A[i+1] > A[i+2].となる i は存在しない。(2 回連続で値が下がることはない)

 数列が与えられている。その数列の値は -1 以上 40 以下である。そのうち -1 の部分を別の数字に書き換えて,beautiful sequence にする場合の数を mod 1,000,000,007 で答えよ。

方針

 長さ i の数列の個数から長さ i+1 の数列を作る DP を考える。i+1 番目の数を決めるのに必要な情報は

  • 数列の末端で値の下降は何回連続で起こったか( a[t] > a[t+1] を 1 回の値の下降と呼んでいる)
  • それまでの数の和
  • 最後の数

なので,dp[j][k][l] で,(長さが i で)j 回値が下降し,数列の和が k,最後の数字が l の数列の個数を表す事にする。

コード例(c++,コンテスト外)
nt

1000 FoxSerarchingRuins

問題文

 (要ログイン)http://www.topcoder.com/stat?c=problem_statement&pm=11286&rd=14430

要約

 まだ読んでいません

Coding Phase

 目標 Level 2 を解く事。これまでに比べ黄色や赤色の人が多い部屋に割り振られる。Level 1 パッと思いつく限りでも pB の場合分けが少なくとも 3 通り,pA の場合分けが少なくとも 2 通りある事がわかる。場合分けをきちんとやれば各々のケースは簡単に書けるはずだとコードが汚くなる事を覚悟で if then else を列挙する事に決める。自分が書き始めようとする時点でもう提出者が現れ,焦ってしまう。コーナーケース ( pB = -1000 など)の場合どうなるかと不安になるが,今回の場合気にしなくてもよかった。時間がかかったが提出,場合分けの 1 つので計算式を間違えていたがコンテスト中には気づけなかった。自作のテストケースで検証したが場合分けが多くて全ての可能性を列挙できなかったのが失敗の原因だと思う。

 Level 2 数列の数を数える問題。Project Euler で bouncy number を求める問題*1 と似ている。Codeforcesでも似たような問題を扱ったので,これは解けるのではないかと思った。DP の方法もすぐに思いつき大体の実装も比較的すんなりできた,がデバッグが間に合わなかった。

反省

デバッグについて

 Segmentation Fault などの問題とあまり関係ない所でのデバッグに時間がかかった。コード文法ミスがないかをにらめっこして時間を費やす事が多かったが,簡単なテストケースの printf でバッグの方が良かったかもしれない。周りでプログラミングが上手い人との差を見ると,コードを書く時間の差異より,デバッグする時間の差異が大きいように思う。

問題選定について

 Level 2 に注力した結果それに捕われ, Level 1 が疎かになった。

2011-03-25

[][][][] SRM473 Div1 Level2 600 TwoSidedCards 06:47 はてなブックマーク -  SRM473 Div1 Level2 600 TwoSidedCards - 練習帳

問題文

 http://www.topcoder.com/stat?c=round_overview&er=5&rd=14154

要約

 N 枚のカードが与えられている。それぞれのカードには 1 から N のうちいずれかの数字が裏表に 1 つずつ書かれている。表面合計 N 面に書かれている数字は 1 から N の相違なる数で,裏面も同様である(つまり表面の数をすべて集めると {1, ... , N} の置換)。例えば N = 4 の場合の一例は,

表 1 4 3 2
  ー ー ー ー
裏 3 2 1 4

 この N 枚のカードを適当に順序入れ替え,さらに何枚かを裏返して横一列に並べる事で,ordered N tuple を作る。作れる tuple の種類を modulo 1,000,000,007 で答えよ。

 N は 1 以上 50 以下

方針

 あるカードの裏の数とその次のカードの表の数が等しいという関係でカードを数珠つなぎにすると,カードをいくつかのグループに分ける事ができる。数珠つなぎの一例は

表 1 3 7 2 4
  ー ー ー ー ー
裏 3 7 2 4 1

のようなもの。tuple の種類の数はグループに含まれるカードの枚数にしかよらない。各々のグループで作れる tuple の種類の数をまず計算する。

 グループのカードの枚数を k 枚とする。適当な枚数裏返した結果,表面に 1 つしか現れていない数字の種類を j , 2 つ現れている数字の種類を i とすると(k = j + 2 * i),これの順序を適当に入れ替えて作れる tuple の種類は n! / 2^i 。さらに i は「裏返したカード達の連結成分の数」に等しい。例えば○は表面を向いたカード,×を裏返したカードとして,カード達が

○○××○○×○

という状態の場合,連結成分の数は××と×で 2 個と数える。また,両端同士はつながっているとみなして,

×○××○×××

の場合も連結成分は 2 個とカウントする。上の i はこの裏返したカードの連結成分の数に等しい。i 個の × - 連結成分を決めることと ○ と × の境界点を 2 * i 個決める事と同義なので,上の (i, j) を達成できる組み合わせの数は kC2*i 通り。また,全て表向きの場合を除いて,ある並べ方とそれを裏表を全部入れ替えたものは異なる tuple になるので,結局サイズが k のグループで作れる tuple の数 f(k) は

f(k) = k! + 2 * Σ_{i=1}^{k/2} (k! / 2^i) * kC2*i

 最後に,N 枚のカードが k_1, k_2, .. k_p のグループに分かれていたとすると,N 枚のカードを適当に並べかえ, k_1枚,k_2枚,... k_p枚ずつ同一視し,各々のグループで f(k_i) 通りの入れ替えを行うので,求める組み合わせの数は

N! * Πf(k_i) / Π(k_i)!

コード例(c++)

#include <string>
#include <vector>
#include <iostream>

using namespace std;
typedef long long ll;

class TwoSidedCards {
public:
  vector<int > t;
  vector<int > h;
  vector<int > used;
  int n;
  ll mod;

  // mathematical functions (modulo)
  ll comb(int n,int k){
    if(k == 0 || n == k) return 1;
    return ((comb(n-1, k-1) * n + mod )  % mod * pow(k,mod-2) + mod) % mod; 
  }
  ll fact(int n){
    if(n == 0) return 1;
    return (fact(n-1) * n + mod) % mod;
  }  
  ll pow(int a, int r){
    if(r == 0) return 1;
    ll ans = 1;
    if(r & 1){
      ans = (ans *  a + mod) % mod;
    }
    ll aa = pow(a, r/2);
    ans =  ( ( (ans * aa + mod) % mod ) * aa + mod ) % mod;
    return ans;
  }

  // make loops 
  int check(int head, int now){
    used[now] = 1;
    if(h[now] == head){
      return 1;
    }
    int next = 0;
    for(next = 0; next < n; next++){
      if(t[next] == h[now])
	break;
    }
    return 1 + check(head, next);    
  }

  // calculate f(k) (defined in the explanation above)
  ll count(int k){
    ll ans = 0;
    for(int i = 0;i<=k/2;i++){
      ans = ( ans + ( ( ( (fact(k) * pow ( pow(2, i), mod-2) )+ mod ) % mod) * comb(k, 2*i) + mod)  %mod + mod ) % mod ;
      if(i != 0){
	ans = ( ans + ( ( ( (fact(k) * pow ( pow(2, i), mod-2) )+ mod ) % mod) * comb(k, 2*i) + mod)  %mod + mod ) % mod ;
      }
    }
    return ans;
  }

  int theCount(vector <int> taro, vector <int> hanako) {
    mod = 1000000007LL;
    n = taro.size();
    used.clear();
    used.resize(n);
    t = taro;h = hanako;
    vector<int > loops;

    for(int i = 0; i < n; i++){
      if(used[i] == 1) continue;
      loops.push_back(check(taro[i], i));
    }

    ll ans = fact(n);  
    for(int i = 0; i < loops.size(); i++){
      ll a = fact(loops[i]);
      ans = ( ans * pow(a, mod-2)  + mod) % mod;
    }

    for(size_t i = 0; i < loops.size(); i++){
      ans = (ans * count(loops[i]) + mod) % mod;
    }
    return ans;
  }
};

分析

 自力では連結成分の数を境界点の数に翻訳する部分ができずにギブアップ。残りの部分は kusano_prog さんの解説を参考にしました。ありがとうございました

*1。この問題の場合剰余を取った状態で (k_i)! で割り算しなければならない。これを先日のエントリーで計算したように逆元を全探索で調べると到底時間内に終わらないので,ここでは a の Z/pZ 内での逆元は a^{p-2}である事を用いています。

するとあらゆる所で悉く mod 計算が現れました。実際剰余を取る所でサボると,いくつかのケースで落ちました。

2011-03-22

[][][][] SRM473 Div1 Level2 500 RightTriangle 03:23 はてなブックマーク -  SRM473 Div1 Level2 500 RightTriangle - 練習帳

問題文

 http://www.topcoder.com/stat?c=round_overview&er=5&rd=14155

要約

 円周上に等間隔に places 個の点が置かれ,時計回りに 0 から places-1 まで番号が振られている。整数 a, b, c が与えられていて,次のルールで points 個の点に赤いマークを付ける。N = 0,1, ... , points-1に対して

  • P(N) = (a * n * n + b * n + c) % places を計算する
  • P(N)の番号を振られた点から時計回りに点を巡り,赤くマークされていない最初の点を見つける(P(N)がマークされていなければP(N)自身を選ぶ)
  • その点に赤いマークを付ける

円に内接するの直角三角形で頂点 3 つともに赤いマークがついているものの数を答えよ。

 places は 1 以上 1000000以下,pointsは 1 以上 100000 以下でplacesより大きくはない,a, b, cは 0 以上 1000000 以下


方針

 直角三角形の数を数えるのは,ある点とその反対側の点が両方マークされているという条件で探せば O(places) でできる。問題は赤いマークを付ける部分で,問題文の方法(特にマークされていない点を見つける所)をそのまま実装してしまうと最悪 O(points^2) のアルゴリズムになってしまう。

 n を log nにしようということで 2 分探索を考える。今回の場合,条件 C(n):「 P(N) から n 個先まですべてマークされている」を考えると,C(n) が正しいならば k <= n となるすべての k に対し C(k) が正しいので,2 分探索が用いられる。ただ,P(N) から k 個先までにあるマークの数を 1 つずつ数えていると,O(points) のアルゴリズムになり,全てマークするのにやっぱり O(points^2) かかってしまう。

 そこで,Binary Index Tree を用いマークの数を管理すれば数えるのが O(log (points) ) に減り,結局合計で O(points * log^2 (points) )で間に合う。


コード例

#include <vector>
#include <cmath>

using namespace std;

class RightTriangle {
public:
  template<typename T>
  class BIT{
  private:
    /**
     * val : n
     * the number of underlying sequence
     */
    int n;
    /**
     * val : nn
     * nn is the minimum value which satisfies the following conditions
     * (1) nn is some power of 2
     * (2) n <= nn;
     */
    int nn;
    vector<T> val;
  public:
    BIT(int _n) : n(_n){
      nn = 1;
      while(n > nn) nn *= 2;    
      val.resize(nn);
      for(size_t i = 0;i<val.size();i++){
	val[i] = 0;
      }
    }
    BIT(size_t _n){BIT((int) _n);}
    BIT(){BIT(0);}

    inline size_t size(){return n;}

    /**
     * return the partial sum in [0, i) of a
     * Note that internal data is 1-indexed,
     * whereas access from outside is required to be 0-indexed
     */
    T sum(int i){
      T s = (T) 0;
      while(i > 0){
	s += val[i];
	i -= i&-i;
      }
      return s;
    }

    /**
     * add x to a[i] where a[i] is considering sequence
     * note that internal data is 1-index,
     * whereas access from outside is required to be 0-indexed
     */

    void add(int i, T x){
      i++;
      while(i <= n){
	val[i] += x;
	i += i & -i; 
      }
    }
  };

  long long triangleCount(int places, int points, int a, int b, int c) {
    long long A = a;
    long long B = b;
    
    if(places % 2 == 1) return 0;
    vector<int> isred(places, 0);
    BIT<int> bit(places);    
    for(long long  n = 0; n < points;n++){
      long long  pos = (A * n * n + B * n) % places;
      if(isred[pos] == 0 ){
	bit.add(pos, 1);
	isred[pos] = 1;
	continue;
      }
      int low = 0;
      int high = places;
      int mid = 0;
      while(high - low > 1){
	mid = (low + high) /2;
	int h = 0,l = 0;
	if(mid + pos < places){
	  h = bit.sum(mid + pos);
	  l = bit.sum(pos);
	}else{
	  h = bit.sum(pos + mid-places) + n;
	  l = bit.sum(pos);
	}
	if(h-l < mid){
	  high = mid;
	}else{
	  low = mid;
	}
      }
      bit.add((low+ pos) % places, 1);
      isred[(low + pos) % places]= 1;
    }
    long long  ans = 0;

    for(int i = 0;i<places/2;i++){
      if(isred[i] == 1 && isred[i+places/2] == 1) 
	ans+= (points-2);
    }
    return ans;
  }

提出する時にこんな警告が

Your submission may contain more than 30% unused code which would violate the Unused Code Rule. Are you sure you want to submit this code?

そんなルールがあったんだ・・・

2011-03-20

[][][] Top Coder Single Round Match 500 Div1 14:10 はてなブックマーク -  Top Coder Single Round Match 500 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:31:16.592Passed System Test138.89
5000:43:32.380Opened0.00
10000:41:14.889Challenge Succeeded0.00
Challenge..0.00

部屋 6位 (Room 43) ,全体 148位

Rating : 1260 → 1492 (+232)

 まさかの大幅アップ,自分くらいのレーティングで Easy を解けた方は同じような恩恵を受けたのだと思います。もうすぐ黄色になれる位置ですが,ここからはもっと大変そうです。 

 同じ部屋だった wrong さんが Redcoder になられたようです。おめでとうございます。

250 MafiaGame

要約

 N 人の中から相互投票で敗者 1 人を決める。投票のルールは次の通り。

  • 始め,全員が敗者の候補である
  • N 人のうち何人かは投票する相手を決めていて(その相手のリストを decision と呼ぶ),もし相手が敗者の候補の中にいたら必ずその人に投票する。まずそういう人が投票する。
  • 次に投票する人を決めているけれど相手が敗者の候補にいない人,及び投票相手を決めていない人が 1 人ずつ投票する。これらの人は自分が投票する段階で最も得票数が少ない人にランダムに投票する。
  • 最も得票数が多い人が 1 人の場合はその人が敗者。最多得票数の人が複数人いる場合は敗者の候補を最多得票者に限定して,再び最初から繰り返す。

 これを繰り返すと永遠に終わらないか,有限回で一人に決定する。まず無限ループになるか否かを判定し,無限ループにならない場合は,敗者になる確率が最も高い人のその確率を求めよ。

 N は 2 以上 500 以下。そのうち投票する相手を決めている人は 1 人以上 N 人以下

方針

 (全員の投票ではなく,)decision の中だけで最多得票数の人が 1 回目に残る。それらの人達は decision の中での得票数が同じなので,敗者になる確率はみな等しい。従って答えは無限ループか 確率 1 / (残っている人)。2 回目以降は無党派層を残っている人達に振分けて人数を絞っていく。その時,1 回の投票で人数が減らなかったら無限ループになる。逆に人数が真に減少し続けるなら最後に必ず 1 人に決定する。

コード例
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;

class MafiaGame {
public:
  double probabilityToLose(int N, vector <int> d) {
    vector<int > vote(N);
    for(int i = 0;i<d.size();i++){
      vote[d[i]]++;
    }
    int mx = 0;
    for(int i = 0;i<N;i++){
      mx = max(mx, vote[i]);
    }
    int count=0;
    for(int i = 0;i<N;i++){
      if(mx == vote[i] ) 
	count ++;
    }

    if(mx == 1 && N != 1) return 0.0;
    if(count == 1) return 1.0; 

    int res = count;
    while(1){
      int next = (N - res * mx ) % res;
      if(next == 0) return 0.0;
      if(next == 1) return 1.0/(double)count;
      res = next;
    }
  }
};

500 FractalPicture

要約

 座標平面上にケーリーグラフ(Cayley graph - Wikipedia)の 1/4 と長方形が与えられている。(ケーリーグラフは繰り返しを 500 回で止めている)。グラフの中で長方形の中に含まれている部分の長さの合計を求めよ。グラフと長方形の各辺は座標軸に平行。ケーリーグラフの大きさは固定で,根本が (0, 0),頂点が(0, 81)。長方形の左下の点はx, y 座標ともに -100 以上 100 以下の格子点で,縦横の大きさは 1 以上 100 以下の整数値。

方針

 まだ解いていません

1000 ProductAndSum

要約

 整数 S, p2, p3, p5, p7 が与えられている。各桁の和が S で,各桁の積が 2^{p2}*3^{p3}*5^{p5}*7^{p7} となる整数を考える。そのような整数達の和を modulo 500500573 で答えよ。

 p2 から p7 は 1 以上 100 以下,S は 0 以上 2500 以下。

方針

 1 から 9 を使う個数の組が決まればそれらを並べ替えて作れる整数達の和は計算できるので,まずそれを全探索する(S は 0 でないので 0 は 1 つも使えない)。5, 7 を使う個数はそれぞれ p5, p7。2, 3, 4, 6, 8, 9 を用いる個数を c[2]〜c[9] とすると,それらは

c[2] + c[4] * 2 + c[6] + c[8] * 3 = p2
c[3] + c[6] + c[9] * 2 = p3

を満たせば良い。最後に各桁の和が S になるように 1 を適当な個数付け加える。

 1 から 9 を使う個数の組 c[1]〜c[9] が決まったとして,それらから作られる整数の和を求める。例えば {2,3,4,4} の場合,可能性は

2344 
2434
2443
----
3244
3424
3442
----
4234
4243
4324
4342
4423
4432

現れる整数の個数はそれぞれの桁で同じなので,1 つの桁の和を計算してそれを11..11 倍すればよい( 1 は桁数分並ぶ)。i が現れる回数は残りの数の組み合わせ分なので,(N-1)! / c[1]! /c[2]!・・/(c[i]-1)!・・・/c[9]! 個。従って,1 つの桁の和はこれに i を掛け, i について全て足し上げたものになる。

 実はこれはさらに簡単にする事が出来る(※)。

 Σ_{i = 1}^{9} (i * (N-1)! / c[1]! /c[2]!・・・/(c[i]-1)!・・・/c[9]!)
= Σ_{i = 1}^{9} (i * (N-1)! * c[i]) / c[1]! /c[2]!・・・/c[i]!・・・/c[9]!
= (Σ_{i = 1}^{9} (i * c[i]) ) * (N-1)!  / (Π_{j=1}^{9} c[j]!)
= S * (N-1)!  / (Π_{j=1}^{9} c[j]!)

 後はこれを上で考えた可能性全てについて足し上げれば答えが求まる。

コード(c++)

 TLEを起こさないように 階乗とその逆数と11...11をメモ化しています(cafelierさんのコードを参考にしました*1)。 実際これをしなかったら TLE しました。

#include <vector>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;
typedef long long ll;
vector<ll> f(2600,-1), ones(2600,-1), f_inv(2600,-1); // memoization
int mod =500500573;

class ProductAndSum {
public:

  ll calcones(int digit){
    if(ones[digit] != -1) return ones[digit];
    ll ret = 0;
    for(int i = 0 ;i < digit;i++){
      ret = (ret * 10 +mod) % mod;
      ret  = (ret + 1 + mod) % mod;
    }
    return ones[digit] = ret;
  }

  ll powa(int a, int r){
    if(r == 0) return 1;
    ll ans = 1;
    if(r & 1 == 1)  ans *= a;
    ll aa = powa(a, r/2);
    return (((ans * aa+ mod) % mod) *aa + mod)%mod; 
  }
  
  ll fact(int n){
    if(f[n] != -1) return f[n];
    if(n == 0) return 1;
    return f[n] = (fact(n-1)*n + mod)% mod;
  }

  ll fact_inv(int n){
    if(f_inv[n] != -1) return f_inv[n];
    return f_inv[n] = powa(fact(n), mod-2);
  }

  ll check(vector<int > & ii , ll S){
    int sum = 0;
    int digit = 0;
    for(int i = 1;i<=9;i++){
      sum += ii[i] * i;
      digit += ii[i];
    }
    if(sum > S) return 0;
    ii[1] = S - sum;
    digit += ii[1];


    // NOTE : See also the redundant calculation below
    ll onedigitsum = (fact(digit-1) * S + mod)%mod;
    for(int i = 1; i<=9; i++){
      onedigitsum = (onedigitsum * fact_inv(ii[i]) + mod) %mod;
    } 
       
    ll getones = calcones(digit);
    return  (getones * onedigitsum + mod ) %mod;
  }

  int getSum(int p2, int p3, int p5, int p7, int S) {
    vector<int > ii(10);
    ll count = 0;
    ii[5] = p5;
    ii[7] = p7;
    for(ii[8] = 0; ii[8] <= p2/3; ii[8]++){ 
      for(ii[4] = 0; ii[4] * 2 + ii[8]*3 <= p2; ii[4]++){
	for(ii[9] = 0 ; ii[9] <= p3/2; ii[9]++){
	  for(ii[6] = 0; ii[6] + ii[8]* 3 + ii[4] * 2 <= p2 && ii[6] + ii[9] * 2<=p3; ii[6]++){
	    ii[2] = p2 - (ii[4] * 2 + ii[8]*3 + ii[6]);
	    ii[3] = p3 - (ii[9] * 2 + ii[6]);
	    ii[1] = 0;
	    count = (count +  check(ii,S) + mod ) %mod;
	  }
	}
      }
    }
    return (int)count;
  }
};

もし,(※)の簡約を行わなかったら,各桁の整数の和(上のコードのonedigitsum)の計算は次のようになります。

    ll onedigitsum = 0;
    for(int i = 1;i<=9;i++){
      if(ii[i] == 0) continue;
      ll factor =  (i * fact(digit-1) + mod) % mod;
      for(int j = 1; j<=9; j++){
	ll div = ii[j];
	if(i == j) div--;
	factor = (factor * powa(fact(div), mod-2) + mod) % mod;
      }
      onedigitsum = (onedigitsum + factor+ mod)%mod;
    }

コンテスト中

 Easyを解くが第一目標,Mediumを解くが第二目標。

 Easy,問題文長い・・・,それだけで心が折れそうになる。ランダムという言葉を見て期待値かと身構えるが,何かの確率の最大値を求めるだけだった。ただ,シミュレーションの問題はコーナーケースが怖い,テスト慎重にやろうと思う。プログラムを組むのと紙に書いてシミュレーションを繰り返す。decision に載っていない人の投票行動は全員が 1 票を得るのでない限りほとんど影響がないことや,1 回目と 2 回目以降で大きく分かれている事,1 回目の投票で残った人が等確率で残る事などがわかる。こういう徐々にわかっていく感覚は楽しい。

 2 回目で 1 人になるかタイブレイクが続くかが決まると思い実装する。テスト → 全く通らない。EXAMPLE 2 を見ると残る人の数は 7 → 6 → 2人 と減っているので,この考えは間違いと分かる。愚直に while 分で何回も投票を繰り返し,残り 1 人になるか,残っている人に等しく票が分配されるかで判定する。テスト時 1 人の場合をテストしてしまう。N >= 2 の条件を見落としていた。

 Medium,フラクタル図形と長方形が重なっていて,長方形の内部に含まれる部分の長さを求めよ。再帰の方はどうにかなるかもしれないけれど微妙な位置関係の場合分けで身悶えしそうな気がしたので触れないことにする。

 Hard,問題文が短い。こちらの方が希望がありそうに見えたが,全ての数の合計を答えるのではなく,場合の数を数え上げると読み違えただけだった。コンテスト中はそれに気づかず,n! / Π(各数字の個数)! を全部足しあわせればいいじゃん,ということは剰余を取った中でのcombinationの計算?ついこの前やったじゃないかと揚々と書き始める。もっともそれすらも満足に書けなかったのでどうしようもないです。

 

 Challenge Phase

 自分の Hard が開始10数秒で落とされる。ほとんど当たる可能性がないのに提出するのは 50 点を場に与えるだけだからやめよう。特に今回のように問題が難しく団子状態の中でのこの点数は余りにも大きい。

 部屋で Medium を通している人が一人いて,落ちているのではないかと思うも,全くよくわからず手が触れられなかった。 Easy を見ていると,1 回目の投票の後残った人数を,2 回目以降の投票中に書き換えて,それの逆数を答えている人がいた,落とせると確信して,テストケースを考えていたが,目の前で他の人に落とされてしまった。結局何も出来ずに Challenge 終了。Codeforces の Hack といい他人のコードを読むのが下手すぎる。

2011-03-19

[][][][] SRM474 Div1 Level2 500 TreeCount 07:14 はてなブックマーク -  SRM474 Div1 Level2 500 TreeCount - 練習帳

テーマ:試行錯誤,実験の重要性

問題(要ログイン)

 http://www.topcoder.com/stat?c=problem_statement&pm=10805&rd=14185

要約

 連結無向グラフ G = (E, V) が与えられていて,頂点に 0 から N-1 まで番号が振られている。G に含まれる木で,0 から各点の最短距離が変化しないものの数を modulo 1000000009 で答えよ。つまり数えるのは次の条件を満たす G の部分グラフ

  • G' は木
  • V' = V
  • E' ⊂ E
  • 任意の頂点 i に対し,G' と G で 0 と i の最短距離は同じ

コード(c++)

#include <string>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

typedef long long ll;

class TreesCount {
public:
  int count(vector <string> graph) {
    ll ans = 1;
    ll mod = 1000000007;
    int n = (int )graph.size();
    int dist[51][51]; // 最短距離
    int graph1 [51][51] = {}; 
    ll count[51] = {};

    // 初期化
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	if( i!= j && graph[i][j] == '0'){
	  graph1[i][j] = INT_MAX/3; // つながっていない所が 0 はいやだ!
	  dist[i][j] = INT_MAX/3;
	}else{
	  graph1[i][j] = graph[i][j] - '0';
	  dist[i][j] = graph[i][j] - '0';
	}
      }
    }

    // ワーシャル・フロイド
    for(int k = 0;k<n;k++){
      for(int i = 0;i<n;i++){
	for(int j = 0;j<n;j++){
	  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
      }
    }

    // 最短経路の種類のカウント
    for(int i = 0;i<n;i++){
      for(int j = 0;j<n;j++){
	if(i == j) continue;
	if(dist[0][i] == dist[0][j] + graph1[i][j]){
	  count[i] ++;
	}
      }
    }

    for(int i = 0;i<n;i++){
      ans = (ans * count[i]) % mod;
    }
    return (int) ans;
  }
};

分析

 サンプルケースで色々実験してみると,どうも各点ごとに最短経路の数(実際には違う)を独立に計算して,掛け算すると良さそうだと予想しました。組み合わせだから答えが大きくなる事が予想され,剰余を取る事とも compatible です。でも,最短経路の数ってどうやって数えるのだろう。思いつくのはよくある長方形の場合で「左下から右上にいく最短経路の数」を数える時,一番最後に上に進む場合の数と左に進む場合を足し算するというもの。これと同様に考えると,

(頂点 i への最短経路の数)= Σ( i の直前に通った頂点への最短経路の数)

となるのだろうか。Σを取る範囲は? i に繋がっている頂点全部を計算するのは明らかに違う。「そこを通れば最短経路になる」という条件を考えるので定式化すると

dist[0][i] == dist[0][j] + (graph1[i][j]))

となりそう。頂点の数が小さいのでワーシャルフロイドで最短距離を計算しても十分間に合う。さらに,お互いにお互いを足しあわせて無限大にならないように,最短経路の数が確定した頂点にはマークをつけてマークをついているものだけ数え上げれば良さそう。

 以上の考察のもと書いたのが下のコード。上のコードとの違いは変数 used[i] で確定した点をマーク付けしている所と,count[i] で数えているのが頂点 0 から頂点 i への最短経路の種類である点。

(このコードは正しくありません)
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>

using namespace std;
typedef long long ll;

class TreesCount {
public:
  int count(vector <string> graph) {
    ll ans = 1;
    ll mod = 1000000007;
    int n = (int )graph.size();
    int dist[51][51];
    int graph1 [51][51] = {};
    int used[51];
    ll count[51] = {}; 

    // 初期化
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	if( i!= j && graph[i][j] == '0'){
	  graph1[i][j] = INT_MAX/3;
	  dist[i][j] = INT_MAX/3;
	}else{
	  graph1[i][j] = graph[i][j] - '0';
	  dist[i][j] = graph[i][j] - '0';
	}
      }
    }
    for(int i = 0;i<n;i++){
      used[i] = -1;
    }

    // ワーシャル・フロイド
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++){
	  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
      }
    }

    count[0] = 1;
    used[0] = 1;
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
	if(used[i] == 1 ) continue;
	bool flag = true;
	for(int j = 0; j < n; j++){
	  if(i == j) continue;
	  if(used[j] == -1 && dist[0][i] == dist[0][j] +( graph1[i][j])){
	    flag = false;
	  }
	}
	if(flag){
	  for(int j = 0;j<n;j++){
	    if(used[j] == 1 && dist[0][i] == dist[0][j] +( graph1[i][j])){
	      count[i] += count[j];
	    }
	  }
	  used[i] = 1;
	}
      }
    }
    for(int i = 0; i < n; i++){
      ans = (ans * count[i]) % mod;
    }
    return (int) ans;
  }
};

 ケースを試してみると,答えとあわない・・・。EXAMPLE 3を見ると,頂点 2 への最短経路の種類は 4 種類だけど,ここは 3 であってほしい。ということは最短経路の種類ではなく,最短経路として最後に通る頂点の数の方が正しそう。つまり,

count[i] += count[j]; →  count[i] ++;

 こう書き換えて提出した所,それであっていました。そうすると,変数 count[i] 達がお互いにお互いを足しあわせるという状態にならないので,マークをつける必要がなくなりました。それを修正したのが上のコードです。試行錯誤って重要なんだなと感じた 1 題でした