SRM 585 DIV1 本番

久しぶりにSRM。実際に死んだ

Coding

Easy (250)

ほぼ全部を'∧'の形で回る数え方を考えて、1つの車では(平均的に)3つしか回れないかな、と思いceil(頂点数/3)をMODで計算した。
色々考えたり少し手間取ったりして遅すぎた

Medium (500)

数え上げ嫌い。順列嫌い。
全然方針が見つからなかった。
後半は小さな値から順においてって既に置いてある右側に置いたら分割されるなーとか考えてた。
でもその先が全然駄目だった。
解答は列に挿入してく感じになるらしい。それは自分の(脳内の)順列典型リストになかったので、追加しておこう。

Challenge

誰かに1人落とされてた。
1人、入力0の時にスタック上のdp[-1]を0としてアクセスしてるものがあったが、それにChallengeした人が失敗していた。
考えたら、引数の0がスタックにあってそれにアクセスしてるのかなーとか思った。

SystemTest

Easyは通ったけれど、赤にもなってMed解けてないという事実が重くのしかかる。

結果

Easy: 226.63/250
Medium: Opened
Challenge: 0/0 = +0
Division Place: 179/821
Rating: 2210→2196

コメント

黄色！

コード

Easy

#include <algorithm>

using namespace std;
typedef long long ll;   

unsigned inverse(ll a, const unsigned MOD) {
	ll b = MOD, u = 1, v = 0;
	while(b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	return (u % MOD + MOD) % MOD;
}
unsigned powmod(unsigned long long a, unsigned long long k, const unsigned MOD) {
	unsigned long long r = MOD == 1 ? 0 : 1;
	while(k) {
		if(k & 1)
			(r *= a) %= MOD;
		(a *= a) %= MOD;
		k >>= 1;
	}
	return (unsigned)r;
}

struct TrafficCongestion {
	int theMinCars(int treeHeight) {
		const int MOD = 1000000007;
		ll x = (powmod(2, treeHeight+1, MOD)+MOD-1)%MOD;
		if(treeHeight % 2 == 0)
			x = (x + 2) % MOD;
		return x * inverse(3, MOD) % MOD;
	}
};