CodeIQ q432 crossing

crossing.c

/* ********************************************************************** */
/*
	矢印を逆転して見ると、隣接要素を交換しながらのソートになっている
	交差回数は、隣接交換に必要な最小回数を表している。

	隣接交換はどこから着手しても同じ結果になるし計算しやすいが
	単純なバブルソートでは時間がかかるのでマージソートを使う。
*/
/* ********************************************************************** */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <setjmp.h>

/* ********************************************************************** */

/* 交差数計算 */
long long count(int * const values, const int length);

/* マージソートしながら交換回数を数える */
static long long sort_and_count(int * const values, const int length, int * const work);

/* マージしながら交換回数を数える */
static long long merge_and_count(int * const values, const int length, const int point, int * const work);

/* ********************************************************************** */

static jmp_buf error_handler;

int main(void) {

	/* エラーハンドラ設定 */
	if (setjmp(error_handler) == 0) {

		/* バッファ割り当て */
		int capacity = 16;
		int length = 0;
		int *values = (int *)malloc(capacity * sizeof (int));
		if (!values) {
			/* メモリ確保失敗 */
			longjmp(error_handler, 1);
			/* NOTREACHED */
		}

		/* 問題読み込み */
		{
			while (scanf("%d", values + length) == 1) {
				++length;

				/* バッファに容量がなければ倍々に拡張 */
				if (length >= capacity) {
					int *expanded;
					capacity <<= 1;
					expanded = (int *)realloc(values, capacity * sizeof (int));
					if (!expanded) {
						/* メモリ拡大失敗 */
						free(values);
						longjmp(error_handler, 1);
						/* NOTREACHED */
					}
					values = expanded;
				}
			}	

			/* 経過時間を診断出力 */
			fprintf(stderr, "Input: %fs\n", (double)clock() / CLOCKS_PER_SEC);
		}

		/* 計算 */
		{
			long long inversions = count(values, length);

			/* 経過時間を診断出力 */
			fprintf(stderr, "Count: %fs\n", (double)clock() / CLOCKS_PER_SEC);

			/* 結果出力 */
			printf("%lld\n", inversions);

		}

		free(values);

		return 0;

	} else {

		/* エラー */
		fputs("Unexcepted error occured.\n", stderr);
		return 1;

	}

}

/* 交差数計算 */
long long count(int * const values, const int length) {

	/* 作業領域割り当て（最後はマージしないので 1/4 で足りる） */
	int * const work = (int *)malloc(((length + 3) >> 2) * sizeof (int)); /* 端数切り上げ */
	if (!work) {
		/* メモリ確保失敗 */
		longjmp(error_handler, 1);
		/* NOTREACHED */
	}

	{

		/* 2 分割 */
		const int point = length >> 1;

		/* 分割の左右それぞれをマージソート */
		long long inversions 
				= sort_and_count(values, point, work)
				+ sort_and_count(values + point, length - point, work);

		/* 最後はマージせずに交換回数だけ計算する */
		int l = 0, r = point;
		while (l < point && r < length) {
			if (values[l] <= values[r]) {
				++l;
			} else {
				++r;
				inversions += point - l; /* 左に残っている要素数だけ移動（交換）する */
			}	
		}

		free(work);

		return inversions;

	}

}

/* マージソートしながら交換回数を数える */
static long long sort_and_count(int * const values, const int length, int * const work) {

	/* ソート不要？ */
	if (length <= 1) {
		return 0;
	}

	/* TODO: 2, 3, 4 要素最適化 */

	{
		/* 2 分割 */
		const int point = length >> 1; /* 右側を大きく */

		/* それぞれで交換回数を計算 */
		const long long inversions 
				= sort_and_count(values, point, work)
				+ sort_and_count(values + point, length - point, work);

		/* マージの際の交換回数を加算 */
		return inversions + merge_and_count(values, length, point, work);
	}

}

/* マージしながら交換回数を数える */
static long long merge_and_count(int * const values, const int length, const int point, int * const work) {

	/* マージ不要？ */
	if (values[point - 1] <= values[point]) {
		return 0;
	}

	/* 左側を作業領域に避難 */
	{
		int l = 0, w = 0;
		while (l < point) {
			work[w++] = values[l++];
		}
	}

	/* マージ開始 */
	{
		long long inversions = 0;

		int l = 0, w = 0, r = point;

		/* 作業領域と右側をマージ */
		while (w < point && r < length) {
			if (work[w] <= values[r]) {
				values[l++] = work[w++];
			} else {
				values[l++] = values[r++];
				inversions += point - w; /* 作業領域に残っている要素数だけ移動（交換）する */
			}	
		}

		/* 作業領域の残り全てを転記 */
		while (w < point) {
			values[l++] = work[w++];
		}

		/* 右側の残りは適正な位置にあるのでそのままで OK */

		return inversions;

	}

}