Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

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 といい他人のコードを読むのが下手すぎる。