Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-15

[][] 2011 TCO Qualifier Round 1 15:26 はてなブックマーク -  2011 TCO Qualifier Round 1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:13:44.036Passed System Test206.05
5000:27:12.828Challenge Succeeded0.00
10000:33:46.621Opened0.00
Challenge..0.00

部屋(Room 18) 13位,全体 763位

Rating : 1453 → 1420 (-33)

 3回あるQualification Roundの1回目,上位600名がRound 1に進出します.今回はDivisionの分割はなく,全員が共通の問題を解きました.問題の難易度はDiv.1とDiv.2 の中間くらいだったように思います.AdvancerになるにはEasy + Medium かEasy + Challenge2回くらいが必要でした.また,一部屋あたりの参加者の数が20人から25人に増えていました.これは参加者が増えて,Register期間内に定員に達する事が多かったので,今回だけの措置ではないと思います.

 反省点は250が余りにも遅かった事と,500での最大ケースでの検証をさぼった事でしょうか.

250 MinimumLiars

要約

 n人の人がいて,それぞれに「n人のなかに嘘つきは何人いますか」と質問する.それぞれの人は「少なくともclaim[i]人いる」と答える.i番目の人が正直者の場合,その発言は正しいが,嘘つきの場合は逆の事を言うので,「嘘つきはclaim[i]人未満」が正しい情報である.claim[i]達が与えられているので,嘘つきの人数として考えられる人数のうち最低数を答えよ.答えが存在しない場合は-1と答えよ.

 nは2以上50以下,claim[]の各要素の値は0以上100以下.

方針

 (方針1)嘘つきの人数が分かっていれば,発言された数との大小関係でその人が正直者か嘘つきかを判定できる.そこで,嘘つきの人数を0人からn人まで走査して,発言から分かる嘘つきの人数と仮定した嘘つきの人数が等しいかを調べる.計算量はO(n^{2}).

 (方針2)嘘つきの主張する数は正直者の主張する数より常に真に大きい.従ってclaimを順番に並べると小さい側に正直者,大きい側に嘘つきが並ぶ.そこで,方針1と同じように嘘つきの数を0~nで走査する.例えばclaimが,

1 2 2 2 4 5 6 7

で,嘘つきの人数が3人だと仮定した場合,4までが正直者で,5以降が嘘つき,となるが正直者が4と発言するのは不合理.

正直者と嘘つきの境界上にいる2人だけを調べればよいので,計算量は落ちて,O(n)となります.

コード例

 問題を解くには必要ない情報が多く含まれていて,文意を理解するのに少し時間がかかりました.

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

class MinimumLiars {
public:
    int getMinimum(vector <int> claim) {
        int n = claim.size();
        sort(claim.rbegin(), claim.rend());

        if(claim[0] == 0) return 0; 
 
        for(int i = 1;i<n;i++){
            if(claim[i-1] > i && claim[i] <= i) 
                return i;
        }
        if(claim[n-1] > n) return n;

        return -1;
    } 
};

500 FoxListeningToMusic

要約

 シャッフル機能付きの音楽プレーヤーを考える.プレーヤーにはn曲が収録され,それぞれの長さはlength[i]分である.曲が終わるとn曲の中からランダムに1曲が選ばれ,即座に再生される.時間Tが与えられているので,時刻0にランダムに1曲を選んだところから初めて,T+0.5分後にそれぞれの曲が再生されている確率をそれぞれ求めよ.

 nは1以上50以下,length[]の各要素の値は1以上80001以下,Tは0以上80000以下.

方針

 prob[i][t]を,開始t分後にi番目の曲が終わる確率とすると,

prob[i][ length[i] + t] += prob[k][t] / n

と,より遅い時刻の方に確率を配っていく事で,時刻の早い方から順に計算する事で帰納的にprob[][]の値が求まる.

 T + 0.5 分後にi番目の曲が流れている確率はprob[i][T]からprob[i][T+length[i を足し合わせればよい.下のコードはこの方針で計算している.ただし,このコードではprob[i][t]の計算をTで打ち切っているので,prob[i][t]を合計する範囲で,tの上限をT+length[i]に制限する必要がない.

(このコードはTLEを起こします.)
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
using namespace std;

class FoxListeningToMusic {
public:
  vector <double> getProbabilities(vector <int> l, int T) {
    int n = l.size();
    vector<vector<double > > prob(n, vector<double> (200000, 0));
    for(int i = 0; i < n ; i++){
      prob[i][l[i]] = 1/(double)n; 
    }

    for(int j = 0; j <= T; j++){
      for(int k = 0; k < n; k++){
	for(int i = 0; i < n; i++){
	  prob[i][l[i] + j] += prob[k][j] / (double) n;
	}
      }
    }

    vector<double> ret(n);

    for(int i = 0; i < n; i++){
      for(int t = T; t < 200000; t++){
	ret[i] += prob[i][t];
      }
    }
    return ret;
  }

 しかしこのコードに最大ケースを入力したところ約9秒かかった(計算量はO(n^{2}T)なので,n, Tの制限を考えるとぎりぎり間に合うように思ったのですが...なぜ駄目なのかまだ納得できていません).そこで,計算量を減らす事を考える.prob[i][t]をprob[t]として,時刻tでどれかの曲が終了する確率とする,最後にどの曲を聴いたかはその次に再生する曲の確率分布に影響しないのでこうまとめるのは妥当だと考えられます.問題は,求める答えはprob[]のどの部分を足し合わせなければならないか,上のコードでの計算方法からの類推で,

  • T < t < T + length[i].
  • T - length[i] < t < T

などが考えられるが,ここでは後者が正しい.

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <cmath>

using namespace std;

class FoxListeningToMusic {
public:
  vector <double> getProbabilities(vector <int> l, int T) {
    int n = l.size();
    vector<double > prob(160010, 0);

    prob[0] = 1;

    for(int j = 0; j <= T; j++){
      for(int i = 0; i < n; i++){
	  prob[l[i] + j] += prob[j] / (double) n;
      }
    }

    vector<double> ret(n);
    for(int i = 0; i < n; i++){
      for(int t = max(0, T - l[i] + 1); t <= T; t++){
        ret[i] += prob[t] / (double) n;
      }
    }
    return ret;
  }
};

分析

 先ほどの2つの範囲の候補で,前者の範囲を使って

(前略)
    vector<double> ret(n);
    for(int i = 0; i < n; i++){
      for(int t = T; t <= T + l[i]; t++){ // The interval of t is changed.
        ret[i] += prob[t];                      // Division-by-n is omitted. 
      }
    }
    return ret;
  }
};

のようにしても正しい答えが得られると思ったのですが,どうもうまく行かないです.もう少し考えてみようと思います.