Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM557 DIV1 EASY - FoxAndMountainEasy (この記事を編集する[管理者用])

Source

TopCoder SRM557 DIV1 EASY (250pt)
Problem Statement

問題概要

n+1要素の数列を考える.(nは100000以下)
その数列は非負整数のみからなり,その階差数列 (D[i] = A[i+1] - A[i]) はすべて1か-1.
階差数列の連続する部分がmin(n,50)要素以下与えられる.
また,数列の初項A[0]と末項A[n]が与えられる.
そのような数列が存在しうるかどうかを判定する問題.

解法

階差数列で与えられない部分で,1の要素の数,-1の要素の数は計算可能. 後は0を下回らないように,1を全部使って,与えられた部分を使って,-1を全部使えば良い. 本番では,1を使う数は,0を下回らないぐらい使って,後はgreedyに0に近づくようにシミュレーションした.

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

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

class FoxAndMountainEasy {
public:
string possible(int n, int h0, int hn, string h) {
  int i,j,k,mn;

  k = mn = 0;
  rep(i,h.size()){
    if(h[i]=='U') k++;
    else          k--;
    if(mn > k) mn = k;
  }

  while(n >= 0 && h0 + mn < 0) n--, h0++;
  if(n < h.size()) return "NO";

  n -= h.size();
  h0 += k;

  printf("%d %d %d\n",n,h0,hn);

  while(n > 0){
    if(h0 <= hn) h0++;
    else         h0--;
    n--;
  }
  if(h0==hn) return "YES";
  return "NO";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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