読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2013 Round1C Easy TheArray

SRM

さてTCO2013 Round1C。
これは参加してないけど、EasyとMediumは解けたので出ればRound2抜けられてたな。
とはいえMediumでちょっと時間食ってさほどいい順位じゃないけど。
http://community.topcoder.com/stat?c=problem_statement&pm=12455

問題

整数列の初期値F・終了値L・要素数Nおよび、隣接要素間の差の絶対値の最大値Dが与えられる。
この数列であり得る最大の要素値を答える。

解法

問題文がちょっとややこしい。
別に等差数列である必要はないので、FからできるだけDを足して値を大きくして、後でまたDずつ減らして最後にLに戻ってくれば良い。
Fから何回Dを足して戻ってこれるかをシミュレートすればよいので、O(N)で終わる。

class TheArray {
	public:
	int find(int n, int d, int first, int last) {
		int ma=max(first,last);
		int i;
		if(n==2) return ma;
		
		FOR(i,n) {
			int t=first+i*d;
			if(t-(n-1-i)*d<=last) ma=max(ma,t);
			else if(t-(n-1-i)*d<last+d) ma=max(ma,last+(n-1-i)*d);
			
		}
		return ma;
	}
};

まとめ

問題文がわかりにくいなぁ…。
解法は幸いすぐに思いついたけど、微妙に-1を付ける場所とか間違えそうで怖い。

広告を非表示にする