SoundHound Inc. Programming Contest 2018 -Masters Tournament- 予選 C, D - 解説

今回は30歳以上の方の枠が広いプロコンでした。かつて競プロですごく強かったみたいな人がでていらっしゃっていてかっこよかったです。憧れる〜

コンテストサイトです。
SoundHound Inc. Programming Contest 2018 -Masters Tournament- - AtCoder

C - Ordinary Beauty

$n^m$ とか出てきて一瞬ドン引きします。 $1000000000^{1000000000}$ なんかC++では扱えません。でも平均というからには分母に $n^m$ がくるはずです。なんとなく分子に $n^{(something)}$ がくるときれいに割り切れてくれて幸せになれそうです。

真面目な考察

真面目に考えていきます。
手元で計算をします。分子には全ての数列の美しさの総和をつっこんでやらねばなりません。これを考えます。

第 $k$ 項と第 $k+1$ 項によってつくられる美しさの和を全てのkについて足せば、全ての数列の美しさの総和を考えることができます。

第 $k$ 項と第 $k+1$ 項の差がdとなるような「第 $k$ 項と第 $k+1$ 項の数の組」は、

$d>0$ のとき $2(n-d)$
$d=0$ のとき $n$

組あります。

次に、第 $k$ 項と第 $k+1$ 項が美しいような数列の数を求めます。
第 $k$ 項と第 $k+1$ 項の差がdとなるとき、他のm-2項はなんでもいいので、これを満たすような数列の数は

$d>0$ のとき $2(n-d)n^{m-2}$
$d=0$ のとき $n\times n^{m-2} = n^{m-1}$

です。
これは、第 $k$ 項と第 $k+1$ 項によってつくられる美しさの総和と等しいといった言い方もできそうです。

長さ $m$ の数列で隣り合う2数は $m-1$ 組あるので、美しさの総和は

$d>0$ のとき $2(n-d)(m-1)n^{m-2}$
$d=0$ のとき $(m-1)n^{m-1}$

となります。

あとはこれを $n^m$ で割ります。答えは

$d>0$ のとき $\frac {2(n-d)(m-1)n^{m-2}}{n^m} = \frac {2(n-d)(m-1)}{n^2}$
$d=0$ のとき $\frac {(m-1)n^{m-1}}{n^m} = \frac {m-1}{n}$

です。

ビジュアライズ的な

この画像を見ればわかる場合とわからない場合があるぞい

f:id:hewla:20180710142141j:plain — ①×②×③が美しさの総和となります

▶ソースコードを開く

int main(){
	std::cin >> n >> m >> d;
	if(d == 0.0){
		ans = (m-1)/n;
	}else{
		ans = 2*(m-1)*(n-d)/(n*n);
	}
	printf("%.10lf\n", ans);
	return 0;
}

D - Saving Snuck

変わった通貨が出てきました。問題文読解がちょっとややこしくて戸惑いました。日本語が苦手。

0年目はどこで両替してもいいのでパターンがたくさんありそうで大変です。しかし、n-1年目は両替を都市nで行う必要があります。この年においては、

sからnまで円で移動
nからtまでスヌークで移動

ということになります。sからnに使う円とnからtに使うスヌークの最適解はダイクストラ法を用いると求められます。

n-2年目はn-1年目に比べて、都市n-1の両替所も使えるようになります。そうすると、先ほどの場合に加えて、都市n-1の両替所を経由して移動するパターンを考えて、この2パターンのうち答えの良い方を選んで答えとすればいいです。

同様に、n-3年目には都市n-2の、n-4年目には都市n-3の、...、1年目には都市2の、0年目には都市1の両替所が新しく使えるようになります。
都市sから都市iまで移動するのにかかる円の最小値を $yen_i$ 、都市iから都市tまで移動するのにかかるスヌークの最小値を $snuuk_i$ とします。
i年目の答え $ans_i$ は新しく使えるようになった両替所を経由する答えと1年後の答えの良い方なので、
$ans_i = max(ans_{i+1}, 10^{15} - (yen_{i+1} + snuuk_{i+1}))$
となります。この漸化式を、n-1年後から順に埋めていけば良いです。

$yen_i$ はsを始点としたダイクストラ法1回で全てのiについて求めることができます。
また、鉄道はどこも双方向に走っているので、 $snuuk_i$ はtからiまでにかかるスヌークの最小値に等しいです。したがって、tを始点としたダイクストラ法で求められます。

ダイクストラ法を実装したのはJOI以来です。というより実装を真面目にやったのがすごく久しぶりな気がします。思い通りに動いた時はやっぱり楽しいです。

▶ソースコードを開く

const long LINF = 1123456789012345678;

typedef std::pair<long, long> P;
long cost[100005][2];//[0]:yen s -> i, [1]:snuuk i -> t

long n, m, s, t;

struct Edge{
	long to;
	long cost[2];
};

std::vector<Edge> edge[100005];

long ans[100005];

void dijkstra(int a){
	std::priority_queue<P, std::vector<P>, std::greater<P> > que;
	long st;
	if(a == 0){
		st = s;
	}else{
		st = t;
	}
	cost[st][a] = 0;
	que.push(P(0, st));
	
	while(!que.empty()){
		P p = que.top();
		que.pop();
		long v = p.second;
		if(cost[v][a] < p.first){
			continue;
		}
		for(int i = 0; i < edge[v].size(); i++){
			Edge e = edge[v][i];
			if(cost[e.to][a] > cost[v][a] + e.cost[a]){
				cost[e.to][a] = cost[v][a] + e.cost[a];
				que.push(P(cost[e.to][a], e.to));
			}
		}
	}
}

int main(){
	std::cin >> n >> m >> s >> t;
	for(int i = 0; i <= n; i++){
		cost[i][0] = LINF;
		cost[i][1] = LINF;
	}
	for(int i = 0; i < m; i++){
		long u, v, a, b;
		std::cin >> u >> v >> a >> b;
		Edge e1 = {u, {a, b}};
		Edge e2 = {v, {a, b}};
		edge[v].push_back(e1);
		edge[u].push_back(e2);
	}

	dijkstra(0);
	dijkstra(1);

	ans[n] = cost[n][0] + cost[n][1];
	for(int i = n-1; i > 0; i--){
		ans[i] = std::min(cost[i][0] + cost[i][1], ans[i+1]);
	}
	for(int i = 1; i <= n; i++){
		printf("%ld\n", 1000000000000000 - ans[i]);
	}
	return 0;
}

Rating 2000以下はratedでした。青になりたい人向けコンテストみたいな感じです。~~またやってほs~~
全完して爆上げのつもりでしたがEが解けませんでした。A〜Dの4完でレートはなんとか上がってくれました。
f:id:hewla:20180708120101p:plain
perf:1896で、1483 → 1532 (+49)です。次回で青もあり得る！！！（しかしAGC）