TopCoder SRM 590 Div1

Tatsuya Yatagawa
Programming Contest

はい、では今日もさっそく行ってみましょう。

今日のEasyのみ解説します。

Easy (250点)

この問題は横一列のマス目がいくつかあって、そこに右にしか動けない駒と左にしか動けない駒がいくつか置いてあります。

その駒を動かして初期配置beginから目的配置targetに変更できるかどうかを答えます。

まず、注意したいのが駒の順番は入れ替わらないということです。

ですから、beginとtargetの両方で左から順に出てくるRとLの文字をstringか何かにスタックしていきます。

そのあとで文字列を比較して、もし違っていたら目的配置にすることは不可能です。

こうすることで出現してくるLとRの数がbeginとtargetで同じになっていることも確認できます。

これが確認できたら、あとはbeginで右からk番目に現れる駒の同じ位置あるいはそれより右の位置でtarget上にk個以上Rが現れているかを確認します。

Lについても同様にbeginで左からk番目に現れる駒の同じ位置あるいはそれより左でtarget上にk個以上Lが現れているかを確認します。

以上ができれば、問題なく通るはずです。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define REP(i,n) for(int i=0; i cnt) return "Impossible";
            }
        }

        // check R
        for(int i=0; i cnt) return "Impossible";
            }
        }

        return "Possible";
    }
}
```



ありそうなChallengeケースは2種類ほど見つけていて、まずはLとRの出現回数を数えていないパターン。

たとえば{..LR..}, {LR..LR}みたいなケースで落とせます。

次に順番が入れ替わらない事を考慮していないケース。

たとえば{.RL.}, {L..R}みたいなケースで落とせます。

* * *

## まとめ

聞いたところによるとMediumは剰余の連立方程式で解ける問題らしい。

面白そうなので気が向いたら更新するかもです。

それでは、また。