【ARC 093】D. Grid Components

Atcoder Python

問題文

2 つの整数 A,B が与えられます。

各マスが白または黒に塗られたグリッドであって以下の条件を満たすものを、出力の項で指定されたフォーマットに従って一つ出力してください。

  • グリッドの大きさを縦 h 行横 w 列としたとき、h および w はともに 100 以下である。
  • 白く塗られたマスの集合はちょうど A 個の連結成分に分かれている (連結成分という単語の定義については後の注釈を参照)。
  • 黒く塗られたマスの集合はちょうど B 個の連結成分に分かれている。

制約の項で指定される条件のもとで解は必ず一つ以上存在することが証明できます。 解が複数ある場合、どれを出力しても構いません。

注釈

2 つの白く塗られたマス c1,c2が連結であるとは、マス c1 からマス c2 へ、上下左右に隣り合うマスへの移動を繰り返して、 白く塗られたマスだけを通って移動できることを意味します。

白く塗られたマスの集合 S が連結成分であるとは、S が以下の条件を満たすことを意味します。

  • S のどの 2 つのマスも連結である。
  • S に含まれないどの白く塗られたマスと、S に含まれるどのマスも連結ではない。
  • 黒く塗られたマスについても連結成分を同様に定義します。

制約

  • 1≤A≤500
  • 1≤B≤500

考え方

下の図のように白と黒の要素で二分された領域を考えて、そこから八方が塞がれたような領域のところだけ違う色（文字）で塗る

f:id:inaba00032:20180617010203j:plain

ソースコードでは1行99文字（1行に50まで違う色を確保できる）にしているけれど、何行でも良いはずです。 色を置き換える数については、上の図でそれぞれ1つずつの連結領域があるため、A-1個(B-1個)置き換える必要があります。

ソースコード


A,B=map(int,input().split())

#文字を置き換える必要のある'#','.'それぞれのラインの数
a_line=(A-1)//50+1
b_line=(B-1)//50+1
 

#置き換えたものを連結にしないために1ラインごとに1行一つの色を塗る必要がある
print(2*a_line+2*b_line,99)



for i in range(a_line):
 #最後にこの行で50の倍数でない余りの数を塗る
 if i == a_line-1:
  print(('.#'*((A-1)%50)+'#'*(99-2*((A-1)%50))))
 #51以上の場合50個ずつ塗って次の行へ
 else:
  print(('.#'*49)+'.')
 print('#'*99)
 
#上記と同じ
for i in range(b_line):
 print('.'*99)
 if i == b_line-1:
  print(('#.'*((B-1)%50)+'.'*(99-2*((B-1)%50))))
 else:
  print(('#.'*49)+'#')