Codeforces #197, B : Xenia and Ringroad

問題文

http://codeforces.com/contest/339/problem/B

概要

円周上の道に沿って n 個の家がある。
始め 1 番 ( 1-indexed ) の家に居て、m 個の用事を済ますために各家を順に訪問する。
i 番目の用事を済ますためには 番の家に行く必要がある。
移動は時計回りにのみ可能で、隣の家に移動するときに単位時間がかかる。
用事自体にかかる時間は無視できる。
全ての用事を済ますのに必要な時間の最小値を求めよ。

解法

通りすぎてまた一周する必要は無いので、無駄な移動をしないようにしてシミュレーションです。
全体を mod n で扱うと都合がよいので 0-based とします。
このとき、現在位置が cur で の家に移動するとすると、その移動距離は ( a + n - cur ) % n です。
cur を更新しながらこの値を全ての i について求めた和が答えです。

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;

	VI as( m );
	FOR( a, as )
	{
		cin >> a;
		a--;
	}

	int cur = 0;
	LL res = 0;
	FOR( a, as )
	{
		res += ( a + n - cur ) % n;
		cur = a;
	}

	cout << res << endl;

	return 0;
}