D問題：モノクロ正方形の面積は？
カテゴリ：プログラミング(Python)、アルゴリズム、Atcorder
➊ 問題概要
AtCoder 社の壁紙の模様を xy 平面上に表現すると、以下のようになります。
以下の 3種類の直線で領域が分割されている。
x = n (n は整数)
y = n (n は偶数)
x + y = n (n は偶数)
各領域は白もしくは黒で塗られている。
いずれかの直線で隣接する 2領域は異なる色で塗られている。
(0.5 , 0.5) を含む領域は黒で塗られている。
下の図は、模様の一部を表したものです
整数A,B,C,D が与えられます。
各辺がx,y 軸に平行で、左下の頂点が(A,B) にあり右上の頂点が (C,D) にあるような長方形を考えます。
この長方形の内側に存在する黒で塗られた領域の面積を求め、それを 2 倍したものを出力してください。
出力する値は整数になることが証明できます。
➋ 設問①: 入力(0,0,3,3) ⇒ 出力10
(例) 求めるのは以下の正方形で囲われた領域内の黒く塗られた領域の面積です。
これは5なので2倍した10を出力します。
上記のように縦と横でパターンが異なることが分かります。
次はy軸方向に余りが出た時（x軸は余りが出ない時）、x軸方向に余りが出た時（x軸は余りが出ない時）で場合分けして考えてみましょう。
★(0,0,4,2) の場合
ここまででy軸(余りある場合＋ない場合)、x軸(余りない場合)で面積を求められました。
残りパターンはx軸(余りある場合）を考えれば、全ての面積を計算できるはず。。
さらに3通りに分けられました。
今までの解説をコードすると以下になります。
A, B, C, D = map(int, input().split())
def f(x, y):
width = x // 4
height = y // 2
width_rem = x % 4
height_rem = y % 2
res = width * height *8
res += width *4* height_rem
# print(res)
if width_rem >= 1:
res += 3* height + 2* height_rem
if width_rem >= 2:
res += 3* height + height_rem
if width_rem == 3:
res += height
return res
print(f(C,D))
❸ 設問②: 入力(-1,-2,1,3) ⇒ 出力11
さて次は（A,B）にマイナスが含まれているのが難しいポイントとなります。
y軸は上に2ついくと同じ形になるので任意の2倍数を追加して正の整数にしてあげればよいです。
今回であればyに2を足して0にします。
x軸は4パターンなので右に4ずつ足してあげれば同じ形になります。
今回であればxに4を足して3にします。
❹ 設問③：入力(-1000000000,-1000000000,1000000000,1000000000) ⇒ 出力400...
今回、長方形が最大のケースですが、出力は64bit符号付き整数の範囲に収まります。
ちなみに10**9は10の9乗という意味になります。
x軸は4の倍数、y軸は2の倍数であれば良い(動かす前と後で面積が同じになる)ので10**9を足しちゃいます。
制約の条件を変えます。
0 ≦ A,B,C,D ≦ (10**9) * 2にすると座標でのマイナスをなくします。
全体 – (①+③) + ② = 緑の面積
anser = f(C, D) – (f(A, D) + f(C, B)) + f(A, B)
print(anser)
❺ まとめ
設問①②③全てを満たすコードは以下になります。
A, B, C, D = map(int, input().split())
A += 10**9
B += 10**9
C += 10**9
D += 10**9
def f(x, y):
width = x // 4
height = y // 2
width_rem = x % 4
height_rem = y % 2
res = width * height *8
res += width *4* height_rem
# print(res)
if width_rem >= 1:
res += 3* height + 2* height_rem
if width_rem >= 2:
res += 3* height + height_rem
if width_rem == 3:
res += height
return res
anser = f(C, D) + f(A, B) - f(A, D) - f(C, B)
print(anser)