(Old) NPCA #33 : 濁流

問題文 : 濁流

きつねの曲大好きな身としては, 解かなければと思い意を決して取り組みました.
concon 好きです.

解法 :
算数, しよう.(提案)
明らかに(x, y) と(y, x) を押す順番は一緒なので, x > y なら折り返してしまいましょう.
その後, マスの斜め上半分だけに注目します. (行列で言うと上三角になっている箇所.)
たとえば, 大きさ 4 のmofbeat 板なら

①②④⑥
　③⑤⑧
　　⑦⑨
　　　⑩

この部分です.

すると, 左上方向から順番に番号がついていること気づきます. 和が小さいものの並びですネ.
そこで, f(x) : 和がx 未満でunique な番号の個数 という関数をがんばって作ります.
同じ和のグループの中で, 自分の位置はabs(x - y) / 2 + 1 番目 になります(問題文から分かります).

実装は軽いですが, なかなかおもしろい問題です.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;

lint f(lint x)
{
	lint ret;
	lint s = x / 2;
	
	ret = s * (s - 1) / 2 * 2;
	if (x & 1) ret += s;
	
	return (ret);
}

int main()
{
	lint N, y, x;
	lint pos;
	
	scanf("%lld %lld %lld", &N, &y, &x);
	if (x < y) swap(x, y);
	
	pos = abs(x - y) / 2 + 1;
	
	if (x + y <= N + 1){
		pos += f(x + y);
	}
	else {
		lint s = N / 2;
		pos += s * (s + 1) / 2 * 2;
		if (N & 1) pos += (N + 1) / 2;
		pos += f(N + 1) - f(2 * N + 3 - x - y);
	}
	
	printf("%lld\n", pos);
	
	return (0);
}