SRM 586 - Particle

250

点(i,Y[i-1])と点(i+1,Y[i]) を i = 1..n としてつないだ曲線がある。
この曲線と、直線 y = a との交点の個数の最大値を求めよ。という問題です。

y[i]が大きく、aを沢山調べるのは難しいので、Y[i]とその近くだけを調べれば良いです。
(整数点(Y[i])だけを調べると Y = {0,1,0,1} のときに2を返してしまったりします。これで落ちている人が何人もいました。)
座標を2倍にすると、小数を使わないで整数点以外を調べることができます。

Y[i]の近くを調べるのは、本番中には思いつかなかったので O(n^2) の座圧をして解きました。(もしかするとこの方が実装が軽いかもしれないが、この座圧を思いつくのに時間を費やしすぎてしまった)

class PiecewiseLinearFunction {
public:
	int maximumSolutions( vector <int> Y ) {
		int n = Y.size();
		bool f = false;
		for(int i = 1; i < n; i++)
			if(Y[i-1]==Y[i])f=true;
		if(f)return -1;
		
		vector<int> s = Y;
		sort(s.begin(),s.end());
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(Y[i]==s[j]){
					Y[i] = j*2;
					break;
				}
			}
		}

		int ans = 0;
		for(int i = 0; i < 200; i++){
			int r = 0;
			for(int j = 1; j < n; j++)
				if(Y[j-1]==i||Y[j-1]<i&&i<Y[j]||Y[j]<i&&i<Y[j-1])r++;
			if(Y[n-1]==i)r++;
			ans = max(ans,r);
		}

		return ans;
	}
};

500

AiからA(i+1)までの時間の長さが与えられて、PaとQbは重なっている時間がある。
この条件の下で、XnとYmに重なっている時間があるかを判定する。

PaとQbが重なっているという情報から、PがQに対して進んでいる時間の範囲(最大値と最小値)が分かります。また、QとRの関係も分かっているときに、PとRの関係も分かります。
これは最短路問題に帰着できるので、ワーシャルフロイド法で解けます。

考えやすくするために最大値と最小値の配列をそれぞれ作りましたが、同じ情報しかないので、配列は1つで十分です。

int dl[30][30],dr[30][30];

class History {
public:
	string verifyClaims( vector <string> ys, vector <string> bs, vector <string> q ) {
		int n = ys.size();
		for(int i = 0 ; i < n; i++){
			for(int j = 0; j < n; j++){
				dl[i][j] =  INF;
				dr[i][j] = -INF;
			}
		}
		vector<vector<int> > g(n);
		for(int i = 0; i < n; i++){
			stringstream ss(ys[i]);
			int t,r;
			ss>>r;
			g[i].push_back(0);
			while(ss>>t)
				g[i].push_back(t-r);
		}

		string s;
		for(int i = 0; i < bs.size(); i++)
			s += bs[i];

		for(int i = 0; i < s.size(); i+=6){
			int a1 = s[i]-'A', a2 = s[i+1]-'0', b1 = s[i+3]-'A', b2 = s[i+4]-'0';
			dl[a1][b1] = -(dr[b1][a1] = max(dr[b1][a1],g[b1][b2]-(g[a1][a2+1]-1)));
			dr[a1][b1] = -(dl[b1][a1] = min(dl[b1][a1],(g[b1][b2+1]-1)-g[a1][a2]));
		}
		for(int k = 0; k < n; k++){
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					dl[i][j] = min(dl[i][j],dl[i][k]+dl[k][j]);
					dr[i][j] = max(dr[i][j],dr[i][k]+dr[k][j]);
				}
			}
		}

		string ans;

		for(int i = 0; i < q.size(); i++){
			int a1 = q[i][0]-'A', a2 = q[i][1]-'0', b1 = q[i][3]-'A', b2 = q[i][4]-'0';
			int a = -(g[b1][b2]-(g[a1][a2+1]-1)),b = -((g[b1][b2+1]-1)-g[a1][a2]);
			if(a<dr[a1][b1]||b>dl[a1][b1])ans+='N';
			else ans+='Y';
		}

		return ans;
			
		
	}
};

oo- 198.13 + 213.92 = 412.05
1521 -> 1653

rate が上がりました。楽しい！！✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