SRM560 Div1 Medium(500) DrawingPointsDivOne

TopCoder

DrawingPointsDivOne

問題文では古い点が幅1の正方形になっていると中央に新しい点を描くと言っているけど、中央ではなく左下の点と考えると、扱いが楽になる。

WojtekがSステップ処理を行うことができるかどうかは、Sステップ戻してからSステップ進めて、余計な点が無いかを調べれば良い。また、Sステップが可能ならSステップ未満は可能だし、SステップがダメならSステップ超過はダメ。二分探索で高速化する。

#include <vector>
using namespace std;

bool check( vector<int> &X, vector<int> &Y, int step )
{
    const int H = 512;
    const int W = 512;

    static char B[H][W];
    static char C[H][W];

    for ( int y=0; y<H; y++ )
    for ( int x=0; x<W; x++ )
        B[y][x] = C[y][x] = false;

    for ( int i=0; i<(int)X.size(); i++ )
        B[Y[i]+128][X[i]+128] = true,
        C[Y[i]+128][X[i]+128] = true;

    for ( int s=0; s<step; s++ )
        for ( int y=H-1; y>0; y-- )
        for ( int x=W-1; x>0; x-- )
            B[y][x] = B[y][x] || B[y][x-1] || B[y-1][x] || B[y-1][x-1];

    for ( int s=0; s<step; s++ )
        for ( int y=0; y<H-1; y++ )
        for ( int x=0; x<W-1; x++ )
            B[y][x] = B[y][x] && B[y][x+1] && B[y+1][x] && B[y+1][x+1];

    for ( int y=0; y<H; y++ )
    for ( int x=0; x<W; x++ )
        if ( B[y][x] != C[y][x] )
            return false;

    return true;
}

class DrawingPointsDivOne{public:
int maxSteps( vector <int> x, vector <int> y )
{
    int ans = 0;
    for ( int b=128; b>0; b/=2 )
        if ( check(x,y,ans+b) )
            ans += b;

    return ans<255 ? ans : -1;
}};