Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM586 DIV1 EASY (250pt)
Problem Statement

問題概要

関数 $y = f(x)$ は定義域 $[1, n]$ の区分線形関数.$2 \leq n \leq 50$.
$x$が整数の時 の$f(x)$ の値が整数で与えられ,その間は線分で繋いだものが $f(x)$ となる.
$f(x)$ の値は,$-10^9$ 以上 $10^9$ 以下.
$y$ を何か定数とした時,$y = f(x)$ を $x$ についての方程式と思った時の解の個数の最大値を求める問題.
有限でないならそれを指摘する.

解法

$f(x) = f(x+1)$ となる整数 $x$ があれば,答えは無限.
$y$ の値を端点の周辺のみ調べれば良い.(ただし,$y$ の値は整数だけに限定してはいけない)
$y$ を固定した時,$y = f(x)$ の解の個数は,各折れ線と交わるかを端に注意しながら1つずつ判定していけば良い.(これはDIV2 MEDIUMの問題)
以下のコードでは,値が大きいので無駄に座標圧縮して$y$の値を全部調べた.

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 PiecewiseLinearFunction {
public:
int maximumSolutions(vector <int> y) {
  int i, j, k, n;
  set<int> st;
  set<int>::iterator it;
  map<int,int> mp;
  int res;

  n = y.size();
  REP(i,1,n) if(y[i-1]==y[i]) return -1;

  mp.clear();
  rep(i,n) st.insert(y[i]);
  k = 0;
  for(it=st.begin(); it!=st.end(); it++) mp[(*it)] = k++;
  rep(i,n) y[i] = mp[y[i]] * 2;

  res = 0;

  rep(i,1000){
    k = 0;
    if(y[0] == i) k++;
    REP(j,1,n){
      if( (y[j-1] < i && i <= y[j]) || (y[j-1] > i && i >= y[j]) ) k++;
    }
    res = max(res, k);
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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