始めたのが終了直前だったのでSubmitせず。Dまでは自力で行けそうだった。
https://beta.atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_c
問題
N*Nの白マスで構成されたグリッドが与えられる。
1マスを指定し、その上下左右の隣接マスを含む5マスを黒く塗る、ということを繰り返す。
同じマスが2回以上塗られてもよい。
指定回数201800以下でN*Nを黒く塗る例を答えよ。
解法
最大でN=1000でN*N/5=200000となるので、無駄は少なく重複のないよう効率的に塗らなければいけない。
指定するマスとマスの間はマンハッタン距離で3マス離すと、間が塗れる、ということに気付くと以下のような塗り方が思いつく。
..X....X....X X....X....X.. ...X....X.... .X....X....X. ....X....X... ..X....X....X
これだと端を一部塗り残す可能性があるが、残り1800マス指定する余地があるのでそれで塗ればよい。
int N; int A[1010][1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; int num=0; FOR(y,N) FOR(x,N) if((2*x+y)%5==0) { A[y][x]|=3; num++; if(y) A[y-1][x]|=1; if(x) A[y][x-1]|=1; A[y+1][x]|=1; A[y][x+1]|=1; } FOR(y,N) { FOR(x,N) { if(A[y][x]==0) A[y][x]=3, num++; if(A[y][x]==3) cout<<"X"; else cout<<"."; } cout<<endl; } }
まとめ
これは割とすんなり思いつけたね。