AtCoder ABC 384 E - Takahashi is Slime 2

はじめてコンテスト中に、4完の後、5問目の解法までたどり着いたけど、時間切れで実装しきれなかったのが悔しかったので、やりたかった解法があっているのか確認するために実装したコードを晒しておきます。

考えたこと

• （入力例 1の解説を見ながら）高橋くんの強さの上がり方は単純な加算だから、取り込むスライムの順は関係ありません、と
• ということは、単純に一番弱いスライムを取り込んでいって、まったく取り込めなくなったら終了でいいかな？
• （しばらく考察）うん、問題に「ありえる最大値」とはあるけど、複数のケースから最大値を探すとかは必要なくて、単純にいくつまで強くなるか考えればいいやつ
• 基本の BFS の queue を priority_queue に変えて、何もできなくなったら終了するようにすればいいかな
• （入力例3が WA になったのでログ入れて観察） ああ、吸収済みのマスの情報が前に別の契機でキューに入っちゃってるパターンがあるのか
• 面倒くさいから、吸収済みのマスの情報が出てきたらスキップすればいいや

↑ 脳内の高橋くんのイメージ(諸星大二郎『生物都市』より)

サンプルコード

Main.cpp

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

// フロア  マスにはスライムの強さ
//  高橋くん吸収済み: -1
//  未使用マス      : LLONG_MAX
ll gFloor[509][509];

// スライム
struct Slime
{
	int p;		// いる座標
	int q;		// いる座標
	ll power;	// 強さ
};


int main( void )
{
	// フロアの状態を初期化
	//  使っていない部分が高橋くんに吸収されないように
	//  極大の値を入れておく
	for( int i = 0; i < 509; ++i)
	{
		for( int j = 0; j < 509; ++j)
		{
			gFloor[i][j] = LLONG_MAX;
		}
	}

	// 入力
	int H, W, X, P, Q;
	cin >> H >> W >> X >> P >> Q;
	for( int i = 1; i <= H; ++i)
	{
		for( int j = 1; j <= W; ++j)
		{
			cin >> 	gFloor[i][j];
		}
	}

	// BFS もどきを実施
	// 高橋くんの初期化
	ll takaPower = gFloor[P][Q];
	gFloor[P][Q] = -1;

	// priority_queue に弱い順に並べてもらうための比較関数
	auto CompSlime = [](const Slime & a, const Slime & b)
	{
		return a.power > b.power;
	};

	// スライムを弱い順に取り出すためのキュー
	priority_queue<Slime, vector<Slime>, decltype(CompSlime)> pq(CompSlime);

	// 最初に隣あっているスライムをキューに突っ込む
	//  ちゃんとコーディングすれば下のループの中に入れられると思うけど混乱するので(*'ω'*)
	vector<pair<int, int>> vecMove = {{-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	for( size_t i = 0; i < vecMove.size(); ++i)
	{
		int next_p = P + vecMove[i].first;
		int next_q = Q + vecMove[i].second;

		if( gFloor[next_p][next_q] != -1 )
		{
			pq.push( {next_p, next_q, gFloor[next_p][next_q]});
		}
	}

	// キューが空になるまでループ
	while( ! pq.empty())
	{
		// 先頭の一番弱いスライムを取り出し
		Slime now = pq.top();
		pq.pop();

		// 隣接しているスライムで一番弱いものが吸収できなかったら終了
		if( now.power >= (long double)takaPower / X )
		{
			break;
		}

		// 吸収済みのものが出てきてしまったらスキップ
		if( gFloor[now.p][now.q] == -1 )
		{
			continue;
		}

		// 一番弱いスライムを吸収する
		takaPower += now.power;
		gFloor[now.p][now.q] = -1;

		// 吸収したスライムの隣のマスの情報を突っ込む
		for( size_t i = 0; i < vecMove.size(); ++i)
		{
			int next_p = now.p + vecMove[i].first;
			int next_q = now.q + vecMove[i].second;

			// 吸収済みのマスは入れない
			if( gFloor[next_p][next_q] != -1 )
			{
				pq.push( {next_p, next_q, gFloor[next_p][next_q]});
			}
		}
	}

	cout << takaPower << endl;
	return 0;
}

追記：混ぜるな危険（浮動小数点演算）

解説放送を拝見してヒヤッとしたので、念のため追記。

基本的に整数を扱っている処理中での割り算は、できるだけ掛け算に変換して比較してやったほうが良いです。わかってはいたんだけど、なんとなく倍精度(80bit浮動小数点数)なら足りてそうな気がするという雑な見積もりで通してしまいました。 仕事でやらかしたこともある部分なので反省しないとです。

抜粋

		// 隣接しているスライムで一番弱いものが吸収できなかったら終了
		if( now.power * static_cast<__int128>(X) >= takaPower )
		{
			break;
		}