blue_jamのTopCoder日記

SRM495 Div1 Easy

SRM, Practice | 00:35

概要

275点問題．

1からNまでの数を素数は赤，それ以外は青で塗ったカードがある．カードの部分集合を取り出し昇順に並べる．

色の並びだけで，数値を特定できるところはその数に，それ以外のところは-1を出力．

解法

DPだよDP．

dp[i][j]:=カードのi番目から数値j以上の数字のうち，文字列に適合する数値の数

もし，jがカードに適合しないカードであれば，

dp[i][j] = dp[i][j+1]　…(1)

カードが適合するならば，メソッドを再帰的に呼び出し，結果が1以上であれば，

dp[i][j] = dp[i+1][j+1] + dp[i][j+1]…(2)

結果が0であれば，(1)と同じ．

適合するカードは保存しておく（上書きしてもいい）

dp[i][1]が1なら，保存しておいた数値を返し，それ以外なら-1を返す．

class ColorfulCards {
public:
    bool isPrime[1001];
    int dp[50][1001];
    void init(){
        memset(dp, -1, sizeof(dp));

        isPrime[0] = isPrime[1] = false;
        for(int i=2;i<=1000;++i){
            bool flag = true;
            for(int j=2;j*j<=i;++j){
                flag = flag && i % j != 0;
            }
            isPrime[i] = flag;
        }
    }
    int recur(int idx, int next, int N, string &colors, vector<int> &res){
        int num = 0;
        if(idx == colors.size()) return true;
        if(next > N) return false;
        if(dp[idx][next] != -1){
            return dp[idx][next];
        }
        if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){
            if(recur(idx + 1, next + 1, N, colors, res)){
                res[idx] = res[idx] == 0 ? next : -1;
                num = 1;
            }
        }
        num = num + recur(idx, next + 1, N, colors, res);
        dp[idx][next] = num;
        return num;
    }
    vector <int> theCards(int N, string colors) {
        vector <int> res(colors.size(), 0);
        init();
        recur(0, 1, N, colors, res);
        return res;
    }
};

実は解説書く直前に今回書いた解法を思いついた．

その前は，2次元のvectorとlower_bound使ってDPの代わりやってた．

class ColorfulCards {
public:
    bool isPrime[1001];
    bool checked[50][1001];
    vector<vector<int> > dp;
    void init(){
        memset(checked, 0, sizeof(checked));

        isPrime[0] = isPrime[1] = false;
        for(int i=2;i<=1000;++i){
            bool flag = true;
            for(int j=2;j*j<=i;++j){
                flag = flag && i % j != 0;
            }
            isPrime[i] = flag;
        }
    }
    bool recur(int idx, int next, int N, string &colors){
        bool res;
        if(idx == colors.size()) return true;
        if(next > N) return false;
        if(checked[idx][next]){
            return lower_bound(dp[idx].begin(), dp[idx].end(), next) != dp[idx].end();
        }
        checked[idx][next] = true;
        res = false;
        if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){
            res = recur(idx + 1, next + 1, N, colors);
            if(res) dp[idx].push_back(next);
        }
        bool tmp = recur(idx, next + 1, N, colors);
        res = res || tmp;
        return res;
    }
    vector <int> theCards(int N, string colors) {
        vector <int> res;
        init();
        dp.clear();
        dp.resize(N);
        recur(0, 1, N, colors);
        for(int i=0;i<colors.size();++i){
            if(dp[i].size() == 1){
                res.push_back(dp[i][0]);
            }
            else{
                res.push_back(-1);
            }
        }
        return res;
    }
};

SRM497 DIV1 Easy

SRM, Practice | 22:17

概要

N-1個の要素からなる数列の増減情報が与えられる．この増減情報に合致する辞書順で最小の順列を求める．

解法

いくら限定できる情報があっても50個は多すぎるだろうということで，特殊な生成方法を模索．

辞書順最小とあるので，増加するときは単純に今まで使用した要素の中で最も大きい数より1大きい数を追加すればいいだろう．

減少するときは，前の連続して減少している間その要素に1を加え，現在最後尾になっている要素に1を引いた数を追加する．

class PermutationSignature {
public:
    vector <int> reconstruct(string signature) {
        vector <int> res;
        int n = signature.size() + 1;
        int p = 1;
        res.push_back(1);
        for(int i=0;i<n-1;++i){
            ++p;
            if(signature[i] == 'D'){
                for(int j=i;j>=0;--j){
                    res[j] = res[j] + 1;
                    if(res[j] == p) break;
                }
                res.push_back(res[i]-1);
            }
            else if(signature[i] == 'I'){
                res.push_back(p);
            }
        }
        return res;
    }
};

反省

なんか頭が固くなった気がする．解法を思いつくのに時間がかかったし，思いついてから実装するのに時間がかかった．

事前に解法を詰める癖をつけるべきか．

SRM500 Div1 Easy 練習

SRM, Practice | 18:12

概要

N人のゲーム参加者からゲームから脱落させる人を1人選びます．

何人かは脱落させたい人がいて，その情報はdecisionsに保存されている．

人を選ぶ方法は以下の通り．

1. 脱落させたい人がいる参加者は，脱落させたい人に投票する．（すでに脱落させる候補にいない場合は下の方法に従う）
2. 脱落させたい人がいない参加者は，投票する時点で最も投票数が少ない参加者に投票する．
3. もっとも得票数が多かった人たちのみを脱落候補に残す．
4. これを繰り返して，1人に決まるまで行う．

もっとも高確率で当選する人の確立を求める．

何回やっても決定しない場合は0.0を返す．

解法

decisionsの出現頻度がもっとも高い人（達）は，1回目に必ず当選する．（1回目では脱落候補の人数=投票する人数であることに注意）

2回目以降は，できるだけ均等に割り振られながら投票される．

よって，Nを脱落候補の人数で割った余りが次の脱落候補に加わる．

Nを脱落候補の人数で割った余りが0なら，無限ループ．

Nを脱落候補の人数で割った余りが1なら，その時点で終了．

その確率は，1回目の投票が終わった時点の脱落候補者分の1．(脱落候補者の中から1人選ぶときの確立．コンビネーションとか使って計算しても同じ結果になるはず．楽な方を選ぼう．）

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <functional>
using namespace std;

class MafiaGame {
public:
    double probabilityToLose(int N, vector <int> decisions) {
        double res;
        int firstNum = 0;
        int cnt = 0;
        int M = N;
        
        sort(decisions.begin(), decisions.end());
        for(vector<int>::iterator i=decisions.begin();i!=decisions.end();){
            vector<int>::iterator next = upper_bound(decisions.begin(), decisions.end(), *i);
            if(firstNum < next - i){
                firstNum = next - i;
                cnt = 1;
            }
            else if(firstNum == next - i){
                ++cnt;
            }
            i = next;
        }
        if(firstNum == 1){
            cnt = N;
        }
        res = 1.0 / cnt;
        M = cnt;
        for(;;){
            if(M == 1){
                return res;
            }
            else if(M == 0){
                return 0.0;
            }
            M = N % M;
        }
    }
};