AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典:
DISCO presents ディスカバリーチャンネルコードコンテスト2020予選 C – Strawberry Cakes
ケーキを(イチゴの数だけ)公平に分割する問題。絵に描いて分割の方法を考えるのは比較的簡単だが、それを如何にコードに落とし込めるものにするかが問われる問題……みたいな感じ。
def main():
H, W, K = map(int, input().split())
field = [input() for _ in range(H)]
result = [[] for _ in range(H)]
no_sb = []
piece = 1
for y, raw in enumerate(field):
if '#' not in raw:
no_sb.append(y)
continue
sb_pos = []
for x, c in enumerate(raw):
if c == '#':
sb_pos.append(x)
now = 0
for pos in sb_pos[:-1]:
for i in range(now, pos+1):
result[y].append(piece)
piece += 1
now = pos + 1
for i in range(now, W):
result[y].append(piece)
piece += 1
for y in no_sb:
if y != 0:
result[y] = result[y-1]
for y in no_sb[::-1]:
if y != H - 1:
result[y] = result[y+1]
for r in result:
print(*r)
main()
関連