土下座しながら探索中

主に競技プログラミング

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;
  }
};