0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@anonymously115

paiza問題集の「二次元累積和」のリファクタリング・入力チェック・テストコードを考えてみた。

0
Last updated at Posted at 2026-02-23

paizaラーニングレベルアップ問題集の二次元累積和をやってみました。

問題

参考

二次元配列

早速ですが、二次元配列を管理するクラスを作成します。

  • 二次元配列をコンストラクタの引数に
  • クエリをメソッドの引数に

渡すようなクラスを作成します。

IntArray2.h
#ifndef INTARRAY2_H_
#define INTARRAY2_H_

#include <stdbool.h>

typedef struct __IntArray2 _IntArray2;

typedef struct IntArray2 {
	_IntArray2 *_array;
	bool (*cumulative_sum)(const struct IntArray2*, size_t, size_t, int*);
} IntArray2;

IntArray2* new_IntArray2(size_t, size_t, const int**);

void free_IntArray2(IntArray2**);

#endif /* INTARRAY2_H_ */

「二次元累積和」ですが、毎回

int s = 0;
for (int i = 0; i < y; i++) {
	for (int j = 0; j < x; j++) {
		s += A[i][j];
	}
}

のような二重ループを回していては、100,000クエリを処理しきれません。そこで、

\begin{align}
S_{0,x}&=0\ (0\le x\le N)\\
S_{y,0}&=0\ (0\le y\le N)\\
S_{y,x}&=\sum_{i=1}^y\sum_{j=1}^x a_{i,j}\\
&=a_{y,x}+S_{y-1,x}+S_{y,x-1}-S_{y-1,x-1}\\
\end{align}

を使って、あらかじめコンストラクタにて二次元累積和を計算しておきます。

#include <stdlib.h>
#include <errno.h>
#include "IntArray2.h"

struct __IntArray2 {
	size_t h;
	size_t w;
	const int **A;
	int *sum[];
};

static bool IntArray2_cumulative_sum(const IntArray2 *self, size_t y, size_t x, int *sum) {
	if (y > self->_array->h || x > self->_array->w) {
		errno = ERANGE;
		return false;
	}
	*sum = self->_array->sum[y][x];
	return true;
}

IntArray2* new_IntArray2(size_t h, size_t w, const int** A) {
	IntArray2 *array = (IntArray2*) malloc(sizeof(IntArray2));
	if (!array) {
		return NULL;
	}
	array->_array = (_IntArray2*) malloc(sizeof(_IntArray2) + sizeof(array->_array->sum[0]) * -~h);
	if (!array->_array) {
		free(array);
		return NULL;
	}
	array->_array->h = h;
	array->_array->w = w;
	array->_array->A = A;
	array->_array->sum[0] = (int*) calloc(-~w, sizeof(array->_array->sum[0][0]));
	if (!array->_array->sum[0]) {
		free(array->_array);
		free(array);
		return NULL;
	}
	for (size_t i = 1; i <= h; i++) {
		array->_array->sum[i] = (int*) malloc(sizeof(array->_array->sum[i][0]) * -~w);
		if (!array->_array->sum[i]) {
			size_t t = i;
			while (t--) {
				free(array->_array->sum[t]);
			}
			free(array->_array);
			free(array);
			return NULL;
		}
		array->_array->sum[i][0] = 0;
		for (size_t j = 1; j <= w; j++) {
			array->_array->sum[i][j] = A[i - 1][j - 1]
					+ array->_array->sum[i - 1][j]
					+ array->_array->sum[i][j - 1]
					- array->_array->sum[i - 1][j - 1];
		}
	}
	array->cumulative_sum = IntArray2_cumulative_sum;
	return array;
}

void free_IntArray2(IntArray2** self) {
	size_t i = (*self)->_array->h;
	do {
		free((*self)->_array->sum[i]);
		(*self)->_array->sum[i] = NULL;
	} while (i--);
	free((*self)->_array);
	(*self)->_array = NULL;
	free(*self);
	*self = NULL;
}
テストコード

テストコードを作成し、動作確認したいと思います。

  • コンストラクタ
    • NULL
    • 0行0列（但し、C言語では要素数0の配列は未定義動作になる）
  • 累積和メソッド
    • $y=x=0$
    • $y>H$
    • $x>W$

のケースについてもテストします。

