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

こんばんは。SRMのもろもろがもうつらいので、現実逃避で記事を書きます。

今日はPCKの対策として過去問を解きました。
解いた問題は3問です。

ひとつひとつざっくりと説明していこうかと...

includeとか

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<numeric>
using namespace std;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
#define INF 1e+8
#define EPS 1e-7
#define PB push_back
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
typedef pair<int,int> Pii;
typedef vector<int> vi;

1問目 Stray Twins

二人のx,y座標を持っておいてbfsしたらおｋ。
はじめ、一方がある座標に動けない時はもう一方も動けないと思っていたら、そうではなかったらしい。

コード

class data{
    public:
    int ay;
    int ax;
    int by;
    int bx;
    int cnt;
    data(){}
    data(int _ay,int _ax,int _by,int _bx,int _cnt){
        ay = _ay;
        ax = _ax;
        by = _by;
        bx = _bx;
        cnt = _cnt;
    }
};
bool memo[52][52][52][52];
int main(){
    int W,H;
    while(scanf("%d%d",&W,&H),W){
        memset(memo,0,sizeof(memo));
        int ax,ay;
        int bx,by;
        int stage[52][52];
        scanf("%d%d",&ax,&ay);
        scanf("%d%d",&bx,&by);
        ax--;ay--;bx--;by--;
        rep(i,H){
            rep(j,W){
                scanf("%d",&stage[i][j]);
            }
        }
        queue < data > Q;
        Q.push(data(ay,ax,by,bx,0));
        memo[ay][ax][by][bx] = 1;
        int ans = -1;
        while(!Q.empty()){
            data d = Q.front();Q.pop();
            if(d.cnt > 99){
                break;
            }
            if(d.ax == d.bx && d.ay == d.by){
                ans = d.cnt;
                break;
            }
            rep(i,4){
                int nay,nax;
                int nby,nbx;
                nax = d.ax+dx[i];
                nay = d.ay+dy[i];
                nbx = d.bx+dx[(i+2)%4];
                nby = d.by+dy[(i+2)%4];
                if(nax < 0 || nax > W-1 || nay < 0 || nay > H-1 || stage[nay][nax]){
                    if(nbx < 0 || nbx > W-1 || nby < 0 || nby > H-1 || stage[nby][nbx])continue;
                    if(memo[d.ay][d.ax][nby][nbx]++)continue;
                    Q.push(data(d.ay,d.ax,nby,nbx,d.cnt+1));
                }
                else if(nbx < 0 || nbx > W-1 || nby < 0 || nby > H-1 || stage[nby][nbx]){
                    if(memo[nay][nax][d.by][d.bx]++)continue;
                    Q.push(data(nay,nax,d.by,d.bx,d.cnt+1));
                }
                else{
                    if(memo[nay][nax][nby][nbx]++)continue;
                    Q.push(data(nay,nax,nby,nbx,d.cnt+1));
                }
            }
        }
        if(ans == -1)puts("NA");
        else printf("%d\n",ans);
    }
    return 0;
}

まぁ実装つらいけど、中身はやるだけかな

2問目Filling Game

メモ化しなかった。
MLEとの戦いだった。
short型が多いのはそのせい。

class data{
public:
    short field[10][10];
    short cnt;
    data(){}
    data(short _field[10][10],short _cnt){
        rep(i,10){
            rep(j,10){
                field[i][j] = _field[i][j];
            }
        }
        cnt = _cnt;
    }
};
bool memo[10][10];
short chenge(char c){
    if(c == 'R')return 0;
    if(c == 'G')return 1;
    return 2;
}
bool check(short f[10][10],short W,short H){
    short comp = f[0][0];
    rep(i,H){
        rep(j,W){
            if(comp != f[i][j])return false;
        }
    }
    return true;
}
void dfs(short b,short col,short y,short x,short stage[10][10],short W,short H){
    rep(i,4){
        short ny = y+dy[i];
        short nx = x+dx[i];
        if(ny < 0 || ny > H-1 || nx < 0 || nx > W-1 || stage[ny][nx]!=b)continue;
        if(memo[ny][nx]++)continue;
        stage[ny][nx] = col;
        dfs(b,col,ny,nx,stage,W,H);
    }
    return ;
}
void copy(short stage[10][10],short bef[10][10],short W,short H){
    rep(i,H){
        rep(j,W){
            stage[i][j] = bef[i][j];
        }
    }
    return ;
}
int main(){
    int W,H;
    while(scanf("%d%d",&W,&H),W){
        short stage[10][10];
        rep(i,H){
            rep(j,W){
                char c;
                scanf(" %c",&c);
                stage[i][j] = chenge(c);
            }
        }
        queue < data > Q;
        Q.push(data(stage,0));
        short ans = -1;
        while(!Q.empty()){
            data d = Q.front();Q.pop();
            if(check(d.field,W,H)){
                ans = d.cnt;
                break;
            }
            short col1 = (d.field[0][0]+1)%3;
            short col2 = (d.field[0][0]+2)%3;
            short sub[10][10];
            copy(sub,d.field,W,H);
            memset(memo,0,sizeof(memo));
            sub[0][0] = col1;
            dfs(d.field[0][0],col1,0,0,sub,W,H);
            Q.push(data(sub,d.cnt+1));
            copy(sub,d.field,W,H);
            memset(memo,0,sizeof(memo));
            sub[0][0] = col2;
            dfs(d.field[0][0],col2,0,0,sub,W,H);
            Q.push(data(sub,d.cnt+1));
        }
        printf("%d\n",ans);
    }
    return 0;
}

これはなんかつらい。

3問目 Salary for a Plumber

ソートして足してみる。
部分和をもつと良さそう(持たないとTLEする)。

int main(){
    int n;
    while(scanf("%d",&n),n){
        vector <ll> jo;
        ll sum = 0;
        rep(i,n){
            int p;
            scanf("%d",&p);
            sum += (ll)p;
        }
        rep(i,n-1){
            ll x;
            scanf("%lld",&x);
            jo.PB(x);
        }
        ll ans = -1*INF;
        sort(jo.begin(),jo.end());
        reverse(jo.begin(),jo.end());
        jo.PB(0);
        for(int i = n-1;i > 0; i--){
            jo[i] = jo[i-1];
        }
        jo[0]=0;
        partial_sum(jo.begin(),jo.end(),jo.begin());
        rep(i,n){
            ll sub = sum;
            sub += jo[n-i-1];
            sub *= (i+1);
            ans = max(ans,sub);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

制約に符号なし32bitに収まるとか書いてあった。そんなのに気づくはずがない。

まとめ

注意力がない。
もっとちゃんとしよう。