blue_jamのTopCoder日記

SRM 493 Div1 Easy

SRM, Practice | 21:23

概要

N個の石が1列にあって，M番目の石が白，他はすべて黒になっている．

2人のプレイヤーが交互にK個の連続した石を選んで，その順番を入れ替える．

先にL番目の位置に白い石を配置したほうが勝ち．

どちらのプレイヤーが勝つか求める．（いつまでたっても終わらない場合は引き分け）

解法

初手でLに移動させられたら，先手の勝ち．

2手目で確実にLに移動させられたら，後手の勝ち．

3手以上かかる場合は，相手と同じ動きをして，無限ループに落としこむことができるので，引き分け．

class StonesGame {
public:
    bool can(int N,int M, int K, int L){
        int num = max(L, M) - min(L, M) + 1;
        if(num % 2 != K % 2) return false;
        int t = (K - num) / 2;
        if(t < 0) return false;
        return min(M, L) - t  >= 0 && max(M, L) + t < N;
    }
    string winner(int N, int M, int K, int L) {
        bool win;
        M = M - 1; L = L - 1;
        if(can(N, M, K, L)) return "Romeo";
        win = true;
        for(int i=0;i+K<=N;++i){
            int next;
            if(i + K <= M)
                continue;
            if(M < i)
                continue;
            next = i + K - (M - i) - 1;
            win = win && can(N, next, K, L);
        }
        return win ? "Strangelet": "Draw";
    }
};

SRM492 Div1 Easy

SRM, Practice | 15:11

概要

木の高さが一直線上に並ぶようにそろえる．

主人公は時間を巻き戻せるので，木は短くすることができる．

最小でいくつの木を短くすればいいだろうか．

解法

全探索．

2本の木を順番に選んで，いくつ木を短くすればいいか調べる．

#define EPS (1e-10)
class TimeTravellingGardener {
public:
    int determineUsage(vector <int> distance, vector <int> height) {
        int n = height.size();
        int res = n - 1;
        vector<int> v;
        v.push_back(0);
        for(int i=0;i<n;++i){
            v.push_back(v[i] + distance[i]);
        }
        for(int a=0;a<n;++a){
            for(int b=0;b<n;++b){
                double t = double(height[b] - height[a]) / (v[b] - v[a]);
                double s = height[a] - t * v[a];
                int cnt = 0;
                bool flag = true;
                for(int i=0;i<n;++i){
                    if(s + t * v[i] < - EPS){
                        flag = false;
                    }
                    else if(height[i] - EPS < s + t * v[i] && s + t * v[i] < height[i] + EPS){
                    }
                    else if(height[i] + EPS > s + t * v[i]){
                        ++cnt;
                    }
                    else{
                        flag = false;
                    }
                }
                if(flag) res = min(cnt, res);
            }
        }
        return res;
    }
};

SRM494 Div1 Easy

SRM, Practice | 14:23

概要

ピクセルの情報が与えられるので，それを塗りつぶすことができる最大のブラシの大きさを求める．

解法

O(min(W,H) * (WH)^2)で全部ぬって確かめる．

O(WH)でいけない気がしなくもない．

なんかすごい時間かかった．

class Painting {
public:
    int largestBrush(vector <string> picture) {
        int w, h;
        bool checked[60][60];
        w = picture[0].size(); h = picture.size();
        for(int k=1;k<=min(w,h);++k){
            bool filled;
            memset(checked, 0, sizeof(checked));
            for(int i=0;i+k<=h;++i){
                for(int j=0;j+k<=w;++j){
                    bool flag = true;
                    for(int ti=0;ti<k;++ti){
                        for(int tj=0;tj<k;++tj){
                            if(picture[i+ti][j+tj] == 'W'){
                                flag = false;
                            }
                        }
                    }
                    if(flag){
                        for(int ti=0;ti<k;++ti){
                            for(int tj=0;tj<k;++tj){
                                checked[i+ti][j+tj] = true;
                            }
                        }
                    }
                }
            }
            filled = true;
            for(int i=0;i<h;++i){
                for(int j=0;j<w;++j){
                    if(picture[i][j] == 'B' && !checked[i][j]){
                        filled = false;
                    }
                }
            }
            if(!filled) return k - 1;
        }
        return min(h, w);
    }
};