結果

問題 No.883 ぬりえ
コンテスト
ユーザー None
提出日時 2021-03-06 20:00:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 4,601 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 72,320 KB
最終ジャッジ日時 2024-10-08 21:24:37
合計ジャッジ時間 2,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def max_cost(smaller=True, single=True, negative=False):
    """
    :param smaller:  False = (重さ = W)の時の最大価値
                     True  = (重さ =< W)の時の最大価値
    :param single:   False = 重複あり
    :param negative: True = 負の価値の物が混入している

    dp[weight (=<W)] = 重さを固定した時の最大価値
    """
    N=len(weight_list)

    if negative==True:
        dp_min=-float("inf")
    else:
        dp_min = 0 # 総和価値の最小値
    dp = [dp_min] * (W+1)
    dp[0] = 0  # 重さ 0 の時は価値 0
    parent = [(-1,-1)]*(W+1)

    for item in range(N):
        if single:
            S = range(weight_list[item], W+1)[::-1]
        else:
            S = range(weight_list[item], W+1)
        for weight in S:
            if weight==weight_list[item]:
                if dp[weight]<cost_list[item]:
                    dp[weight]=cost_list[item]
                    parent[weight]=(0,item)
            elif dp[weight - weight_list[item]]!=dp_min:
                if dp[weight]<dp[weight - weight_list[item]] + cost_list[item]:
                    dp[weight]=dp[weight - weight_list[item]] + cost_list[item]
                    parent[weight]=(weight-weight_list[item],item)
    if smaller==False:
        return dp[W], path_restoring(parent,W)
    else:
        res=-float("inf")
        w0=-1
        for w in range(W+1):
            if res<dp[w]:
                res=dp[w]
                w0=w
        return res,path_restoring(parent,w0)

def min_cost(larger=True, single=True, INF=float("inf")):
    """
    :param larger: False = (重さ = W)の時の最小価値
                   True  = (重さ >= W)の時の最小価値
    :param single: False = 重複あり

    dp[weight (<=W)] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値

    path_restoring = [(weight,cost), (weight,cost),...] = 最適コストを実現する組み合わせ
    """
    N=len(weight_list)

    dp_max = INF   # 総和価値の最大値
    dp = [dp_max] * (W+2)
    dp[0] = 0               # 重さ 0 の時は価値 0
    parent = [(-1,-1)]*(W+2)

    for item in range(N):
        if single:
            S = range(W+2)[::-1]
        else:
            S = range(W+2)
        for weight in S:
            if dp[min(weight + weight_list[item], W+1)] > dp[weight] + cost_list[item]:
                dp[min(weight+weight_list[item],W+1)]=dp[weight] + cost_list[item]
                parent[min(weight+weight_list[item],W+1)]=(weight,item)

    if larger:
        if dp[W]<dp[W+1]:
            return dp[W], path_restoring(parent,W)
        else:
            return dp[W+1], path_restoring(parent,W+1)
    else:
        return dp[W], path_restoring(parent,W)

def path_restoring(parent,W):
    """
    [(weight,cost), (weight,cost),...] = 重さが丁度 W となる最適コストを実現する組み合わせ
    """
    w=W
    w0,item=parent[w]
    res=[]
    while w0!=-1:
        res.append((weight_list[item],cost_list[item]))
        w=w0
        w0,item=parent[w]
    return res
##########################################################
def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y
##########################################################
def example():
    global input
    example = iter(
        """
5 11
2 9
5 4
7 2
9 4
6 10
        """
            .strip().split("\n"))
    input = lambda: next(example)
##########################################################
import sys
from bisect import *
input = sys.stdin.readline

# example()


N, K = map(int, input().split())  # N: 品物の種類 W: 重量制限

cost_list = []
weight_list = []
for k in range(1,K+1):
    """ cost と weight が逆転して入力されている場合有り """
    weight, cost = k**2, k
    cost_list.append(cost)
    weight_list.append(weight)

W=N
cost,path=min_cost(larger=True,single=False)
if cost<=(N-1)//K+1 or N<=K**2:
    res=[["."]*cost for _ in range(cost)]
    k0=0
    cnt=0
    for _,k in path:
        for h in range(k0,k0+k):
            for w in range(k0,k0+k):
                if cnt>=N: continue
                res[h][w]="#"
                cnt+=1
        k0+=k
    print(cost)
    for h in range(cost):
        print("".join(res[h]))
else:
    cost=(N-1)//K+1
    res=[["."]*cost for _ in range(cost)]
    cnt=0
    for h in range(cost):
        for w in range(h,h+K):
            if cnt>=N: continue
            res[h][w%cost]="#"
            cnt+=1
    print(cost)
    for h in range(cost):
        print("".join(res[h]))
0