[ARC123] C - 1, 2, 3 - Decomposition
[Q]https://atcoder.jp/contests/arc123/tasks/arc123_c
考察
・桁ごとの値を考える。
・各桁について。1,2,3で分解したときに、最小で何個、最大で何個に分解できるかを考える。
・上位桁がさっさと0になる分には問題ない。
・分解回数が、上位桁の最小回数 > 下位桁の最大回数になった場合、処理できないので桁下げをする必要がある。(10とか、41とか、72とか)
Q. 314 = 313 + 1にわけられる。
・上位の桁を早めに消化するのは問題ない。
314 - 313 = 001 // <= 上位に0が連続するのはOK
Q. 10000 = 3333 + 3333 + 3333 + 1とわけられる。
・桁ごとに、値を考える。
1 0 0 0 0
・下位に0の桁があると処理できないので、桁下げをする。
0 10 0 0 0
・上位の桁が0である分には構わないが、100の位の0はだめ。さらに下げる
0 9 9 9 10
・indexで比較する。上位桁の最小分解回数 <= 下位桁の最大分解回数であれば問題ない。
0 9 9 9 10
これは
0,3,3,3,4回で処理できるので、4つに分けられる。10241024
を考える。難しいケース。
・分解
1 0 2 4 1 0 2 4
~~~ ここNG。0が分解できないのに、1が1回の分解を必要とする。桁下げ。
0 10 2 4 1 0 2 4
~~~~ ここNG。2が2回しか分解できないのに、10が4回の分解を必要とする。桁下げ。
0 9 12 4 1 0 2 4
~~~ ここNG。1が1回しか分解できないのに、12が4回の分解が必要とする。桁下げ。
0 9 11 14 1 0 2 4
~~~~ ここNG。1が1回しか分解できないのに、14が5回の分解が必要とする。桁下げ。
0 9 11 13 11 0 2 4
~~~~ ここNG。0が分解できないのに、13が5回の分解が必要とする。桁下げ。
0 9 11 13 10 10 2 4
~~~~ ここNG。2が2回しか分解できないのに、13が5回の分解が必要とする。桁下げ。
0 9 11 13 10 9 12 4
~~~~ ここNG。4が4回しか分解できないのに、13が5回の分解が必要とする。桁下げ。
0 9 11 13 10 9 11 14 OK
最大14 = 3+3+3+3+2 で5要素が最大のため
A. 5実装
int main() {
cincout();
ll T;
string S;
cin >> T;
while (T--) {
cin >> S;
ll N = S.size();
vector<ll> A(N);
rep(i, N) A[i] = S[i] - '0';
ll ans = 0;
ll mx = 0;
for (ll i = 1; i < N; ++i) {
chmax(mx, (A[i - 1] + 2) / 3);
if (mx > A[i]) { // ターンが足りない場合は桁下げ必須
A[i - 1]--;
A[i] += 10;
i = 0; // A[i - 1]の値を変更したので、最初からやりなおし
mx = 0;
}
}
rep(i, N) chmax(ans, (A[i] + 2) / 3);
cout << ans << endl;
}
}