結果

問題 No.3157 Nabeatsu
コンテスト
ユーザー TKTYI
提出日時 2025-05-06 18:52:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,405 bytes
コンパイル時間 586 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 623,124 KB
最終ジャッジ日時 2025-05-06 18:52:54
合計ジャッジ時間 7,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

DP = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(D + 1)]
pre = [[[(0, 0) for _ in range(3)] for _ in range(2)] for _ in range(D + 1)]
DP[0][1][0] = 0
for i in range(D):
    for j in range(2):
        for k in range(3):
            if DP[i][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[i][j][k] * 10 + l
                if DP[i + 1][_j][_k] < val:
                    DP[i + 1][_j][_k] = val
                    pre[i + 1][_j][_k] = (l, j)
    cmp = []
    for j in range(2):
        for k in range(3):
            if DP[i + 1][j][k] >= 0:
                cmp.append(DP[i + 1][j][k])
    cmp.sort()
    for j in range(2):
        for k in range(3):
            if DP[i + 1][j][k] >= 0:
                DP[i + 1][j][k] = cmp.index(DP[i + 1][j][k])

ans = []
j, k = 0, 1
for _j in range(2):
    for _k in range(1, 3):
        if DP[D][j][k] < DP[D][_j][_k]:
            j, k = _j, _k

for i in range(D - 1, -1, -1):
    l = pre[i + 1][j][k][0]
    ans.append(str(l))
    j = pre[i + 1][j][k][1]
    k = (k - l) % 3

ans.reverse()
print(''.join(ans))
0