Member SRM 491 DIV2

仮眠取って、JOI予選直前だけど参加してきました。問題の一部をid:JAPLJ君が作問したらしい。div2 500もそれだったけど、良い問題だったと思います!

250 OneDigitDifference

1桁弄って最小の値を作れ。与えられた整数の最大の桁の値を0にしてやればいいことが分かる。

ただ入力が0の場合は1にしなければならない。これはさすがに250なだけあって入力ケースで与えられていたので問題無し。無かったらチャレンジ祭り。

実際はもっと汚いコード提出してるけどまあいい。

class OneDigitDifference {
public:
	int getSmallest(int N) {
		stringstream ss; ss << N;
		return (N?atoi(ss.str().substr(1).c_str()):1);
	}
};

Passed System Test 246.03.

500 FoxMakingDiceEasy

NとKが与えられる。1 <= N の範囲の数を使ってサイコロを作った時(サイコロの向かい合う面の合計は全て等しい)。向かい合う面の合計がK以上のサイコロは何通りあるか。

1つの対のペアを決めた時、そのペアの間の数を使ってできるペアは決まる。([1,6]って決めたら [2,5],[3,4]が使えるペアになる。)

出来るペアの個数は、区間の最小の端をmin、最大の端をmaxとすると、

(max - min - 1)が偶数ならば、(max - min - 1)/2

(max - min - 1)が奇数ならば、(max - min - 1)/2 - 0.5

(1つ使えないペアがあるため。)

実際はintで切り捨てられるから偶数と同じ式でいい。

考えられる。全区間(min < max <= N での)についてそれをやる。組み合わせはnCr?。習ってないから分かんないけどとりあえずそれっぽいことした。

超低速Submitした感じ。

long long ncr(ll n,ll r){
	ll ret = 1;
	rep(i,r)ret *= (n-i);
	return ret;
}

class FoxMakingDiceEasy {
public:
	int theCount(int N, int K) {
		int ret = 0;
		
		for(int mi = 1; mi <= N ; mi++){
			for(int mx = mi+5; mx <= N ; mx++){
				if(mx + mi < K)continue;  
				ret += ncr((mx-mi-1)/2,2);
			}
		}
		return ret;
	}
};

Passed System Test 237.69.

1000 BottlesOnShelf

500に時間かけ過ぎたので見るだけにした。とりあえず最大の入力入れたら落とせそうな問題だということだけ理解してテストケースつくった。

Compiled.

Challenge

快挙。6回成功、3ミス = 50.0 * 6 - 25.0 * 3 = 225.0Pt.

500に時間掛けすぎたのを取り返せるくらい出来た。

Result

246.03 + 237.69 + 0.00 + 225.00 = 708.72

Division 12位。Room1位。

1048 → 1208 (+160)

よっしゃーDiv1もどったー。けどまた跳ね返されそう。