結果

問題 No.883 ぬりえ
ユーザー NoneNone
提出日時 2021-03-06 19:43:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,227 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 71,808 KB
最終ジャッジ日時 2024-04-17 07:07:59
合計ジャッジ時間 2,357 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,480 KB
testcase_01 AC 43 ms
52,864 KB
testcase_02 AC 43 ms
52,736 KB
testcase_03 AC 39 ms
52,480 KB
testcase_04 AC 38 ms
52,608 KB
testcase_05 AC 38 ms
52,736 KB
testcase_06 AC 39 ms
52,608 KB
testcase_07 WA -
testcase_08 AC 38 ms
52,864 KB
testcase_09 WA -
testcase_10 AC 38 ms
52,864 KB
testcase_11 AC 44 ms
52,992 KB
testcase_12 AC 43 ms
53,248 KB
testcase_13 AC 40 ms
53,120 KB
testcase_14 AC 63 ms
63,872 KB
testcase_15 AC 73 ms
71,808 KB
testcase_16 AC 55 ms
63,616 KB
testcase_17 AC 50 ms
61,568 KB
testcase_18 AC 49 ms
62,208 KB
testcase_19 AC 53 ms
61,696 KB
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=True,single=False)
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]))
0