Submission #71090490

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define INF INT64_C(101010101010101010)
int N;
int a[18][18];
#if 1
#if 1
#define USE_POOL
#endif
#define MOD_BY 95295899
#define MULT 13790611
#ifdef USE_POOL
struct memo_s {
  int64_t ans;
  uint32_t query;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define INF INT64_C(101010101010101010)

int N;
int a[18][18];

#if 1
#if 1
#define USE_POOL
#endif

#define MOD_BY 95295899
#define MULT 13790611

#ifdef USE_POOL
struct memo_s {
	int64_t ans;
	uint32_t query;
	int next;
};

#define STATUS_MAX 51234567

int pool_pos = 1;
struct memo_s pool[STATUS_MAX];

int memo[MOD_BY];
#else
struct memo_s {
	int cur, left;
	int64_t ans;
	struct memo_s* next;
};

struct memo_s* memo[MOD_BY];
#endif

int64_t* get_memo(int cur, int left) {
	int hash = (int)(((long long)cur * MULT + left) % MOD_BY);
#ifdef USE_POOL
	uint32_t query = ((uint32_t)cur << 16) | (uint32_t)left;
	int* pmemo = &memo[hash];
	while (*pmemo > 0) {
		if (pool[*pmemo].query == query) {
			return &pool[*pmemo].ans;
		}
		pmemo = &pool[*pmemo].next;
	}
	if (pool_pos >= STATUS_MAX) {
		puts("ERROR: too many status!");
		exit(42);
	}
	*pmemo = pool_pos++;
	pool[*pmemo] = (struct memo_s){ -INF, query, 0 };
	return &pool[*pmemo].ans;
#else
	struct memo_s** pmemo = &memo[hash];
	while (*pmemo != NULL) {
		if ((*pmemo)->cur == cur && (*pmemo)->left == left) {
			return &(*pmemo)->ans;
		}
		pmemo = &(*pmemo)->next;
	}
	*pmemo = malloc(sizeof(**pmemo));
	if (*pmemo == NULL) exit(2);
	**pmemo = (struct memo_s){ cur, left, -INF, NULL };
	return &(*pmemo)->ans;
#endif
}
#elif 0
int64_t* memos[1 << 18];

int64_t* get_memo(int cur, int left) {
	int zerocnt = 0, cur2 = 0;
	int i;
	for (i = 0; i < N; i++) {
		if (((left >> i) & 1) == 0) {
			cur2 |= ((cur >> i) & 1) << zerocnt;
			zerocnt++;
		}
	}
	if (memos[left] == NULL) {
		memos[left] = calloc(1 << zerocnt, sizeof(*memos[left]));
		if (memos[left] == NULL) exit(2);
		for (i = 0; i < (1 << zerocnt); i++) memos[left][i] = -INF;
	}
	return &memos[left][cur2];
}
#else
#define STATUS_MAX 51234567

int cmp(const void* x, const void* y) {
	uint32_t a = *(const uint32_t*)x, b = *(const uint32_t*)y;
	return (a > b) - (a < b);
}

int status_cnt = 0;
uint32_t status_list[STATUS_MAX];

int64_t memo[STATUS_MAX];

int64_t* get_memo(int cur, int left) {
	int l, r;
	uint32_t query;
	if (status_cnt == 0) {
		int i, j, k;
		for (i = 0; i < (1 << N); i++) {
			int zeros[18], zerocnt = 0;
			for (j = 0; j < N; j++) {
				if (((i >> j) & 1) == 0) zeros[zerocnt++] = j;
			}
			for (j = 0; j < (1 << zerocnt); j++) {
				uint32_t x = 0;
				for (k = 0; k < zerocnt; k++) {
					x |= ((j >> k) & 1) << zeros[k];
				}
				if (status_cnt >= STATUS_MAX) {
					puts("ERROR: too many status!");
					exit(42);
				}
				status_list[status_cnt++] = (x << 16) | (uint32_t)i;
			}
		}
		qsort(status_list, status_cnt, sizeof(*status_list), cmp);
		for (i = 0; i < status_cnt; i++) memo[i] = -INF;
	}
	l = 0;
	r = status_cnt - 1;
	query = ((uint32_t)cur << 16) | (uint32_t)left;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (status_list[m] == query) return &memo[m];
		else if (status_list[m] < query) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: cur = %d, left = %d not found!\n", cur, left);
	exit(72);
}
#endif

int64_t score_cache[1 << 18];

int poscnt[1 << 18];
int poses[1 << 18][18];

int64_t calc(int cur, int left) {
	if (cur == 0 && left == 0) {
		return 0;
	} else {
		int64_t ans = -INF;
		int64_t *pmemo = get_memo(cur, left);
		int i, j;
		if (*pmemo > -INF) return *pmemo;
		/* 精算する */
		if (cur != 0) {
			if (score_cache[cur]) {
				ans = ~score_cache[cur];
			} else {
				ans = 0;
				for (i = 0; i < N; i++) {
					if ((cur >> i) & 1) {
						for (j = i + 1; j < N; j++) {
							if ((cur >> j) & 1) ans += a[i][j];
						}
					}
				}
				score_cache[cur] = ~ans;
			}
			ans += calc(0, left);
		}
		/* グループに追加する */
		for (i = 0; i < poscnt[left] && (cur != 0 || i < 1); i++) {
			int64_t candidate = calc(cur | (1 << poses[left][i]), left & ~(1 << poses[left][i]));
			if (candidate > ans) ans = candidate;
		}
		return *pmemo = ans;
	}
}

int main(void) {
	int i, j;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (scanf("%d", &a[i][j]) != 1) return 1;
		}
	}
	for (i = 0; i < (1 << N); i++) {
		for (j = 0; j < N; j++) {
			if ((i >> j) & 1) {
				poses[i][poscnt[i]++] = j;
			}
		}
	}
	printf("%" PRId64 "\n", calc(0, (1 << N) - 1));
	return 0;
}

/*

メモ化探索をする

状態：
* cur：現在のグループに入っているうさぎの集合
* left：まだグループに入っていないうさぎの集合

行動の選択肢：
* 現在のグループを確定し、精算する
* 現在のグループにうさぎを1羽選んで入れる

そのままやると (1<<16) * (1<<16) で死にそうだけど、
curとleftは被らないので……まあなんとかなるやろ (雑)

>>> cnt = 0
>>> for i in range(1<<16):
...  cc = 0
...  for j in range(16):
...   if ((i >> j) & 1) != 0:
...    cc += 1
...  cnt += 1 << cc
...
>>> cnt
43046721

試してみるとうまくいかない
なんか枝を刈るべき
→ cur が空のとき、必ず最初の left をグループに入れる

*/

Submission Info

Judge Result