Help us understand the problem. What is going on with this article?

競プロ精進日記31日目(7/25)

感想

あげるタイミングを逃していました💦
現在(8/3)はCodeforcesのバチャやyukicoderを中心に取り組むようにし、一旦AtCoderの過去問埋めから離れています。

昨日のコンテストも大失敗しました。実力は伸びてきているはずでメンタルの問題だとは思うのですが、かなりしんどいです…。これまでは特に壁を感じたことはなかったので、今は壁にぶつかっているだけなのかもしれません。

ABC086-D Checker

かかった時間

20分考えて分からず、解説AC

間違えた原因

解いたことのない問題で曖昧な方針しか思い浮かびませんでした。
今後、そのような問題が増えてくるので、対応力をつけたいです。
先日のyukicoderのC問題で類題をコンテスト中に解き切ることができうれしかったです。

考察

まず、どの盤面でも必ず同じ色となるマスが存在します。天下りではありますが、$x$座標と$y$座標を$2K$で割った余りがいずれも等しいようなマスです。したがって、全てのマスは$2K \times 2K$のマス目の中で表現することができます。また、そのマスの中で、$x$座標のみが$K$以上離れているマス及び$y$座標のみが$K$以上離れているマスは反対の情報を持ちます。つまり、($x$,$y$)が黒で($x$,$y+K$)が白という情報は同じ意味を持ちます。したがって、$K \times K$のマス内で希望は全て表現することができます。

したがって、この盤面での希望をまとめると以下のようになります。ただし、$l=0$は黒色で$l=1$は白色を表し、$i,j$は$0 \leqq i,j <K$を満たします。

$g[i][j][l]:=$($x$座標が$i$で$y$座標が$j$のマスに帰着できるマスについて$l$に相当する色を希望するマスがいくつあるか)

この盤面においてありうる市松模様のパターンを考えますが、このようなパターンは市松模様の左上のマスがどこであるかそのマスが白色or黒色で合計$2 \times K \times K$通りあります。左上の座標が$(i,j)$であると仮定すれば下図のようになります

IMG_0510.jpg

IMG_0511.jpg

ここで、それぞれの長方形内での希望をまとめる必要がありますが、これは二次元累積和を求めておけば$O(1)$で求めることができます。

また、二次元累積和は以下のように定義して求めました。実装はけんちょんさんの記事を参照しました。

$ac[l][x][y] := [0, x) × [0, y)$ の長方形区間の$l$に相当する色の希望の数

$ac[l][i+1][j+1]=ac[l][i][j+1]+ac[l][i+1][j]-ac[l][i][j]+g[i][j][l]$

ここでは右下の長方形と左上の長方形が白色で右上の長方形と左下の長方形が黒色になるとします(逆の場合も同様に考えられます。)。この時、白色の部分は$①-②-③+2\times ④$であり、黒色の部分は$②+③-2\times ④$となります。

したがって、二次元累積和を半開区間で求めることにのみ気を付ければ、叶えられる希望の数を求められます。よって、ありうる叶えられる希望の数の中で最大の数を出力して答えになります。
  

Pythonのコード
abc086d.py
n,k=map(int,input().split())
g=[[[0,0] for i in range(k)] for j in range(k)]

for i in range(n):
    x,y,c=input().split()
    x,y=int(x),int(y)
    if y%(2*k)<k and x%(2*k)<k:
        g[y%(2*k)][x%(2*k)][c=="W"]+=1
    elif y%(2*k)<k:
        g[y%(2*k)][x%(2*k)-k][c=="B"]+=1
    elif x%(2*k)<k:
        g[y%(2*k)-k][x%(2*k)][c=="B"]+=1
    else:
        g[y%(2*k)-k][x%(2*k)-k][c=="W"]+=1

ac=[[[0]*(k+1) for i in range(k+1)] for l in range(2)]
for l in range(2):
    for i in range(k):
        for j in range(k):
            ac[l][i+1][j+1]=ac[l][i][j+1]+ac[l][i+1][j]-ac[l][i][j]+g[i][j][l]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ac[0][k][k]-ac[0][i][k]-ac[0][k][j]+2*ac[0][i][j]+ac[1][i][k]+ac[1][k][j]-2*ac[1][i][j],ans)
        ans=max(ac[1][k][k]-ac[1][i][k]-ac[1][k][j]+2*ac[1][i][j]+ac[0][i][k]+ac[0][k][j]-2*ac[0][i][j],ans)
print(ans)

DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away