Chokudai Contest 001 - Matchaldの日記

問題概要

$30 \times 30$ のマスがあり、あるマスには1以上100以下の整数が書かれている。
すべてのマスを0にするまで以下の動作を続ける。
①あるマスの値を1減らす
②そのマスの上下左右いずれかのマスが今いるマスの値と同じ時、そのマスに移動し①を実行する。そのようなマスがなければその手は終了。

このときに、手数がなるべく少なくなるような選び方をする。

1回目のコード

すべてのマスの中で一番大きい数のマスを選び①を実行していく戦法。
これで、758559点。

#include<iostream>
#include<vector>
#include<algorithm>
 
void re(std::vector<int> &table, int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1<< std::endl;
	table[pos]--;
	if (pos - 30 >= 0 && table[pos - 30] != 0 && table[pos - 30] == table[pos]) re(table, pos - 30);
	if (pos + 30 < 900 && table[pos + 30] != 0 && table[pos + 30] == table[pos]) re(table, pos + 30);
	if (pos % 30 > 0 && table[pos - 1] != 0 && table[pos - 1] == table[pos]) re(table, pos - 1);
	if (pos % 30 < 29 && table[pos + 1] != 0 && table[pos + 1] == table[pos]) re(table, pos + 1);
}
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				re(table, i);
			}
		}
	}
}

2回目のコード

1回目のコードの関数内でelse ifにするべきところをifにしていたので修正。
この修正で、809699点。

#include<iostream>
#include<vector>
#include<algorithm>
 
void output(int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1 << std::endl;
}
 
void re(std::vector<int> &table, int pos) {
	output(pos);
	table[pos]--;
	if (pos - 30 >= 0 && table[pos - 30] != 0 && table[pos - 30] == table[pos]) re(table, pos - 30);
	else if (pos + 30 < 900 && table[pos + 30] != 0 && table[pos + 30] == table[pos]) re(table, pos + 30);
	else if (pos % 30 > 0 && table[pos - 1] != 0 && table[pos - 1] == table[pos]) re(table, pos - 1);
	else if (pos % 30 < 29 && table[pos + 1] != 0 && table[pos + 1] == table[pos]) re(table, pos + 1);
}
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				re(table, i);
			}
		}
	}
}

最終的なコード

1回目の戦法に加えて、1手のうちでたくさんのマスの値を減らすことができる方法を探索して、それを実行するコードに変更
これで、815109点。

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
 
void output(int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1 << std::endl;
}
 
int max_nest = 0;
std::vector<int> order;
void re(std::vector<int> table, int pos, int nest, std::vector<int> o) {
	o.push_back(pos);
	if (max_nest < nest) {
		max_nest = nest;
		order = o;
	}
	if (table[pos] == 1) return;
	table[pos]--;
 
	if (pos - 30 >= 0 && table[pos - 30] == table[pos]) {
		re(table, pos - 30, nest + 1, o);
	} 
	if (pos + 30 < 900 && table[pos + 30] == table[pos]) {
		re(table, pos + 30, nest + 1, o);
	}
	if (pos % 30 > 0 && table[pos - 1] == table[pos]) {
		re(table, pos - 1, nest + 1, o);
	}
	if (pos % 30 < 29 && table[pos + 1] == table[pos]) {
		re(table, pos + 1, nest + 1, o);
	}
}
 
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				std::vector<int> o;
				re(table, i, 1, o);
				for (int j : order) {
					output(j);
					table[j]--;
				}
				max_nest = 0;
			}
		}
	}
}

結果と感想

6時半ごろに参戦して最終結果は815109点で97位でした。

30行程度でも750000点位だせたので、モチベ高く取り組むことができた。
コードを修正して良くなった、悪くなったがすぐにわかるので点数が上がった時の喜びで
もっと良いコードにするぞ感がまして初心者にはとっつきやすかったのではないかと思う。