プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【RCO】日本橋ハーフマラソン予選 A問題

AtCoderで開催された日本橋ハーフマラソンの予選のA問題です.
A問題に時間をかけすぎてBが悲惨なことになりました.
ちなみに予選115位でした…

A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

問題概要

・50*50のマスに0~9の数字が書いてある
・9個の連結したマスを1グループとする
・グループ内の数同士の掛け算をそのグループの得点とする
・全てのグループの得点の和が最終的なスコア
・スコアを最大化するようにグループを作ってください

方針

・なるべく大きい数同士同じグループにしたい
と思ったので、実装しやすそうな9の周りから大きい数字を選んで行くという方法をとりました。

実装例

焦って書いたコードなので汚いです.
このコードだとA問題だけでは75位でした.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int H, W, K;
vector<string> inputmass;
int mass[51][51];
bool used[51][51];
typedef pair<int, int> YX;//座標
typedef pair<int, YX> P;//値,座標

int main(){
    cin >> H >> W >> K;
    cin.ignore();
    FOR(i, 0, H){
        string s;
        getline(cin, s);
        inputmass.push_back(s);
    }
    FOR(i, 1, 51){
        FOR(j, 1, 51){
            mass[i][j] = inputmass[i-1][j-1] - '0';
        }
    }
    //連結できるならqueに入れておく
    //4方向を見る
    int vx[4] = {0, 1, 0, -1};
    int vy[4] = {-1, 0, 1, 0};
    priority_queue<P> que;
    stack<YX> output;
    int C = 0;
    //9の周りでグループ作る->8の周りで->...
    for(int num = 9; num > 0; --num){
    FOR(yi, 1, H+1){
        FOR(xi, 1, W+1){
            //すでに使われていたらもしくわnum(9->8->7->...)でなければcontinue
            if(used[yi][xi]==true || mass[yi][xi] != num) continue;
            while(!que.empty()) que.pop();
            que.push(P(mass[yi][xi],YX(yi, xi)));
            used[yi][xi] = true;
            //queの周りを調べる
            //0出なければ連結させる
            int k = 0;//グループ内の数の個数-1
            while(1){
                if(k==8){
                    C++;
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;//あまりは戻す
                    }
                    break;
                }
                //8個できるまでに連結できなかったら戻す
                if(que.empty()){
                    FOR(kesu, 0, k){
                        YX yx = output.top();output.pop();
                        used[yx.first][yx.second] = false;//グループにできてないので戻す
                    }
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;
                    }
                    break;
                }
                //使うところを保存
                P p = que.top();que.pop();
                output.push(p.second);//あとで出力する
                k++;
                //周りを調べる
                int y0 = p.second.first;
                int x0 = p.second.second;
                FOR(vi, 0, 4){
                    if(y0 + vy[vi] <= 0 || y0 + vy[vi] > H || x0 + vx[vi] <= 0 || x0 + vx[vi] > W) continue;
                    if(mass[y0+vy[vi]][x0+vx[vi]]==0 || used[y0+vy[vi]][x0+vx[vi]]==true) continue;
                    que.push(P(mass[y0+vy[vi]][x0+vx[vi]],YX(y0+vy[vi], x0+vx[vi])));
                    used[y0+vy[vi]][x0+vx[vi]] = true;
                }
            }
        }
    }
    }
    cout << C << endl;
    while(!output.empty()){
        YX yx = output.top();output.pop();
        cout << yx.first << " " << yx.second << endl;
    }
}

コメント

1個隣だけでなく何個か先も見て得点が大きくなる場合を探す方法でやってみようと思います。