AtCoder Beginner Contest 004

Submission #6907631

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+2, INF)
# 初期化:使用回数0なら移動回数も0
for i in range(1001):
    dp[i][0] = 0

for i in range(1000):
    for j in range(N+1):
        # マーブルを置かない場合の遷移
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # マーブルを置く場合の遷移
        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ソースコード長 1435 Byte
File nameファイル名
Exec time実行時間 1339 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 35 ms 3316 KB
sample_02_BC.txt AC 97 ms 4324 KB
sample_03_C.txt AC 1064 ms 14480 KB
test_ABC_01.txt AC 35 ms 3316 KB
test_ABC_02.txt AC 35 ms 3328 KB
test_ABC_03.txt AC 36 ms 3316 KB
test_ABC_04.txt AC 38 ms 3316 KB
test_ABC_05.txt AC 30 ms 3188 KB
test_ABC_06.txt AC 36 ms 3316 KB
test_ABC_07.txt AC 36 ms 3316 KB
test_ABC_08.txt AC 36 ms 3316 KB
test_ABC_09.txt AC 33 ms 3328 KB
test_ABC_10.txt AC 32 ms 3316 KB
test_ABC_11.txt AC 41 ms 3428 KB
test_ABC_12.txt AC 34 ms 3316 KB
test_ABC_13.txt AC 33 ms 3316 KB
test_ABC_14.txt AC 35 ms 3316 KB
test_ABC_15.txt AC 33 ms 3316 KB
test_ABC_16.txt AC 35 ms 3316 KB
test_ABC_17.txt AC 37 ms 3316 KB
test_ABC_18.txt AC 36 ms 3316 KB
test_ABC_19.txt AC 37 ms 3316 KB
test_ABC_20.txt AC 34 ms 3316 KB
test_ABC_21.txt AC 26 ms 3188 KB
test_ABC_22.txt AC 31 ms 3188 KB
test_ABC_23.txt AC 33 ms 3188 KB
test_ABC_24.txt AC 31 ms 3316 KB
test_ABC_25.txt AC 37 ms 3316 KB
test_ABC_26.txt AC 38 ms 3316 KB
test_ABC_27.txt AC 38 ms 3316 KB
test_ABC_28.txt AC 44 ms 3444 KB
test_BC_29.txt AC 66 ms 3812 KB
test_BC_30.txt AC 75 ms 3956 KB
test_BC_31.txt AC 92 ms 4324 KB
test_BC_32.txt AC 108 ms 4504 KB
test_BC_33.txt AC 140 ms 4820 KB
test_BC_34.txt AC 127 ms 4920 KB
test_BC_35.txt AC 90 ms 4196 KB
test_BC_36.txt AC 115 ms 4564 KB
test_BC_37.txt AC 104 ms 4516 KB
test_BC_38.txt AC 99 ms 4324 KB
test_BC_39.txt AC 91 ms 4324 KB
test_BC_40.txt AC 133 ms 4948 KB
test_BC_41.txt AC 137 ms 4932 KB
test_BC_42.txt AC 153 ms 5332 KB
test_BC_43.txt AC 98 ms 4324 KB
test_BC_44.txt AC 82 ms 4104 KB
test_BC_45.txt AC 86 ms 4196 KB
test_BC_46.txt AC 124 ms 4580 KB
test_BC_47.txt AC 104 ms 4452 KB
test_BC_48.txt AC 147 ms 5188 KB
test_BC_49.txt AC 132 ms 5060 KB
test_BC_50.txt AC 129 ms 4932 KB
test_BC_51.txt AC 131 ms 4820 KB
test_BC_52.txt AC 79 ms 4196 KB
test_BC_53.txt AC 77 ms 4068 KB
test_BC_54.txt AC 78 ms 3940 KB
test_BC_55.txt AC 187 ms 5812 KB
test_C_56.txt AC 434 ms 9100 KB
test_C_57.txt AC 661 ms 11272 KB
test_C_58.txt AC 786 ms 12468 KB
test_C_59.txt AC 633 ms 12828 KB
test_C_60.txt AC 343 ms 8432 KB
test_C_61.txt AC 570 ms 10332 KB
test_C_62.txt AC 568 ms 9936 KB
test_C_63.txt AC 639 ms 10972 KB
test_C_64.txt AC 493 ms 9576 KB
test_C_65.txt AC 697 ms 11176 KB
test_C_66.txt AC 567 ms 10436 KB
test_C_67.txt AC 729 ms 13064 KB
test_C_68.txt AC 417 ms 8944 KB
test_C_69.txt AC 409 ms 8560 KB
test_C_70.txt AC 491 ms 9432 KB
test_C_71.txt AC 774 ms 12788 KB
test_C_72.txt AC 1011 ms 14104 KB
test_C_73.txt AC 756 ms 12008 KB
test_C_74.txt AC 836 ms 13416 KB
test_C_75.txt AC 628 ms 10892 KB
test_C_76.txt AC 910 ms 14576 KB
test_C_77.txt AC 845 ms 13212 KB
test_C_78.txt AC 854 ms 12716 KB
test_C_79.txt AC 446 ms 10484 KB
test_C_80.txt AC 463 ms 9484 KB
test_C_81.txt AC 420 ms 8552 KB
test_C_82.txt AC 1339 ms 16116 KB