結果

問題 No.3157 Nabeatsu
コンテスト
ユーザー TKTYI
提出日時 2025-05-06 19:15:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,176 ms / 2,000 ms
コード長 1,354 bytes
コンパイル時間 748 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 246,900 KB
最終ジャッジ日時 2025-05-06 19:15:38
合計ジャッジ時間 18,963 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
N = input().strip()
D = len(N)
digits = list(map(int, N))

DP = [-1 for _ in range(6 * D + 6)]
pre1 = [0 for _ in range(6 * D + 6)]
pre2 = [0 for _ in range(6 * D + 6)]
DP[3] = 0
for i in range(D):
    for j in range(2):
        for k in range(3):
            if DP[6 * i + 3 * j + k] < 0:
                continue
            for l in range(10):
                if l == 3:
                    continue
                if j and digits[i] < l:
                    break
                _j = j and (digits[i] == l)
                _k = (k + l) % 3
                val = DP[6 * i + 3 * j + k] * 10 + l
                if DP[6* i + 6 + 3 * _j + _k] < val:
                    DP[6* i + 6 + 3 * _j + _k] = val
                    pre1[6 * i + 6 + 3 * _j + _k] = l
                    pre2[6 * i + 6 + 3 * _j + _k] = j
    cmp = DP[6 * i + 6 : 6 * i + 12]
    cmp.sort()
    for j in range(6):
        if DP[6 * i + 6 + j] >= 0:
            DP[6 * i + 6 + j] = cmp.index(DP[6 * i + 6 + j])

ans = [0 for _ in range(D)]
j, k = 0, 1
for _j in range(2):
    for _k in range(1, 3):
        if DP[6 * D + 3 * j + k] < DP[6 * D + 3 * _j + _k]:
            j, k = _j, _k
for i in range(D, 0, -1):
    l = pre1[6 * i + 3 * j + k]
    j = pre2[6 * i + 3 * j + k]
    ans[i - 1] = l
    k = (k - l) % 3
print(''.join(map(str, ans)))
0