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

SRM 485 DIV2 参加記

SRM Programming

3回目のtopcoder、今回こそはレートを上げたい。

250

指定した範囲の価格帯で、末尾に連続する9が最も多くなるような数*1のうち、最も高いものを出力する問題。
与えられた価格帯の最大値以下の数で9がn個続く数を価格帯の最小値を下回らない範囲で順に求め、最後に求まったものを出力する

例:4325の場合
4325,4319,4299,3999

class MicrowaveSelling {
public:
  int mostAttractivePrice(int minPrice, int maxPrice) {
    int result = maxPrice;
		int d = 10;
		while(minPrice<=(maxPrice+1)/d*d-1){
			result = (maxPrice+1)/d*d-1;
			d*=10;
		}
    return result;
  }
};

値の範囲が100万までなので1ずつ調べてる解法などもありました。

結果

Systemtest Passed

500 偶数がこわいの

等差数列の、偶数の項を奇数になるまで2で割り続けることで、できる奇数だけの数列が与えられ、
そこからもとの等差数列を求める問題。
複数解が出る時は辞書順で最小のものを出力する。

解がsigned int型の範囲に収まることが保証されているので一つの項に掛けることのできる2の数は32回未満、
よって、与えられた初項と第二項が取りうる値を順にループで変化させ、
その差を公差になっている等差数列を作ることができるかを調べました。

class AfraidOfEven {
public:
  vector <int> restoreProgression(vector <int> seq) {
    vector <int> r;
		r = seq;
		bool ans = false;
		for(r[0] = seq[0];;r[0] *= 2){
			for(r[1] = seq[1];r[1] > 0;r[1] *= 2){
				int diff = r[1]-r[0];
				ans = true;
				for(int i = 2;i<seq.size();i++){
					r[i] = seq[i];
					while(r[i]<r[i-1]+diff&&r[i]>0){
						r[i]*=2;
					}
					if(r[i]>r[i-1]+diff||r[i]<0){
						ans = false;
						break;
					}
				}
				if(ans)break;
			}
			if(ans)break;
		}
    return r;
  }
};

えっと、元の数列のすべての項が偶数になることはないから、
公差が偶数だとしたらすべて奇数で等差数列を既に満たしている状態であり、
それ以外の場合は公差が奇数になるので、
元の等差数列の偶数番目を取り出した数列か奇数番目を取り出した数列のどちらか片方には奇数しか現れないため、
与えられた等差数列を1つ飛びに取り出せば、どちらかはもとの等差数列の一部になっているというのを聞いた。


ふーん。

結果

Systemtest Passed

1000

開いたけど見てない

結果

oox

1025→1149

はじめてレーティング上がった!

*1:1999円などのトイザらス価格