☀ なので悲しいね. 解法はわかったんだけど実装ミスしてしまった.
Easy (300) LR
TopCoder Statistics - Problem Statement
問題概要
長さ の環状の数列 が与えられる. この数列 に対し, 回までの以下の操作を行って数列 にできるか判定し, できるのならその手順を求めよ.
L
: すべての要素に対して, その要素の左隣の要素の値を加算する.R
: すべての要素に対して, その要素の右隣の要素の値を加算する.
解法
L
R
が可換であることが分かれば, あとは試すだけ(試すだけ).
操作を L
R
の順で行うと, 数列の状態は以下のようになるのはそれはそう.
-> ->
操作を R
L
の順で行うと, 数列の状態は以下のようになるのもそれはそう.
-> ->
これらを比較すると全く同じなので, L
R
の順で行っても R
L
の順で行っても, 最終的な数列は同じということがわかる.
ということは, なにか適当な操作手順が並んでいても L
と R
を入れ替えることにより, 例えば L
L
…R
R
… のように整列することができる.
結局は, 最初に L
を 回, 次に R
を 回行う操作のみに限定してよくて, このような についてすべて試して一致するか見れば良い.
なので十分高速.
ソース
オーバーフローを意識してたら別の所を実装ミスしてた.
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"; } };