解いた問題のソースコードと解説など。


SRM 586 Div1 Easy PiecewiseLinearFunction

問題

http://community.topcoder.com/stat?c=problem_solution&rm=318227&rd=15698&pm=12691&cr=23058389
(y[0], 1) (y[1], 2) (y[3], 3)・・・となるようなvector int yが与えられる。これらの点を順につないでいき、直線の関数のつなぎあわせをつくる。y = hという関数のhを変化させ、この区分線形関数との交点数を最大化したい。最大となる交点の数を求めよ。

やりかた

調べればいいのはy[0], y[1], y[2]... の付近のみでいい。ただし、これらの点のみでは
y[] = {2,1,2}などの時に4ではなく3と答えてしまいWAになる。y[i]とy[i]±0.5の点で調べればオーケー。double を扱いたくなかったので全体を2倍して整数の比較のみでいけるようにした。

y=hが関数の継ぎ目の点と交わるときは交点が一つであるのでそこに注意する。

以下ソース。

class PiecewiseLinearFunction {
public:
  int cnt(vector<int> y, int h){
    int a = 0, b = 0;
    //区分線形関数との交点
    for(int i = 0; i < (int)y.size() - 1; i++){
      if((y[i] <= h && h <= y[i + 1]) ||
	 (y[i + 1] <= h && h <= y[i])) a++;
    }
    //y=hが点と交差するとき2つに数えてしまっていたぶんを引く
    for(int i = 1; i < (int)y.size() - 1; i++) if(y[i] == h) b++;
    return a - b;
  }
  int maximumSolutions(vector <int> y) {
    int N = y.size();
    int result = -1;
    for(int i = 0; i < N; i++) y[i] *= 2;
    for(int i = 0; i < N - 1; i++) if(y[i] == y[i + 1]) return result;
    for(int i = 0; i < N; i++){
      result = max(result, max(cnt(y, y[i]), 
			       max(cnt(y, y[i] - 1), cnt(y, y[i] + 1))));
    }
    return result;
  }
};

本番中はほとんどこれと同じで出したのに落ちてしまった。前後±0.5ではなく別のy座標を与えていた。それでもうまく行くと思ったけどだめだった。
落とした自分が言うことではないけれど、なんで落としてる人が多いんだろう。

Get up! 明日のSUPER ST@R!