読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

SRM 712 Div1

183rd 1510 -> 1438 (-72) 短い黄色ライフだった…

【Easy - LR】

二つの数列s,tが与えられる。
以下の二つの操作でsをtにできるならその手順を1つ求めよ。
L操作:aを元の数列、bを操作後の数列とした時、b[i]=a[i]+a[i-1]とする(ただし円環)
R操作:aを元の数列、bを操作後の数列とした時、b[i]=a[i]+a[i+1]とする(ただし円環)

結局行列の積になるので可換。
行列だからといって可換とは限らないですね、、LRとRLが一緒になるので可換でした
参考:SRM 712 Div1 - ei1333の日記


k回以内にできるかを調べるにはLとRの数だけ考慮すればいいのでO(k^3).
オーバーフローには気をつけよう!(challenge succeeded)

  typedef long long ll;
  typedef vector<ll> vec;
  bool f;
  vec L(vec v){
    vec res=v;
    int n=v.size();
    for(int i=0;i<n;i++) res[i]+=v[(i+n-1)%n];
    f|=*max_element(res.begin(),res.end())>1e15;
    return res;
  }
  vec R(vec v){
    vec res=v;
    int n=v.size();
    for(int i=0;i<n;i++) res[i]+=v[(i+1)%n];
    f|=*max_element(res.begin(),res.end())>1e15;
    return res;
  }
  string construct(vector<long long> s, vector<long long> t) {
    string res="No solution";
    for(int i=0;i<=100;i++){
      for(int j=0;j<=100;j++){
	if(i+j>100) continue;
	vec tmp=s;
	f=0;
	for(int k=0;k<i;k++) tmp=L(tmp);
	for(int k=0;k<j;k++) tmp=R(tmp);
	if(f) continue;
	if(tmp==t){
	  res="";
	  for(int k=0;k<i;k++) res+="L";
	  for(int k=0;k<j;k++) res+="R";
	  goto END;
	}
      }
    }
  END:
    return res;
  }

解法すぐわかったから通れば爆上げだっただろうなあ…
注意力コンテストやめてほしい(注意力がないので