Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1886-915087b6
この記事にトラックバックする(FC2ブログユーザー)

SRM498 DIV1 EASY/DIV2 MEDIUM - FoxSequence (この記事を編集する[管理者用])

Source

TopCoder SRM498 DIV1 EASY (250pt)
TopCoder SRM498 DIV2 MEDIUM (500pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

与えられた数列 (要素数50以下) が,以下の4つの等差数列を繋げたものになっているかどうかを判定する問題.
 最初は単調増加の等差数列 (要素数2以上)
 次は単調減少の等差数列 (要素数2以上)
 次は定数数列 (要素数1以上,つまり空でも良い)
 次は単調増加の等差数列 (要素数2以上)
 次は単調減少の等差数列 (要素数2以上)

解法

今どのパートにいるか,交差は何かを覚えつつ,左からなぞれば良い.
以下のコードは,それぞれのパートがどこか全部試すO(50^5)のコード.
他の人のコードは,交差の変化点だけ抜き出して,それが正負0正負,または正負正負の場合のみOKとしてる人が結構いた.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int is_ok(int a[],int size,int fg){
  int i,d;
  if(size<=1) return 1;

  d = a[1] - a[0];
  if(fg == 0 && d != 0) return 0;
  if(fg > 0 && d <= 0) return 0;
  if(fg < 0 && d >= 0) return 0;

  REP(i,1,size) if(a[i]-a[i-1] != d) return 0;
  return 1;
}

class FoxSequence {
public:
string isValid(vector <int> seq) {
  int i,n;
  int a,b,c,d;
  int in[600];
  string res;

  n = seq.size();
  rep(i,n) in[i]=seq[i];

  REP(a,1,n){
    if( !is_ok(in,a+1,1) ) continue;
    REP(b,a+1,n){
      if( !is_ok(in+a,b-a+1,-1) ) continue;
      REP(c,b,n){
        if( !is_ok(in+b,c-b+1,0) ) continue;
        REP(d,c+1,n-1){
          if( !is_ok(in+c,d-c+1,1) ) continue;
          if( !is_ok(in+d,n-d,-1) ) continue;
          return "YES";
        }
      }
    }
  }

  return "NO";
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1886-915087b6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。