今回は、単体テストツールとしてminunit.hを使用します。

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "IntArray2.h"

int tests_run = 0;

static char* message(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* test_constructor(size_t h, size_t w, const int *A[], const int *expected[]) {
	IntArray2 *intArray2 = new_IntArray2(h, w, A);
	mu_assert("Error: expected: <true> but was: <false>", intArray2);
	int actual[-~h][-~w];
    int **ptr = (int**) ((void*) (intArray2->_array) + sizeof(size_t) + sizeof(size_t) + sizeof(const int**));
    for (size_t i = 0; i <= h; i++) {
        memcpy(actual[i], *ptr, sizeof(actual[i]));
        ptr++;
    }
	free_IntArray2(&intArray2);
	for (size_t i = 0; i <= h; i++) {
        for (size_t j = 0; j <= w; j++) {
            mu_assert(message(expected[i][j], actual[i][j]), actual[i][j] == expected[i][j]);
        }
	}
	return 0;
}

static char* test_constructor_0() {
	const int s[1][1] = { { 0 } };
	const int *S[] = { s[0] };
	return test_constructor(0, 0, NULL, S);
}

static char* test_constructor_1() {
	const int a[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
	const int *A[] = { a[0], a[1], a[2] };
	const int s[4][4] = { { 0, 0, 0, 0 }, { 0, 1, 3, 6 }, { 0, 5, 12, 21 }, { 0, 12, 27, 45 } };
	const int *S[] = { s[0], s[1], s[2], s[3] };
	return test_constructor(3, 3, A, S);
}

static char* test_constructor_2() {
	const int a[3][3] = { { -76, -44, 61 }, { -72, 30, 95 }, { 99, 42, 82 } };
	const int *A[] = { a[0], a[1], a[2] };
	const int s[4][4] = { { 0, 0, 0, 0 }, { 0, -76, -120, -59 }, { 0, -148, -162, -6 }, { 0, -49, -21, 217 } };
	const int *S[] = { s[0], s[1], s[2], s[3] };
	return test_constructor(3, 3, A, S);
}

static char* test_cumulative_sum(size_t h, size_t w, const int **A, size_t y, size_t x, int expected) {
	IntArray2 *intArray2 = new_IntArray2(h, w, A);
	if (!intArray2) {
		return strerror(errno);
	}
	int actual;
	bool result = intArray2->cumulative_sum(intArray2, y, x, &actual);
	free_IntArray2(&intArray2);
	mu_assert("Error: expected: <true> but was: <false>", result);
	mu_assert(message(expected, actual), actual == expected);
	return 0;
}

static char* test_cumulative_sum_fail(size_t h, size_t w, const int **A, size_t y, size_t x) {
	IntArray2 *intArray2 = new_IntArray2(h, w, A);
	if (!intArray2) {
		return strerror(errno);
	}
	int actual;
	bool result = intArray2->cumulative_sum(intArray2, y, x, &actual);
	free_IntArray2(&intArray2);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	mu_assert(message(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_cumulative_sum_0() {
	return test_cumulative_sum(0, 0, NULL, 0, 0, 0);
}

static char* test_cumulative_sum_1() {
	const int a[1][1] = { { 0 } };
	const int* A[] = { a[0] };
	return test_cumulative_sum_fail(1, 1, A, 2, 1);
}

static char* test_cumulative_sum_2() {
	const int a[1][1] = { { 0 } };
	const int* A[] = { a[0] };
	return test_cumulative_sum_fail(1, 1, A, 1, 2);
}

static char* test_cumulative_sum_3() {
	const int a[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
	const int *A[] = { a[0], a[1], a[2] };
	return test_cumulative_sum(3, 3, A, 2, 2, 12);
}

static char* all_tests() {
	mu_run_test(test_constructor_0);
	mu_run_test(test_constructor_1);
	mu_run_test(test_constructor_2);
	mu_run_test(test_cumulative_sum_0);
	mu_run_test(test_cumulative_sum_1);
	mu_run_test(test_cumulative_sum_2);
	mu_run_test(test_cumulative_sum_3);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

Windows環境であれば、以下のようなバッチを作っておけば簡単にテストできるでしょう。

echo off
gcc -Wall -Wextra -Werror -std=c99 IntArray2Test.c IntArray2.c -o IntArrayTest2 1>IntArrayTest2.txt 2>&1
if exist IntArrayTest2.exe (
	.\IntArrayTest2
	echo %ERRORLEVEL%
	del IntArrayTest2.exe
	del IntArrayTest2.txt
) else (
	type IntArrayTest2.txt
)
pause

入力チェック

数値が入るべき所に数字以外の文字が入ってきたり、範囲外の数値が入ってきた場合に適切にはじけるようにしたいと思います。
今回は

  • $1\le H\le 1000$, $1\le W\le 1000$
  • $1\le N\le 100000$
  • $-100\le A_{i,j}\le 100$（$1\le i\le H$, $1\le j\le W$）
  • $1\le y_i\le H$, $1\le x_i\le W$（$1\le i\le N$）

のチェックをします。

#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>

bool read_size(const char*, size_t*, size_t*, size_t*);

bool read_elements(const char*, size_t, int*);

bool read_query(const char*, size_t, size_t, size_t*, size_t*);

#endif /* INPUT_H_ */

#include <string.h>
#include <ctype.h>
#include <inttypes.h>
#include <limits.h>
#include <errno.h>
#include "input.h"

static char* chomp(char *str) {
	size_t n = strlen(str);
	while (n--) {
		if (isspace(str[n])) {
			str[n] = '\0';
		} else {
			break;
		}
	}
	return str;
}

static bool is_unsigned(const char *str) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	if (str[0] == '0') {
		if (str[1]) {
			errno = EINVAL;
			return false;
		}
		return true;
	}
	for (const char *c = str; *c; c++) {
		if (!isdigit(*c)) {
			errno = EINVAL;
			return false;
		}
	}
	return true;
}

static bool is_signed(const char *str) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	if (str[0] == '-') {
		if (str[1] == '0') {
			errno = EINVAL;
			return false;
		} else {
			return is_unsigned(str + 1);
		}
	} else {
		return is_unsigned(str);
	}
}

static bool parse_unsigned(const char *str, uintmax_t max, uintmax_t *out) {
	errno = 0;
	if (!is_unsigned(str)) {
		return false;
	}
	char *s = NULL;
	*out = strtoumax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*out > max) {
		return false;
	}
	return true;
}

static bool parse_signed(const char *str, intmax_t max, intmax_t *out) {
	errno = 0;
	if (!is_signed(str)) {
		return false;
	}
	char *s = NULL;
	*out = strtoimax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*out < ~max || max < *out) {
		return false;
	}
	return true;
}

static bool parse_ulong(const char *str, size_t *out) {
	errno = 0;
	size_t tmp;
	if (!parse_unsigned(str, SIZE_MAX, &tmp)) {
		return false;
	}
	*out = (size_t) tmp;
	return true;
}

static bool parse_int(const char *str, int *out) {
	errno = 0;
	intmax_t tmp;
	if (!parse_signed(str, INT_MAX, &tmp)) {
		return false;
	}
	*out = (int) tmp;
	return true;
}

bool read_size(const char *str, size_t *h, size_t *w, size_t *n) {
	errno = 0;
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "1000 1000 100000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(strtok(chomp(strncpy(s, str, sizeof(s))), " "), h)) {
		return false;
	} else if (*h < 1 || 1000 < *h) {
		errno = ERANGE;
		return false;
	}
	if (!parse_ulong(strtok(NULL, " "), w)) {
		return false;
	} else if (*w < 1 || 1000 < *w) {
		errno = ERANGE;
		return false;
	}
	if (!parse_ulong(strtok(NULL, " "), n)) {
		return false;
	} else if (*n < 1 || 100000 < *n) {
		errno = ERANGE;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_elements(const char *str, size_t w, int *a) {
	errno = 0;
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[strlen("-100 ") * w + 1];
	if (strlen(str) >= sizeof(s)) {
		errno = EINVAL;
		return false;
	}

	char *t = strtok(chomp(strncpy(s, str, sizeof(s))), " ");
	for (size_t i = 0; i < w; i++) {
		if (!parse_int(t, a + i)) {
			return false;
		} else if (a[i] < -100 || 100 < a[i]) {
			errno = ERANGE;
			return false;
		}
		t = strtok(NULL, " ");
	}
	if (t) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_query(const char *str, size_t h, size_t w, size_t *y, size_t *x) {
	errno = 0;
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "100000 100000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(strtok(chomp(strncpy(s, str, sizeof(s))), " "), y)) {
		return false;
	} else if (*y < 1 || h < *y) {
		errno = ERANGE;
		return false;
	}
	if (!parse_ulong(strtok(NULL, " "), x)) {
		return false;
	} else if (*x < 1 || w < *x) {
		errno = ERANGE;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}
テストコード

テストコードでは、

  • 範囲内の入力を通す
  • 範囲外の入力をはじく

ことをチェックします（以下のコードでは、不正文字のチェックは省略しておりますが）。

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <errno.h>
#include "minunit.h"
#include "input.h"

int tests_run = 0;

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* message_z(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* test_read_size(const char *str, size_t eh, size_t ew, size_t en) {
	size_t h, w, n;
	mu_assert("Error: expected: <true> but was: <false>", read_size(str, &h, &w, &n));
	mu_assert(message_z(eh, h), h == eh);
	mu_assert(message_z(ew, w), w == ew);
	mu_assert(message_z(en, n), n == en);
	return 0;
}

static char* test_read_size_invalid(const char *str) {
	size_t h, w, n;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &h, &w, &n));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_size_out_of_range(const char *str) {
	size_t h, w, n;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &h, &w, &n));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_size_0() {return test_read_size_invalid(NULL);}
static char* test_read_size_1() {return test_read_size_invalid("");}
static char* test_read_size_2() {return test_read_size_invalid("1");}
static char* test_read_size_3() {return test_read_size_invalid("1 1");}
static char* test_read_size_4() {return test_read_size_invalid("1 1 1 1");}
static char* test_read_size_5() {return test_read_size_out_of_range("0 1 1");}
static char* test_read_size_6() {return test_read_size_out_of_range("1 0 1");}
static char* test_read_size_7() {return test_read_size_out_of_range("1 1 0");}
static char* test_read_size_8() {return test_read_size("1 1 1", 1, 1, 1);}
static char* test_read_size_9() {return test_read_size("1000 1000 100000\n", 1000, 1000, 100000);}
static char* test_read_size_10() {return test_read_size_out_of_range("1001 1000 100000");}
static char* test_read_size_11() {return test_read_size_out_of_range("1000 1001 100000");}
static char* test_read_size_12() {return test_read_size_out_of_range("1000 1000 100001");}

static char* test_read_element(const char *str, size_t w, ...) {
    va_list args;
	int expected[w];
	va_start(args, w);
	for (size_t x = 0; x < w; x++) {
		expected[x] = va_arg(args, int);
	}
	va_end(args);
	int actual[w];
	mu_assert("Error: expected: <true> but was: <false>", read_elements(str, w, actual));
	mu_assert(message_d(0, errno), errno == 0);
	for (size_t x = 0; x < w; x++) {
		mu_assert(message_d(expected[x], actual[x]), actual[x] == expected[x]);
	}
	return 0;
}

static char* test_read_element_invalid(const char *str, size_t w) {
	int actual[w];
	mu_assert("Error: expected: <false> but was: <true>", !read_elements(str, w, actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_element_out_of_range(const char *str, size_t w) {
	int actual[w];
	mu_assert("Error: expected: <false> but was: <true>", !read_elements(str, w, actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_element_0() {return test_read_element_invalid(NULL, 0);}
static char* test_read_element_1() {return test_read_element("", 0);}
static char* test_read_element_2() {return test_read_element_invalid("\n", 0);}
static char* test_read_element_3() {return test_read_element_out_of_range("-101", 1);}
static char* test_read_element_4() {return test_read_element("-100\n", 1, -100);}
static char* test_read_element_5() {return test_read_element_invalid("-0", 1);}
static char* test_read_element_6() {return test_read_element_invalid("00", 1);}
static char* test_read_element_7() {return test_read_element("100", 1, 100);}
static char* test_read_element_8() {return test_read_element_out_of_range("101", 1);}
static char* test_read_element_9() {return test_read_element_invalid("", 1);}
static char* test_read_element_10() {return test_read_element_invalid("0", 0);}
static char* test_read_element_11() {return test_read_element("-100 -100\n", 2, -100, -100);}

static char* test_read_query(const char *str, size_t h, size_t w, size_t ey, size_t ex) {
	size_t y, x;
	mu_assert("Error: expected: <true> but was: <false>", read_query(str, h, w, &y, &x));
	mu_assert(message_d(0, errno), errno == 0);
	mu_assert(message_z(ey, y), y == ey);
	mu_assert(message_z(ex, x), x == ex);
	return 0;
}

static char* test_read_query_invalid(const char *str, size_t h, size_t w) {
	size_t y, x;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, h, w, &y, &x));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_query_out_of_range(const char *str, size_t h, size_t w) {
	size_t y, x;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, h, w, &y, &x));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_query_0() {return test_read_query_invalid(NULL, 0, 0);}
static char* test_read_query_1() {return test_read_query_invalid("", 0, 0);}
static char* test_read_query_2() {return test_read_query_invalid("1", 1, 1);}
static char* test_read_query_3() {return test_read_query_invalid("1 1 1", 1, 1);}
static char* test_read_query_4() {return test_read_query_out_of_range("0 1", 1, 1);}
static char* test_read_query_5() {return test_read_query_out_of_range("1 0", 1, 1);}
static char* test_read_query_6() {return test_read_query("1 1", 1, 1, 1, 1);}
static char* test_read_query_7() {return test_read_query_out_of_range("2 1", 1, 1);}
static char* test_read_query_8() {return test_read_query_out_of_range("1 2", 1, 1);}
static char* test_read_query_9() {return test_read_query("1000 1000\n", 1000, 1000, 1000, 1000);}
static char* test_read_query_10() {return test_read_query_out_of_range("1001 1000", 1000, 1000);}
static char* test_read_query_11() {return test_read_query_out_of_range("1000 1001", 1000, 1000);}

static char* all_tests() {
	mu_run_test(test_read_size_0);
	mu_run_test(test_read_size_1);
	mu_run_test(test_read_size_2);
	mu_run_test(test_read_size_3);
	mu_run_test(test_read_size_4);
	mu_run_test(test_read_size_5);
	mu_run_test(test_read_size_6);
	mu_run_test(test_read_size_7);
	mu_run_test(test_read_size_8);
	mu_run_test(test_read_size_9);
	mu_run_test(test_read_size_10);
	mu_run_test(test_read_size_11);
	mu_run_test(test_read_size_12);
	mu_run_test(test_read_element_0);
	mu_run_test(test_read_element_1);
	mu_run_test(test_read_element_2);
	mu_run_test(test_read_element_3);
	mu_run_test(test_read_element_4);
	mu_run_test(test_read_element_5);
	mu_run_test(test_read_element_6);
	mu_run_test(test_read_element_7);
	mu_run_test(test_read_element_8);
	mu_run_test(test_read_element_9);
	mu_run_test(test_read_element_10);
	mu_run_test(test_read_element_11);
	mu_run_test(test_read_query_0);
	mu_run_test(test_read_query_1);
	mu_run_test(test_read_query_2);
	mu_run_test(test_read_query_3);
	mu_run_test(test_read_query_4);
	mu_run_test(test_read_query_5);
	mu_run_test(test_read_query_6);
	mu_run_test(test_read_query_7);
	mu_run_test(test_read_query_8);
	mu_run_test(test_read_query_9);
	mu_run_test(test_read_query_10);
	mu_run_test(test_read_query_11);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

echo off
gcc -Wall -Wextra -Werror -std=c99 inputTest.c input.c -o inputTest 1>inputTest.txt 2>&1
if exist inputTest.exe (
	.\inputTest
	echo %ERRORLEVEL%
	del inputTest.exe
	del inputTest.txt
) else (
	type inputTest.txt
)
pause

エントリポイント

以上の関数やクラスを使って、main関数を書いていきます。以下のコードでは、

  • 時間計測用のデバッグコード
  • 本番用のコード

を、NDEBUGを使って切り替えられるように書いております。

#include <stdio.h>
#include <stdlib.h>
#include "IntArray2.h"
#include <errno.h>
#ifdef NDEBUG
#include <string.h>
#include "input.h"
#else
#include <time.h>
#define PRINT(fmt, ...) \
	do { \
		fprintf(stderr, fmt, ##__VA_ARGS__); \
		fflush(stderr); \
	} while (0)
#endif

int main() {
#ifndef NDEBUG
	clock_t clockt = clock();
#endif
	size_t H, W, N;
#ifdef NDEBUG
	do {
		char s[] = "1000 1000 100000\n";
		if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
			for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
		} else {
			if (read_size(s, &H, &W, &N)) {
				break;
			}
		}
		perror("The number of rows must be an integer between 1 and 1000.\n"
		       "The number of columns must be an integer between 1 and 1000.\n"
		       "The number of queries must be an integer between 1 and 100000.");
	} while (true);
#else
	H = 1000;
	W = 1000;
	N = 100000;
#endif
	// int A[H][W];
	int *A[H];
	for (size_t i = 0; i < H; i++) {
		A[i] = calloc(W, sizeof(A[i][0]));
#ifdef NDEBUG
		do {
			char s[strlen("-100 ") * W + 1];
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				if (read_elements(s, W, A[i])) {
					break;
				}
			}
			fprintf(stderr, "The number of elements must be %zu.\n", W);
			perror("The element must be an integer between -100 and 100.");
		} while (true);
#else
		for (size_t j = 0; j < W; j++) {
			A[i][j] = (int) (i * W + j) % 201 - 100;
		}
#endif
	}
	IntArray2 *intArray2 = new_IntArray2(H, W, (const int**)A);
	if (!intArray2) {
		return errno;
	}
	while (N--) {
		size_t y, x;
#ifdef NDEBUG
		do {
			char s[] = "1000 1000\n"; 
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				if (read_query(s, H, W, &y, &x)) {
					break;
				}
			}
			fprintf(stderr, "The row number must be an integer between 1 and %zu.\n", N);
			fprintf(stderr, "The column number must be an integer between 1 and %zu.\n", W);
			perror(NULL);
		} while (true);
#else
		y = (99999 - N) * H / 100000 + 1;
		x = (99999 - N) % W + 1;
#endif
		int sum;
		if (!intArray2->cumulative_sum(intArray2, y, x, &sum)) {
			int e = errno;
			perror(NULL);
			return e;
		}
		printf("%d\n", sum);
	}
	free_IntArray2(&intArray2);
	for (size_t i = H; i; i--) {
		free(A[~-i]);
	}
#ifndef NDEBUG
	PRINT("%f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}

以下、時間計測用のバッチファイルです。

echo off
gcc -Wall -Wextra -Werror -std=c99 main.c IntArray2.c -o main 1>main.txt 2>&1
if exist main.exe (
	for /l %%i in (0,1,9) do (
		.\main 1>nul
	)
	del main.exe
	del main.txt
) else (
	type main.txt
)
pause
テストコード

もはや“単体”テストではありませんが、main関数のテストコード及びテスト実行バッチファイルを、以下のように書くこともできます。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
#include "minunit.h"
#define SOURCE "main"
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define ERR_FILE "err.txt"

int tests_run = 0;
char result[100000][12];

static char* message_u(size_t expected, size_t actual) {
	static char msg[72];
	sprintf(msg, "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_s(const char *expected, const char *actual) {
	static char msg[72];
	sprintf(msg, "Error: expected: <%s> but was: <%s>", expected, actual);
	return msg;
}

static size_t test(size_t n, const char *lines[]) {
	static unsigned k = 0;
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t start = clock();
	if (!!(errno = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	fprintf(stderr, "#%u %f sec\n", ++k, (float) (clock() - start) / CLOCKS_PER_SEC);
	fflush(stderr);
	if (!(file = fopen(OUT_FILE, "r"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	size_t m = 0;
	while (fgets(result[m], sizeof(result[m]), file)) m++;
	fclose(file);
	return m;
}

static char* test0() {
	const char *lines[] = { "1 1 1", "0", "1 1" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("0\n", result[0]), !strcmp(result[0], "0\n"));
	return 0;
}

static char* test1() {
	const char *lines[] = { "3 3 3", "1 2 3", "4 5 6", "7 8 9", "1 1", "2 2", "3 3" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("1\n", result[0]), !strcmp(result[0], "1\n"));
	mu_assert(message_s("12\n", result[1]), !strcmp(result[1], "12\n"));
	mu_assert(message_s("45\n", result[2]), !strcmp(result[2], "45\n"));
	return 0;
}

static char* test2() {
	const char *lines[] = { "3 3 3",
		"-76 -44 61", "-72 30 95", "99 42 82",
		"3 3", "1 1", "3 1" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("217\n", result[0]), !strcmp(result[0], "217\n"));
	mu_assert(message_s("-76\n", result[1]), !strcmp(result[1], "-76\n"));
	mu_assert(message_s("-49\n", result[2]), !strcmp(result[2], "-49\n"));
	return 0;
}

static char* test3() {
	const char *lines[] = {
		"1000  1000  100000", "1001 1001 100001", 
		"000000000000000001 1 1", "0 0 0", "1 1", "1 1 1 1", "2 2 4",
		"-100  -100", "-101 -101", "101 101", "0", "0 0 0", "1 -2", "-3 4",
		"0 0", "3 3", "1", "1 1 1", "1 1", "1 2", "2 1", "2 2"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(4, n), n == 4);
	mu_assert(message_s("1\n", result[0]), !strcmp(result[0], "1\n"));
	mu_assert(message_s("-1\n", result[1]), !strcmp(result[1], "-1\n"));
	mu_assert(message_s("-2\n", result[2]), !strcmp(result[2], "-2\n"));
	mu_assert(message_s("0\n", result[3]), !strcmp(result[3], "0\n"));
	return 0;
}

static char* test4() {
	char *lines[101001] = { };
	size_t k = 0;
	lines[k] = (char*) calloc(-~strlen("1000 1000 100000"), sizeof(char));
	if (!lines[k]) {
		return strerror(errno);
	}
	strcpy(lines[k++], "1000 1000 100000");
	for (size_t i = 0; i < 1000; i++) {
		lines[k] = (char*) calloc(strlen("-100 ") * 1000, sizeof(char));
		if (!lines[k]) {
			int e = errno;
			while (k--) {
				free(lines[k]);
			}
			return strerror(e);
		}
		strcpy(lines[k], "-100");
		for (size_t j = 1; j < 1000; j++) {
			strcat(lines[k], " -100");
		}
		k++;
	}
	for (size_t i = 0; i < 100000; i++) {
		lines[k] = (char*) calloc(-~strlen("1000 1000"), sizeof(char));
		if (!lines[k]) {
			int e = errno;
			while (k--) {
				free(lines[k]);
			}
			return strerror(e);
		}
		size_t y = i / 100;
		size_t x = (i * 10 + y % 10) % 1000;
		sprintf(lines[k], "%zu %zu", -~y, -~x);
		k++;
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_u(100000, n), n == 100000);
	for (size_t i = 0; i < 100000; i++) {
		char expected[] = "-100000000\n";
		size_t y = i / 100;
		size_t x = (i * 10 + y % 10) % 1000;
		snprintf(expected, sizeof(expected), "-%zu00\n", -~y * -~x);
		mu_assert(message_s(expected, result[i]), !strcmp(result[i], expected));
	}
	while (k--) {
		free(lines[k]);
	}
	return 0;
}

static char* all_tests() {
	mu_run_test(test0);
	mu_run_test(test1);
	mu_run_test(test2);
	mu_run_test(test3);
	mu_run_test(test4);
	return 0;
}

int main() {
	if (!!(errno = system("gcc -Wall -Wextra -Werror -DNDEBUG -std=c99 " SOURCE ".c IntArray2.c input.c -o " SOURCE " 1>" SOURCE ".txt 2>&1"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		FILE* file = fopen(SOURCE ".txt", "r");
		if (file) {
			int c = 0;
			while ((c = fgetc(file)) != EOF) {
				putchar(c);
			}
			fclose(file);
		}
		return errno;
	}
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	remove(ERR_FILE);
	remove(OUT_FILE);
	remove(IN_FILE);
	remove(SOURCE ".exe");
	remove(SOURCE ".txt");
	if (errno) {
		return errno;
	} else {
		return result != 0;
	}
}

echo off
gcc -Wall -Wextra -Werror -std=c99 test.c -o test 1>test.txt 2>&1
if exist test.exe (
	.\test
	echo %ERRORLEVEL%
	del test.exe
	del test.txt
) else (
	type test.txt
)
pause
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?