Submission #9815160

---

Source Code Expand

unittest
{
	assert( [ "5 7", "11 13 17 19 23" ].parse.expand.solve == 5 );
	assert( [ "4 10", "0 3 6 10" ].parse.expand.solve == 0 );
	assert( [ "6 36", "0 5 32 48 69 71" ].parse.expand.solve == 4 );
	assert( [ "6 405885562", "133510576 158828561 245133494 461153833 840383806 867039395" ].parse.expand.solve == 6 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nd = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( nd[ 1 ], as );
}

auto solve( long d, long[] as )
{
	// 都市iから徒歩で移動できる都市の数を計算
	auto bs = new long[ as.length ];
	for( auto i = 0L, j = 1L; i < as.length; i++ )
	{
		while( j < as.length && as[ j ] - as[ i ] <= d ) j++;
		bs[ i ] = j - i - 1;
	}
	
	// bsの累積和表を作成
	auto bts = new long[ 1 + as.length ];
	foreach( i, b; bs )
	{
		bts[ i + 1 ] = bts[ i ] + b;
	}
	bts.popFront;
	
	// 徒歩で都市i->j->k かつ 電車で都市i->k と移動するパターンの数を計算
	auto ans = 0L;
	foreach( i, b; bs )
	{
		auto bt = bts[ i + b ] - bts[ i ];		// 徒歩で都市i->j->k と移動するパターンの数
		auto rt = b.combination( 2 );			// 徒歩で都市i->k と移動するパターンの数
		ans += bt - rt;
	}
	return ans;
}

// 組み合わせ数
auto combination( long n, long k )
{
	if( n < k ) return 0;
	auto r = 1L;
	for( auto d = 1L; d <= k; d++, n-- )
	{
		r *= n;
		r /= d;
	}
	return r;
}

Submission Info

Judge Result