Chokudai Contest 001

• 問題

30x30のマスに1以上100以下の値がランダムに与えられて、マスを選択して1づつ減らしていく。

全部のマスを0にしたら終わりで手数が少ないと良いスコアがもらえる。

減らしたマスの上下左右の同じ値のマスの値を減らすときは手数は数えない。

(日本語下手)

最初に「全探索して一番つなげて消せるラインを減らしていけばいける？」って思って書いた。。。

普通にTLE(当たり前)。

そのあと「一番大きな値から減らしていけばいいんでは？？」ってなって最大のスコア-2までのマスを全探索して一番長いルートになるやつを消していくやつを書いた。

それでスコアは、83万弱で43位だった(2ページ目に載りたかった)。

自分はマラソン系の方が好きかも。。。

ダイコンが定期的になったらすっっっごい嬉しいです＞＜

• コード

#include <bits/stdc++.h>
using namespace std;

const int DIRX[4] = {0,0,1,-1};
const int DIRY[4] = {1,-1,0,0};

class banmen{
public:
	int point[40][40];
	int nx,ny;
};

int hyo[40][40] = {};

int main() {
	for(int i = 0;i < 30;i++){
		for(int j = 0;j < 30;j++){
			cin >> hyo[j][i];
		}
	}
	bool all_not_zero = true;
	while(all_not_zero){
		all_not_zero = false;
		int max_p = 0,max_x = 0,max_y = 0;
		for(int i = 0;i < 30;i++){
			for(int j = 0;j < 30;j++){
				if(hyo[j][i] != 0) all_not_zero = true;
				if(max_p < hyo[j][i]){
					max_p = hyo[j][i];
					max_x = j;
					max_y = i;
				}
			}
		}
		queue<pair<int,int> > que;
		for(int i = 0;i < 30;i++){
			for(int j = 0;j < 30;j++){
				if(hyo[j][i] >= max_p - 2){
					que.push(make_pair(j,i));
				}
			}
		}

		vector<pair<int,int> > best_ans;
		while(que.size()){
			banmen hyo2;
			for(int i = 0;i < 30;i++){
				for(int j = 0;j < 30;j++){
					hyo2.point[j][i] = hyo[j][i];
				}
			}
			hyo2.nx = que.front().first;
			hyo2.ny = que.front().second;
			vector<pair<int,int> > ans;
			que.pop();
			queue<pair<banmen,vector<pair<int,int> > > > que2;
			que2.push(make_pair(hyo2,ans));
			while(que2.size()){
				banmen hyo_now = que2.front().first;
				vector<pair<int,int> > ans_now = que2.front().second;
				que2.pop();
				int dx = hyo_now.nx;
				int dy = hyo_now.ny;
				if(hyo_now.point[dx][dy] == 0) continue;
				hyo_now.point[dx][dy]--;
				ans_now.push_back(make_pair(dy,dx));
				if(ans_now.size() > best_ans.size()){
					best_ans = ans_now;
				}
				if(hyo_now.point[dx][dy] == 0) continue;
				for(int i = 0;i < 4;i++){
					if(dx + DIRX[i] < 0 || dx + DIRX[i] >= 30 || dy + DIRY[i] < 0 || dy + DIRY[i] >= 30) continue;
					if(hyo_now.point[dx][dy] == hyo_now.point[dx + DIRX[i]][dy + DIRY[i]]){
						hyo_now.nx = dx + DIRX[i];
						hyo_now.ny = dy + DIRY[i];
						que2.push(make_pair(hyo_now,ans_now));
						hyo_now.nx = dx;
						hyo_now.ny = dy;
					}
				}
			}
		}
		for(int i = 0;i < best_ans.size();i++){
			cout << best_ans[i].first + 1 << " " << best_ans[i].second + 1 << endl;
			hyo[best_ans[i].second][best_ans[i].first]--;
		}
	}
	return 0;
}

マラソン系も頑張るぞい