Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-02-27SRM498 Div1(Practice)

SRM498 Div1 250 FoxSequence

| 17:20 | SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

やるだけだがスピード勝負なので書き方の工夫が求められる

以下の自分のソースはシーケンスを前から順番にイテレートして条件に合うか調べているだけだが意外とこまごまして書きづらい・・

1位の人のを見ると、シーケンスの差分が変わるところだけを抽出して条件に合うかチェックしており短く書けているので頭いいなと思った

ソースコード

class FoxSequence {
public:
	string isValid(vector <int> seq) {
		int N=seq.size();
		if(N<5) return "NO";

		int i=1;

		int diff=seq[1]-seq[0];
		if(diff<=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff>=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		while(i<N && seq[i]-seq[i-1]==0) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff<=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff>=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i!=N) return "NO";

		return "YES";
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110227