ei1333の日記

ぺこい

SRM 712 Div1

☀ なので悲しいね. 解法はわかったんだけど実装ミスしてしまった.

Easy (300) LR

TopCoder Statistics - Problem Statement

問題概要

長さ  {n(1 \le n \le 50)} の環状の数列  {s_i(0 \le s_i \le 10^{15})} が与えられる. この数列  {s} に対し,  {100} 回までの以下の操作を行って数列  {t} にできるか判定し, できるのならその手順を求めよ.

  • L: すべての要素に対して, その要素の左隣の要素の値を加算する.
  • R: すべての要素に対して, その要素の右隣の要素の値を加算する.

解法

L R が可換であることが分かれば, あとは試すだけ(試すだけ).

操作を LR の順で行うと, 数列の状態は以下のようになるのはそれはそう.

 {\{s_1, s_2, \dots, s_n\}} ->  {\{s_n+s_1, s_1+s_2, \dots, s_{n-1}+s_n\}} ->  {\{s_n+2s_1+s_2, s_1+2s_2+s_3, \dots, s_{n-1}+2s_n+s_1\}}

操作を RL の順で行うと, 数列の状態は以下のようになるのもそれはそう.

 {\{s_1, s_2, \dots, s_n\}} ->  {\{s_1+s_2, s_2+s_3, \dots, s_n+s_1\}} ->  {\{s_n+2s_1+s_2, s_1+2s_2+s_3, \dots, s_{n-1}+2s_n+s_1\}}

これらを比較すると全く同じなので, LR の順で行っても RL の順で行っても, 最終的な数列は同じということがわかる.

ということは, なにか適当な操作手順が並んでいても LR を入れ替えることにより, 例えば LLRR… のように整列することができる.

結局は, 最初に L {x} 回, 次に R {y(0 \le x + y \le 100)} 回行う操作のみに限定してよくて, このような  {x, y} についてすべて試して一致するか見れば良い.

 {O(n^3)} なので十分高速.

ソース

オーバーフローを意識してたら別の所を実装ミスしてた.

typedef long long int64;

class LR
{ 
  const int64 INF = 1LL << 59;

  void updateR(vector<int64>& s)
  {
    vector< int64 > buff(s.size());
    for(int i = 0; i < s.size(); i++) {
      buff[i] = s[i] + s[(i + 1) % s.size()];
      buff[i] = min(buff[i], INF);
    }
    swap(s, buff);
  }

  void updateL(vector<int64>& s)
  {
    vector< int64 > buff(s.size());
    for(int i = 0; i < s.size(); i++) {
      buff[i] = s[i] + s[(i + s.size() - 1) % s.size()];
      buff[i] = min(buff[i], INF);
    }
    swap(s, buff);
  }
  
public:
  
  string construct(vector<int64> s, vector<int64> t)
  {
    auto beet = s;
    for(int L = 0; L <= 100; L++) {
      auto latte = beet;
      for(int R = 0; L + R <= 100; R++) {
        bool match = true;
        for(int i = 0; i < t.size(); i++) match &= latte[i] == t[i];
        if(match) return(string(L, 'L') + string(R, 'R'));
        updateR(latte);
      }
      updateL(beet);
    }
    return "No solution";
  }
};