SRM455 Div2 Hard(1000) DonutsOnTheGrid

DonutsOnTheGrid

Easyと付いているDiv1の問題のほうが簡単……かと思いきや、問題サイズが大きくなっていてO(n⁴)では終わらない。

000000
0.....
000000
0....0
000000
0....0
000000
000000 ← y
^    ^
x1   x2

左端がx1、右端がx2、下端がyのドーナツの個数は、yより上の0の連続を考えれば２個である。x1とx2の選び方がO(n²)、縦方向は、あらかじめ横方向の0の連続を調べておき、0の連続が現れればカウンタを+1、両サイドの0が途切れればカウンタを0に、とすることでO(n)で計算できる。

#include <string>
#include <vector>

using namespace std;

class DonutsOnTheGrid
{
public:
    long long calc( int H, int W, int seed, int threshold );
};

long long DonutsOnTheGrid::calc( int H, int W, int seed, int threshold )
{
    //  グリッド
    vector<string> grid( H, string(W,'0') );

    for ( int y=0; y<H; y++ )
    for ( int x=0; x<W; x++ )
        if ( ( seed = (seed*25173+13849)%65536 ) >= threshold )
            grid[y][x] = '.';

    //  [y][x1][x2]  (x1,y)-(x2,y)に0が連続しているか
    static bool zero[350][350][350];

    for ( int y=0; y<H; y++ )
    for ( int x1=0; x1<W; x1++ )
    {
        zero[y][x1][x1] = grid[y][x1]=='0';
        for ( int x2=x1+1; x2<W; x2++ )
            zero[y][x1][x2] = zero[y][x1][x2-1] && grid[y][x2]=='0';
    }

    //  ドーナツの個数
    long long num = 0;

    for ( int x1=0; x1<W; x1++ )
    for ( int x2=x1+2; x2<W; x2++ )
    {
        //  x1, x2に0が連続していて
        //  yより2行以上前にある連続0の個数
        int n = 0;  

        for ( int y=2; y<H; y++ )
        {
            if ( zero[y-2][x1][x2] )
                n++;
            if ( grid[y-1][x1] != '0'  ||  grid[y-1][x2] != '0' )
                n = 0;
            if ( zero[y][x1][x2] )
                num += n;
        }
    }

    return num;
}