SRM550 Div1 Medium(500) CheckerExpansion

CheckerExpansion

こんな感じ。

............
............
............
............
............
............
.....B......
....A.B.....
...B........
..A.B.......
.B...B...B..
A.B.A.B.A.B.

パスカルの三角形

............
............
............
............
............
............
.....1......
....1.5.....
...1.4.10....
..1.3.6.10...
.1.2.3.4.5..
1.1.1.1.1.1.

の奇数のところに駒がある。(x-1,y-1)と(x-2,x)のどちらか一方にのみ駒があるとき、(x,y)に駒があるので。

Wikipediaによると、nCmが奇数であることと(~n&m)==0は同値。

#include <string>
#include <vector>
using namespace std;

class CheckerExpansion{public:
vector <string> resultAfter( long long t, long long x0, long long y0, int w, int h )
{
    vector<string> R(h);

    for ( int i=0; i<h; i++ )
    for ( int j=0; j<w; j++ )
    {
        long long x = x0+j;
        long long y = y0+h-i-1;

        char c = '.';
        if ( (x+y)%2==0 )
        {
            long long n = (x+y)/2;
            long long m = y;

            if ( n<=t-1 && m<=n && (~n&m)==0 )
                c = n%2==0 ? 'A' : 'B';
        }

        R[i] += c;
    }

    return R;
}};