Codeforces #180 Div2 A "Snow Footprints"
問題
http://codeforces.com/contest/298/problem/A
訳
n個のブロックに分かれている真っ直ぐな雪道がある。
このブロックは左から右に向かって1~nの番号が振られている。
もし、ブロックiからブロックi+1へと移動した場合、
ブロックiには右へ向かう足跡が残されることになる。
ブロックiからブロックi-1へと移動した場合、
ブロックiには左へ向かう足跡が残されることになる。
もし、すでにブロックiに足跡が残されていたら、
それは新しい足跡で上書きされる。
始めは足跡は全くない。
そして白熊のアリスはブロックsからスタートし、ブロックtで止まった。
アリスは道の外へ出なかったことが分かっている。
あなたに雪道に残されたアリスの足跡の方向が与えられる。
そのような足跡を残す事ができるsとtを出力せよ。
制約
3 <= n <= 1000
考えた事
sはどこでもよくて、LRの境目をtにすればいいだけじゃないか?
足跡の残ってる範囲を好きなだけ往復できるわけだし
あ、RもしくはLだけって場合があるのか・・
さらに足跡が全く残ってない場合もあるな
めんどくさいなぁ。
この4パターンで場合わけして書こう。
ソースコード
int main() { int N; string F; cin >> N >> F; bool R = false, L = false; // 右向き左向きがあったか? int LI = -1, RI = -1, C = -1; // 足跡の範囲[LI, RI)とLRの境目 for( int i = 0; i < N; i++ ){ if( F[i] == 'R' ) R = true; if( F[i] == 'L' ) L = true; if( LI == -1 && F[i] != '.') LI = i; if( F[i] == '.' && i != 0 && F[i-1] != '.' ) RI = i; if( F[i] == 'L' && i != 0 && F[i-1] == 'R' ) C = i; } // 4パターンにわける int s=-1, t=-1; if( R && L ){ s = LI; t = C; }else if( R ){ s = LI; t = RI; }else if( L ){ s = RI - 1; t = LI - 1; }else{ s = t = 0; } printf( "%d %d\n", s+1, t+1 ); }