Skip to content

Instantly share code, notes, and snippets.

@nariaki3551
Last active December 18, 2016 13:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nariaki3551/3106cc20070910e598304625bd9f3404 to your computer and use it in GitHub Desktop.
Save nariaki3551/3106cc20070910e598304625bd9f3404 to your computer and use it in GitHub Desktop.
# ------------------------------------
# yukicoder
# No.459 C-VS for yukicoder
# http://yukicoder.me/problems/no/459
# 貪欲法
# ------------------------------------
# データ入力
h, w, n = map(int, input().split())
s = [0 for _ in range(w)]
for i in range(h):
for k, elm in enumerate(list(input())):
if elm == '#':
s[k] += 1
c_tmp = [int(input()) for _ in range(n)]
# パック情報
# pack_dic[pack]: dict.
pack_dic = { pack: {'left': c_tmp[pack], 'elm': [0, 0, 0], 'sum': 0} for pack in range(n)}
# 列の情報の入力
# column_list[column] = list(columnに影響するpack_number)
column_list = [list() for _ in range(w)]
for pack, left in enumerate(c_tmp):
column_list[left].append(pack)
column_list[left+1].append(pack)
column_list[left+2].append(pack)
# main(詰め込み)
for column in range(w):
sorted_temp_list = sorted(column_list[column], \
key=lambda x: (pack_dic[x]['sum'], pack_dic[x]['left']))
# 列columnについて、そのcolumnに影響するpackの中で
# 現時点でのpackの要素の合計が少ない順に#を詰める(要素が全くないpackをなくすため)
stock = s[column]
while stock != 0:
for pack in sorted_temp_list:
left = pack_dic[pack]['left']
pack_dic[pack]['elm'][column-left] += 1
pack_dic[pack]['sum'] += 1
stock -= 1
if stock == 0:
break
# パックの表示
def pack_print(_list):
left, center, right = _list
for _ in range(3):
s = str()
s += '#' if left > 0 else '.'
s += '#' if center > 0 else '.'
s += '#' if right > 0 else '.'
print(s)
left -= 1
center -= 1
right -= 1
for pack in range(n):
pack_print(pack_dic[pack]['elm'])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment