結果

問題 No.883 ぬりえ
ユーザー NoneNone
提出日時 2021-03-06 19:36:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,159 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 72,192 KB
最終ジャッジ日時 2024-04-17 07:03:47
合計ジャッジ時間 5,606 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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=False,single=False)
res=[["."]*cost for _ in range(cost)]
k0=0
for _,k in path:
    for h in range(k0,k0+k):
        for w in range(k0,k0+k):
            res[h][w]="#"
    k0+=k
for h in range(cost):
    print("".join(res[h]))
0