PCKに向けての練習してみた的な(2)

こんにちは。練習してみた的なシリーズ(2)です。

今回も3問解いてみたんですけど、一つは解ききれなかったです。

includeは一緒です。

1問目　Making Sugoroku

解法としては、訪れることのできるnodeに辺を張る。
この時に、マスに指示がある場合はそれだけを張る。

その後、ワーシャルフロイドして、到達できるかを調べる。

辺を張るのがちょっとむずかしかった。

int main(){
    int ma;
    while(scanf("%d",&ma),ma){
        int n;
        int stage[256]={0};
        int D[256][256]={{0}};
        scanf("%d",&n);
        reps(i,1,n+1){
            scanf("%d",&stage[i]);
        }
        rep(i,n+1){
            reps(j,1,ma+1){
                int tmp = i+j;
                if(stage[tmp]==0)D[i][tmp] = 1;
                else if(stage[tmp]>0){
                    if(tmp+stage[tmp]>n+1)tmp = n+1;
                    else tmp += stage[tmp];
                    D[i][tmp] = 1;
                }
                else{
                    if(tmp+stage[tmp]<0)tmp = 0;
                    else tmp += stage[tmp];
                    D[i][tmp] =  1;
                }
            }
        }
        rep(k,n+2){
            rep(i,n+2){
                rep(j,n+2){
                    if(D[i][k] && D[k][j]){
                        D[i][j] = 1;
                    }
                }
            }
        }
        bool flg = true;
        rep(i,n+1){
            if(D[0][i] && !D[i][n+1]){
                flg = false;
                break;
            }
        }
        flg ? puts("OK") : puts("NG");
    }
    return 0;
}

2問目Programming Contest

解法は、seg木でログを管理すると、いい感じになる。

class s_data{
    public:
    int id;
    int score;
    s_data(){}
    s_data(int _id,int _score){
        id = _id;
        score = _score;
    }
    bool operator<(const s_data &a)const{
        if(a.score == score)return id > a.id;
        return score<a.score;
    }
};
class Seg{
    public:
    int size;
    vector < s_data > dat;
    void init(int _k){
        int k = 1;
        while(k < _k)k*=2;
        dat = vector<s_data>(2*k-1,s_data(INF,0));
        size = k;
    }
    void update(s_data q){
        int index = q.id;
        index += size - 1;
        dat[index].score += q.score;
        dat[index].id = q.id;
        while(index > 0){
            index = (index-1)/2;
            dat[index] = max(dat[index*2+1],dat[index*2+2]);
        }
    }
};
s_data cam[100001];
int main(){
    int N,R,L;
    scanf("%d%d%d",&N,&R,&L);
    Seg seg;
    seg.init(N);
    rep(i,N){
        seg.update(s_data(i,0));
    }
 
    int bef = 0;
    int mid = 0;
    rep(i,R){
        int d,t,x;
        scanf("%d%d%d",&d,&t,&x);
        d--;
        seg.update(s_data(d,x));
        cam[mid].id = mid;
        cam[mid].score += (t-bef);
        mid = seg.dat[0].id;
        bef = t;
    }
    cam[mid].id = mid;
    cam[mid].score += L-bef;
    s_data ans = s_data(INF,-INF);
    rep(i,N){
        ans = max(ans,cam[i]);
    }
    printf("%d\n",ans.id+1);
    return 0;
}

classにしてたのでいろいろと便利だった。

3問目　Study Session

解法はrの値を2分探索で求めれば良いと思ったのだが、TLEしまくる。
結局解けなかった。
てか、これ以上早くすること出来ない気がするので、少し放置して気が向いたら、もう一度解いてみたい。

一応code

int score[1000001];
bool leader[1000001];
multiset <int> group;
bool check(int r,int terget,int n){
    int cnt = 0;
    int lea = 0;
    rep(i,n){
        if(leader[i]){
            lea++;
            continue;
        }
        set <int>::iterator it = group.lower_bound(score[i]);
        if(it == group.end())continue;
        if(*it-r <= score[i]){
            cnt++;
        }
    }
    int leaked = n-cnt-lea;
    return terget<leaked;
}
int main(){
    int N,Q;
    scanf("%d%d",&N,&Q);
    rep(i,N){
        scanf("%d",&score[i]);
    }
    rep(i,Q){
        char str[20];
        int x;
        scanf("%s",str);
        scanf("%d",&x);
        if(str[0] == 'A'){
            group.insert(score[x-1]);
            leader[x-1] = true;
        }
        if(str[0] == 'R'){
            set <int>::iterator it = group.find(score[x-1]);
            group.erase(it);
            leader[x-1] = false;
        }
        if(str[0] == 'C'){
 
            int l = 0;
            int r = INF;
            rep(i,31){
                int med = (l+r)/2;
                if(check(med,x,N))l = med;
                else r = med;
            }
 
            if(r == INF)puts("NA");
            else printf("%d\n",r);
        }
    }
    return 0;
}

これが一番はやい(TLEが3secでこのコードが3.7sec)

まとめ

二分探索力がない。
twitterで頭ついていないとか世界一〇〇できないといっている人達のどの人よりもなにも出来ない。