AtCoder Beginner Contest 004

Submission #6901243

Source codeソースコード

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

R, G, B = MAP()
N = R + G + B

# どのマーブルを使うか
def calc(cur, cnt):
    # R
    if N - cnt > G + B:
        return abs(400-cur)
    # G
    elif N - cnt > B:
        return abs(500-cur)
    # B
    else:
        return abs(600-cur)

# dp[i][j] := マーブル使用回数jの時の、位置iまでの最小操作回数
dp = list2d(1001, N+1, INF)
# 初期化:使用回数0なら移動回数も0
for i in range(1001):
    dp[i][0] = 0

for i in range(1000):
    for j in range(N+1):
        if dp[i][j] != INF:
            # マーブルを置かない場合の遷移
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j < N:
                # マーブルを置く場合の遷移
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + calc(i, j))
mn = INF
for i in range(1001):
    # N個置き終わった中での最小値を取る
    mn = min(mn, dp[i][N])
print(mn)

Submission

Task問題 D - マーブル
User nameユーザ名 Coki628
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 1511 Byte
File nameファイル名
Exec time実行時間 875 ms
Memory usageメモリ使用量 16116 KB

Test case

Set

Set name Score得点 / Max score Cases
sub1 10 / 10 sample_01_ABC.txt,test_ABC_01.txt,test_ABC_02.txt,test_ABC_03.txt,test_ABC_04.txt,test_ABC_05.txt,test_ABC_06.txt,test_ABC_07.txt,test_ABC_08.txt,test_ABC_09.txt,test_ABC_10.txt,test_ABC_11.txt,test_ABC_12.txt,test_ABC_13.txt,test_ABC_14.txt,test_ABC_15.txt,test_ABC_16.txt,test_ABC_17.txt,test_ABC_18.txt,test_ABC_19.txt,test_ABC_20.txt,test_ABC_21.txt,test_ABC_22.txt,test_ABC_23.txt,test_ABC_24.txt,test_ABC_25.txt,test_ABC_26.txt,test_ABC_27.txt,test_ABC_28.txt
sub2 30 / 30 sample_01_ABC.txt,sample_02_BC.txt,test_ABC_01.txt,test_ABC_02.txt,test_ABC_03.txt,test_ABC_04.txt,test_ABC_05.txt,test_ABC_06.txt,test_ABC_07.txt,test_ABC_08.txt,test_ABC_09.txt,test_ABC_10.txt,test_ABC_11.txt,test_ABC_12.txt,test_ABC_13.txt,test_ABC_14.txt,test_ABC_15.txt,test_ABC_16.txt,test_ABC_17.txt,test_ABC_18.txt,test_ABC_19.txt,test_ABC_20.txt,test_ABC_21.txt,test_ABC_22.txt,test_ABC_23.txt,test_ABC_24.txt,test_ABC_25.txt,test_ABC_26.txt,test_ABC_27.txt,test_ABC_28.txt,test_BC_29.txt,test_BC_30.txt,test_BC_31.txt,test_BC_32.txt,test_BC_33.txt,test_BC_34.txt,test_BC_35.txt,test_BC_36.txt,test_BC_37.txt,test_BC_38.txt,test_BC_39.txt,test_BC_40.txt,test_BC_41.txt,test_BC_42.txt,test_BC_43.txt,test_BC_44.txt,test_BC_45.txt,test_BC_46.txt,test_BC_47.txt,test_BC_48.txt,test_BC_49.txt,test_BC_50.txt,test_BC_51.txt,test_BC_52.txt,test_BC_53.txt,test_BC_54.txt,test_BC_55.txt
All 60 / 60 sample_01_ABC.txt,sample_02_BC.txt,sample_03_C.txt,test_ABC_01.txt,test_ABC_02.txt,test_ABC_03.txt,test_ABC_04.txt,test_ABC_05.txt,test_ABC_06.txt,test_ABC_07.txt,test_ABC_08.txt,test_ABC_09.txt,test_ABC_10.txt,test_ABC_11.txt,test_ABC_12.txt,test_ABC_13.txt,test_ABC_14.txt,test_ABC_15.txt,test_ABC_16.txt,test_ABC_17.txt,test_ABC_18.txt,test_ABC_19.txt,test_ABC_20.txt,test_ABC_21.txt,test_ABC_22.txt,test_ABC_23.txt,test_ABC_24.txt,test_ABC_25.txt,test_ABC_26.txt,test_ABC_27.txt,test_ABC_28.txt,test_BC_29.txt,test_BC_30.txt,test_BC_31.txt,test_BC_32.txt,test_BC_33.txt,test_BC_34.txt,test_BC_35.txt,test_BC_36.txt,test_BC_37.txt,test_BC_38.txt,test_BC_39.txt,test_BC_40.txt,test_BC_41.txt,test_BC_42.txt,test_BC_43.txt,test_BC_44.txt,test_BC_45.txt,test_BC_46.txt,test_BC_47.txt,test_BC_48.txt,test_BC_49.txt,test_BC_50.txt,test_BC_51.txt,test_BC_52.txt,test_BC_53.txt,test_BC_54.txt,test_BC_55.txt,test_C_56.txt,test_C_57.txt,test_C_58.txt,test_C_59.txt,test_C_60.txt,test_C_61.txt,test_C_62.txt,test_C_63.txt,test_C_64.txt,test_C_65.txt,test_C_66.txt,test_C_67.txt,test_C_68.txt,test_C_69.txt,test_C_70.txt,test_C_71.txt,test_C_72.txt,test_C_73.txt,test_C_74.txt,test_C_75.txt,test_C_76.txt,test_C_77.txt,test_C_78.txt,test_C_79.txt,test_C_80.txt,test_C_81.txt,test_C_82.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01_ABC.txt AC 33 ms 3316 KB
sample_02_BC.txt AC 100 ms 4324 KB
sample_03_C.txt AC 794 ms 14480 KB
test_ABC_01.txt AC 33 ms 3188 KB
test_ABC_02.txt AC 34 ms 3316 KB
test_ABC_03.txt AC 34 ms 3316 KB
test_ABC_04.txt AC 37 ms 3316 KB
test_ABC_05.txt AC 29 ms 3188 KB
test_ABC_06.txt AC 34 ms 3316 KB
test_ABC_07.txt AC 35 ms 3316 KB
test_ABC_08.txt AC 35 ms 3316 KB
test_ABC_09.txt AC 32 ms 3188 KB
test_ABC_10.txt AC 32 ms 3188 KB
test_ABC_11.txt AC 40 ms 3316 KB
test_ABC_12.txt AC 32 ms 3316 KB
test_ABC_13.txt AC 33 ms 3188 KB
test_ABC_14.txt AC 33 ms 3188 KB
test_ABC_15.txt AC 32 ms 3188 KB
test_ABC_16.txt AC 34 ms 3316 KB
test_ABC_17.txt AC 37 ms 3316 KB
test_ABC_18.txt AC 37 ms 3316 KB
test_ABC_19.txt AC 37 ms 3316 KB
test_ABC_20.txt AC 33 ms 3316 KB
test_ABC_21.txt AC 24 ms 3188 KB
test_ABC_22.txt AC 30 ms 3188 KB
test_ABC_23.txt AC 31 ms 3188 KB
test_ABC_24.txt AC 30 ms 3188 KB
test_ABC_25.txt AC 37 ms 3316 KB
test_ABC_26.txt AC 37 ms 3316 KB
test_ABC_27.txt AC 37 ms 3316 KB
test_ABC_28.txt AC 43 ms 3428 KB
test_BC_29.txt AC 71 ms 3812 KB
test_BC_30.txt AC 76 ms 3940 KB
test_BC_31.txt AC 98 ms 4196 KB
test_BC_32.txt AC 111 ms 4452 KB
test_BC_33.txt AC 139 ms 4820 KB
test_BC_34.txt AC 139 ms 4820 KB
test_BC_35.txt AC 97 ms 4084 KB
test_BC_36.txt AC 118 ms 4580 KB
test_BC_37.txt AC 109 ms 4452 KB
test_BC_38.txt AC 108 ms 4212 KB
test_BC_39.txt AC 98 ms 4196 KB
test_BC_40.txt AC 141 ms 4936 KB
test_BC_41.txt AC 133 ms 4932 KB
test_BC_42.txt AC 160 ms 5204 KB
test_BC_43.txt AC 103 ms 4324 KB
test_BC_44.txt AC 85 ms 4068 KB
test_BC_45.txt AC 92 ms 4196 KB
test_BC_46.txt AC 129 ms 4580 KB
test_BC_47.txt AC 105 ms 4324 KB
test_BC_48.txt AC 153 ms 5060 KB
test_BC_49.txt AC 140 ms 5076 KB
test_BC_50.txt AC 141 ms 4952 KB
test_BC_51.txt AC 149 ms 4824 KB
test_BC_52.txt AC 86 ms 4196 KB
test_BC_53.txt AC 83 ms 4068 KB
test_BC_54.txt AC 85 ms 3940 KB
test_BC_55.txt AC 219 ms 5700 KB
test_C_56.txt AC 426 ms 9100 KB
test_C_57.txt AC 594 ms 11144 KB
test_C_58.txt AC 684 ms 12472 KB
test_C_59.txt AC 565 ms 10792 KB
test_C_60.txt AC 357 ms 8324 KB
test_C_61.txt AC 576 ms 10316 KB
test_C_62.txt AC 511 ms 9948 KB
test_C_63.txt AC 540 ms 10948 KB
test_C_64.txt AC 468 ms 9544 KB
test_C_65.txt AC 583 ms 11172 KB
test_C_66.txt AC 539 ms 10316 KB
test_C_67.txt AC 627 ms 12928 KB
test_C_68.txt AC 404 ms 8816 KB
test_C_69.txt AC 421 ms 8560 KB
test_C_70.txt AC 475 ms 9416 KB
test_C_71.txt AC 681 ms 12788 KB
test_C_72.txt AC 869 ms 14096 KB
test_C_73.txt AC 682 ms 12084 KB
test_C_74.txt AC 761 ms 13316 KB
test_C_75.txt AC 564 ms 10780 KB
test_C_76.txt AC 729 ms 14596 KB
test_C_77.txt AC 765 ms 13192 KB
test_C_78.txt AC 712 ms 12716 KB
test_C_79.txt AC 436 ms 10464 KB
test_C_80.txt AC 442 ms 9524 KB
test_C_81.txt AC 412 ms 8536 KB
test_C_82.txt AC 875 ms 16116 KB