kmjp's blog

競技プログラミング参加記です

TopCoder SRM 590 Div1 Easy FoxAndChess

今回はMediumがちょっと難しめなため、上位を除けばEasy早解き回になった。
自分もMediumが解けなかったが、幸いChallengeが1個とれて250ptを超え、上位に入った。
http://community.topcoder.com/stat?c=problem_statement&pm=12725

問題

1次元に並んだマスで行われるチェスを考える。
初期状態でいくつか左右どちらかを向いたポーンがある。
各ポーンは向いてる向きに1マスずつ移動可能。他のポーンがあるマスには移動できない。
最終的なマスの状態が与えられたとき、その状態に遷移可能か答えよ。

解法


まず、初期状態と最終状態で左右向きのポーンの順番が等しいか確認する。
等しい場合、初期状態のポーンと最終状態のポーンを対応付けられるので、移動した向きが左右あっているかを判定すればよい。

class FoxAndChess {
int T[100],T2[100],A[100],B[100];

public:
string ableToMove(string begin, string target) {
int i,N;
N=begin.size();
string S,S2;

FOR(i,N) {
if(begin[i]!='.') S += begin[i];
if(target[i]!='.') S2 += target[i];
}
if(S!=S2) return "Impossible";

int N1=0,N2=0;
FOR(i,N) {
if(begin[i]!='.') {
T[N1]=begin[i];
A[N1]=i;
N1++;
}
if(target[i]!='.') {
T2[N2]=target[i];
B[N2]=i;
N2++;
}
}
FOR(i,N1) {
if(T[i]=='L') if(A[i] if(T[i]=='R') if(A[i]>B[i]) return "Impossible";
}
return "Possible";
}
};
|

まとめ

もうチョイ簡潔にも書けるかな?
Medium落としたけどレート上昇してよかった。

広告を非表示にする