TopCoder SRM 712 Div1 Easy: LR

オーバーフローで死ぬつらい問題。

問題概要

原文 → TopCoder Statistics - Problem Statement

環状になっているサイズ $n$ の数列 $s, t$ がある (0-indexed)。 $i$ 番目の要素に対して左隣は要素 $i-1$ であり、右隣は要素 $i+1$ である。 (ただし、 $(n-1)$ 番目の要素の右隣は要素 $0$ である。)

数列に対して、以下の 2 種類の操作が可能である。

L: すべての要素に対して、その左隣の要素の値だけ加算する。
R: すべての要素に対して、その右隣の要素の値だけ加算する。

$s$ に対してこの 2 種類の操作を合計 100 回まで行って、数列 $s$ を数列 $t$ にすることができれば、その操作手順を出力せよ。できないならば、No solution を出力せよ。

解説

操作を見ればわかるように、各要素に対して加算の操作しかできないため s[i] > t[i] となるような要素が一つでもあればその時点で不可能です。また、最初から $s$ と $t$ が一致していれば操作する必要がありません。このチェックは最初にすべきでしょう。

今回の場合、総和を比較することによって操作回数を知ることができます。数列 $s$ の総和を $S$ として、簡単に説明します。

どちらの操作においても、操作後には現時点での数列の総和ぶん増えます。これは各要素で隣にあるものを足しているので、各要素が 1 度ずつ加算されているということからわかりますね。ですので、操作をするごとに数列の総和は $S \rightarrow 2S \rightarrow 4S \rightarrow 8S \dots$ のように増えていくことになります。( $t$ の総和 $-$ $s$ の総和) に対してこの性質を利用して計算していけば、操作回数が特定できます。

また、L と R の並び順は関係ない こともわかります。これは L -> R と R -> L の結果が等しいことを利用すれば示せます。したがって、LL…L RR…R のような操作手順に帰着できるため、L と R の個数さえ分かれば良いことになります。

答えを導く方法の一つとして DP があります。 dp[i][j][k] := R を i 回、L を j 回行った時の k 番目の要素の値 となるような配列を作ります。この遷移は R を行うか L を行うかしかないので、その 2 つを書けば良いです。

ソースコード

ll dp[110][110][60];
class LR {
    public:
    string construct(vector<long long> s, vector<long long> t) {
        int n = (int)s.size();
        rep(i,0,n) if(s[i] > t[i]) return "No solution";
        if(s == t) return "";

        ll ssum = accumulate(s.begin(), s.end(), (ll)0);
        ll tsum = accumulate(t.begin(), t.end(), (ll)0);
        if(ssum == 0 || (tsum - ssum) % ssum) return "No solution";
        ll diff = (tsum - ssum) / ssum;
        ll turn = 1, d = 1;
        while(1) {
            if(diff - d < 0) return "No solution";
            if(diff - d == 0) break;
            diff -= d;
            d *= 2; turn++;
        }

        memset(dp, 0, sizeof(dp));
        rep(i,0,n) dp[0][0][i] = s[i];
        repq(x,1,turn) repq(i,0,x) {
            int j = x - i;
            bool ok = true;
            rep(k,0,n) {
                ll v = -1, w = -1;
                if(j != 0) v = dp[i][j-1][k] + dp[i][j-1][(k-1+n)%n];
                if(i != 0) w = dp[i-1][j][k] + dp[i-1][j][(k+1)  %n];
                dp[i][j][k] = max(v, w);
                if(dp[i][j][k] != t[k]) ok = false;
            }
            if(ok) return string(i, 'R') + string(j, 'L');
        }
        
        return "No solution";
    }
};