Submission #2070102


Source Code Expand

#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
using namespace std;

/*
第1回実装方針:
9を中心にピースを創れば多分早いでしょ

第2回実装方針:
9~4を中心にしてみた<-本番でやるならここまでが多分限界

第3回実装方針:
でぃーぷらーにんぐで、評価関数ってものがあった。使ってみよう。
そして、上位から使えるだけ使って、answerに入れよう

第4回実装方針:
上位A個だけ使うのをB回ループさせたらどうなるんだろ
(時間ギリギリを狙う)
*/

//サイトにある通りの変数
int H, W, K;
vector<vector<int>> s;


//自作変数
vector<pair<int,vector<pair<int, int>>>> candidate;//答えの候補を格納する
vector<vector<pair<int,int>>> answer;//答えを格納する

//サブ関数
//入力
void input()
{
	//入力1行目
	cin >> H >> W >> K;

	//入力2行目以降
	string tmpS;
	for (int i = 0; i < H; i++) {
		vector<int> tmpV;
		cin >> tmpS;
		for (int j = 0; j < W; j++) {
			//注:stringから1文字だけ取り出すと、char型なので
			tmpV.push_back(tmpS[j] - '0');
		}
		s.push_back(tmpV);//お姉ちゃんが忘れちゃったところ
	}
}


//最大値だったら更新する
void update_max_data(
	int& tmpMax,
	pair<int, int>& tmpMaxSq,
	const pair<int, int>& nextSq,
	const vector<vector<bool>>& used
)
{
	if (s[nextSq.first][nextSq.second] > tmpMax && used[nextSq.first][nextSq.second] == false) {
		tmpMax = s[nextSq.first][nextSq.second];
		tmpMaxSq = nextSq;
	}
}

//既にあるpieceに対して縦か横で隣り合ってるマス目のうち、最大値を持つマス目の座標を返す
pair<int, int> find_best_square(const vector<pair<int, int>>& piece, const vector<vector<bool>>& used)
{
	int tmpMax = -1;//付近にあるマス目の暫定的最大値です
	pair<int, int> tmpMaxSq = make_pair(-1, -1);//暫定的最大値の座標です

												//実装面倒くさいので、毎回ピースの各要素の、上下左右見ちゃおう(TLEしたら直す)
	for (auto nextSq : piece) {
		//上
		if (0 < nextSq.first) {//そもそも上がある
			nextSq.first--;//上の座標に調整
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.first++;//元に戻す
		}
		//以下、上のを少しいじっただけ
		//下
		if (nextSq.first < H - 1) {
			nextSq.first++;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.first--;
		}
		//左
		if (0<nextSq.second) {
			nextSq.second--;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.second++;
		}
		//右
		if (nextSq.second < W - 1) {
			nextSq.second++;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.second--;
		}
	}
	return tmpMaxSq;
}

//点数計算
int calcScore(vector<pair<int,int>> piece) 
{
	int ans = 1;
	for (auto square : piece) {
		ans *= s[square.first][square.second];
	}
	return ans;
}


//座標(x,y)の近くにある、大きい数字が書かれたマスを一緒にして、ピースにしよう
void make_piece(int y, int x) 
{
	vector<vector<bool>> used(H, vector<bool>(W, false));//今回はローカルに作ります
	vector<pair<int, int>> piece;//新しく作るピースの内容

	//(x,y)は使用することを( ..)φメモメモ
	piece.push_back(make_pair(y, x));
	used[y][x] = true;
	
	//既に1個は決まってるので、残り7個必要です
	for (int i = 0; i < 7; i++) {
		//新しくピースの仲間入りをするマス目の座標です。
		pair<int, int> newSquare = find_best_square(piece,used);

		//ピースが作れなさそうなら無視しよう
		if (newSquare.first == -1)return;

		//仲間入りしたので、( ..)φメモメモ
		piece.push_back(newSquare);
		used[newSquare.first][newSquare.second] = true;
	}

	//ピースが決まったので、候補に入れよう
	candidate.push_back(make_pair(calcScore(piece), piece));
}

//既に使われてるマスと被ってたら無視
bool check_over(const vector<pair<int, int>>& piece, const vector<vector<bool>>& used) 
{
	for (auto square : piece) {
		if (used[square.first][square.second]) {
			return true;
		}
	}
	return false;
}

//計算
void calc()
{
	vector<vector<bool>> used(H, vector<bool>(W, false));//answerに既に入れちゃったマス目はtrue
	
	//ほな次、9じゃないやつもやったらどうなるんやろ
	for (int k = 9; k > 6; k--) {
		//全部のマス目に着目する
		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				//マスの積がスコアなんやろ?なら一番大きいやつを中心にピース作ろうや
				if (s[y][x] == k) {
					make_piece(y, x);
				}
			}
		}
	}

	//候補をソートして、スコアの高い順に採用するで
	sort(candidate.begin(), candidate.end());
	reverse(candidate.begin(), candidate.end());
	for (auto piece : candidate) {
		//cout << piece.first << endl;
		//もし被ってたら無視
		if (check_over(piece.second, used))continue;

		//被ってないなら採用
		answer.push_back(piece.second);
		for (auto square : piece.second) {
			used[square.first][square.second] = true;
		}
	}
}


//出力
void output()
{
	//ピースの数を出力する
	cout << (int)answer.size() << endl;

	//それぞれのピースについて出力を行う
	for (auto piece : answer) {
		//各ピースに所属するマス目について、それぞれ出力を行う
		for (auto square : piece) {
			//フォーマットは、(y座標)(スペース)(x座標)
			cout << square.first+1 << " " << square.second+1 << endl;
		}
	}
}

//メイン関数
int main()
{
	input();
	calc();
	output();
	int N;
	cin >> N;
	return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User toma25
Language C++14 (GCC 5.4.1)
Score 833453
Code Size 6012 Byte
Status AC
Exec Time 10 ms
Memory 384 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 86902 / 1343058 80287 / 1343058 85208 / 1343058 80441 / 1343058 88086 / 1343058 78936 / 1343058 83072 / 1343058 79639 / 1343058 87491 / 1343058 83391 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 10 ms 384 KB
subtask_01_02.txt AC 9 ms 384 KB
subtask_01_03.txt AC 10 ms 384 KB
subtask_01_04.txt AC 9 ms 384 KB
subtask_01_05.txt AC 10 ms 384 KB
subtask_01_06.txt AC 10 ms 384 KB
subtask_01_07.txt AC 10 ms 384 KB
subtask_01_08.txt AC 10 ms 384 KB
subtask_01_09.txt AC 10 ms 384 KB
subtask_01_10.txt AC 10 ms 384 KB