Topcoder SRM 712 Div.1 Easy - LR

問題概要

N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる。

• 操作L: S[i]の値をS[i]+S[i-1]とする。ただしi=0のときはS[i]+S[N-1]
• 操作R: S[i]の値をS[i]+S[i+1]とする。ただしi=N-1のときはS[i]+S[0]

N <= 50, 0 <= S[i], T[i] <= 10¹⁵

解法

最終的にそれぞれの回数が同じであるならば、L, Rを行う順番は結果に影響しない。つまりLLLRRRもRRRLLLもRLRLRLも結果として出てくる数列は同じである。ゆえにまず操作を行う全体回数を決め打ちし、その中でまたLを行う回数を決め打ちするという全探索を行えばよい。操作の全体回数はO(log(max(T[i])))で抑えられそうだが、問題文で100回でOKといっているのでこれを素直に使えばいい。オーバーフローには注意が必要で、足し算を行うたび毎回Sの各要素がTを超えていないかチェックするとこれを避けることができる。

感想

オーバーフローが罠い

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

int N;
ll A[55];
ll B[55];
ll C[2][55];
const ll MAX = 1000000000000000;

class LR {
public:
    bool check(int L, int R) {
        REP(i, N) C[0][i] = A[i];
        int cur = 0, tar = 1;
        
        REP(l, L) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i-1+N)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }
        
        REP(r, R) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i+1)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }

        REP(i, N) if (B[i] != C[cur][i])
            return false;

        return true;
    }
    
    string construct(vector<ll> s, vector<ll> t) {
        N = s.size();
        REP(i, N) A[i] = s[i];
        REP(i, N) B[i] = t[i];

        REP(i, 101) REP(L, i+1) {
            int R = i - L;
            if (check(L, R)) {
                string ans = "";
                REP(_, L) ans += "L";
                REP(_, R) ans += "R";
                return ans;
            }
        }

        return "No solution";
    }
};