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] <= 1015
解法
最終的にそれぞれの回数が同じであるならば、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"; } };