SRM 712 DIV 1 easy : LR
問題概要:
サイズがnであるような2つの数列s,tが与えられる。
数列s,tの各要素には0からn-1まで番号がふられている。
数列sに対して以下の2つの操作を任意の回数だけ適用してtにできるか。
できるならその適用した順序を1つ出力せよ。
操作1. s[i] = s[i] + s[i-1] ( ただし i-1 < 0 なら s[i-1] は s[n-1] )
操作2. s[i] = s[i] + s[i+1] ( ただし i+1 >= n なら s[i+1] は s[0] )
解法:
操作1と操作2の使用回数が同じ場合、その順番によって結果は変わらない。
つまり、(操作1)→(操作2)→(操作1)→(操作2)の結果得られる数列と
(操作1)→(操作1)→(操作2)→(操作2)の結果得られる数列は同じである。
そのため、操作1と操作2を同じ回数で何回適用するか決め打ちする。
その後操作1だけを適用してtを作れるか、また操作2だけを適用してtを作れるかを試す。
注意点::オーバーフロー
s = { 1, 1 } t = { 0, 0 }
のようなケースでオーバーフローしないか?
私は「そんなうまいケースないでしょ」と手を抜いてしまいeasy落としました。
悔い改めます。
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; const string NO = "No solution"; class LR { public: vector<ll> tmp; void simulateL(vector<long long> &vec) { int n = (int)vec.size(); vector<long long> next(n); rep(i,n) next[i] = vec[i] + vec[((i-1)+n)%n]; vec = next; } void simulateR(vector<long long> &vec) { int n = (int)vec.size(); vector<long long> next(n); rep(i,n) next[i] = vec[i] + vec[(i+1)%n]; vec = next; } bool check(vector<ll> &s,vector<ll> &t) { rep(i,(int)s.size()) { if( s[i] < tmp[i] ) return false; if( s[i] != t[i] ) return false; } return true; } int checkL(vector<ll> s,vector<ll> t,int rem) { if( check(s,t) ) return 0; REP(i,1,rem+1) { simulateL(s); rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1; if( check(s,t) ) return i; } return -1; } int checkR(vector<ll> s,vector<ll> t,int rem) { if( check(s,t) ) return 0; REP(i,1,rem+1) { simulateR(s); rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1; if( check(s,t) ) return i; } return -1; } string construct(vector<long long> s, vector<long long> t) { string ans = ""; tmp = s; rep(i,101) { if( 100 - 2 * i < 0 ) break; if( check(s,t) ) { return ans; } int use; if( ( use = checkL(s,t,100-2*i) ) != -1 ) { rep(_,use) ans += "L"; return ans; } if( ( use = checkR(s,t,100-2*i) ) != -1 ) { rep(_,use) ans += "R"; return ans; } simulateL(s); rep(j,(int)s.size()) if( s[j] < tmp[j] ) break; simulateR(s); rep(j,(int)s.size()) if( s[j] < tmp[j] ) break; ans += "LR"; } return NO; } };