paizaの新作プログラミングゲーム【電脳少女プログラミング2088 ─壊レタ君を再構築─】思い出の屋上（paizaランク：S相当）をやってみました。

問題

方針

二次元配列$A=(a_{i,j})$に縄張りを埋めた後で

$i=1,2...,H$について
- $j=1,2,...,W$について
  - $a_{i,j}$が縄張りでなければ
    - $d=1,2,...,H+W$について
      - $k=0,1,...,d-1$について
        
        $a_{i+k,j+d-k}$, $a_{i+d-k,j-k}$, $a_{i-k,j-d+k}$, $a_{i-d+k,j+k}$いずれかが縄張りならば
        
        現時点での$d-1$の値を新たな縄張りのサイズとして次の$j$の処理に移る

の様な実装をすると、$i,j,d,k$の4重ループになります。本問の制約条件では、実行時間制限に間に合いません。
そこで、

$H\times W$行列$A=(a_{i,j})$を用意し、各成分を$H+W$より大きな値で初期化する
$m=1,2,...,M$について
- $r_i, c_i, s_i$を取得
- $a_{r_i,c_i}\leftarrow\min(a_{r_i,c_i},-s_i-1)$とする
  - 「縄張り同士は重ならない」条件を信用して、$a_{r_i,c_i}=-s_i-1$で十分
- $d=1,2,...$について
  - $k=0,1,...,d-1$について
    - $a_{i+k,j+d-k}$, $a_{i+d-k,j-k}$, $a_{i-k,j-d+k}$, $a_{i-d+k,j+k}$の4個の値について、それぞれ$d-s-1$より大きい場合、$d-s-1$に置き換える
  - $k$に対して行列成分の更新が行われなければ、$d$のループを抜ける
$\max_{1\le i\le H, 1\le j\le W} a_{i,j}$が答え

とします。
これなら$m,d,k$の3重ループとなり、最初の方針よりループを1つ減らせました。paizaの実行制限時間は言語により3～16秒ですので、本問の制約条件では十分間に合います。

入出力例1で例を示します。

縄張り1入力後の行列$A$の状態（濃い色の所が縄張りです）

縄張り2、$d=4$（$d-s-1=3$）まで（緑色が更新部分）

さて、縄張り2により行列成分が3に更新されることはありませんでした。ここで処理を打ち切って大丈夫です。外側に1マス行けば$d-s-1$も1増えますが、現時点での行列成分も$+1$しか変化しないので、それ以上行列成分を更新することはありません。

縄張り3（$d=3$（$d-s-1=1$）で打ち切り）

$(1,6)$成分が最大なので、3を出力

他にも二分探索や幅優先探索を用いる解法が紹介されています。

C（四重ループ）

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int max(int a, int b) {
	return a > b ? a : b;
}

bool chmax(int *a, int b) {
	if (b > *a) {
		*a = b;
		return true;
	}
	return false;
}

int radius(int h, int w, bool *A[], int r, int c) {
	if (A[r][c])
		return -1;
	int D = max(r, h - 1 - r) + max(c, w - 1 - c);
	for (int d = 1; d <= D; d++) {
		for (int k = 0; k < d; k++) {
			int Y[4] = { r + k, r + d - k, r - k, r - d + k };
			int X[4] = { c + d - k, c - k, c - d + k, c + k };
			for (int i = 0; i < 4; i++) {
				if (0 <= Y[i] && Y[i] < h && 0 <= X[i] && X[i] < w) {
					if (A[Y[i]][X[i]])
						return d - 1;
				}
			}
		}
	}
	return D;
}

int main() {
	int H, W, M;
	scanf("%d %d %d", &H, &W, &M);
	bool A[H][W];
	memset(A, false, sizeof(A));
	while (M--) {
		int r, c, s;
		scanf("%d %d %d", &r, &c, &s);
		A[--r][--c] = true;
		for (int d = 1; d <= s; d++) {
			for (int k = 0; k < d; k++) {
				int Y[4] = { r + k, r + d - k, r - k, r - d + k };
				int X[4] = { c + d - k, c - k, c - d + k, c + k };
				for (int i = 0; i < 4; i++) {
					if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W) {
						A[Y[i]][X[i]] = true;
					}
				}
			}
		}
	}
	bool *a[H];
	for (int i = 0; i < H; i++)
		a[i] = A[i];
	int maximum = -1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			chmax(&maximum, radius(H, W, a, i, j));
		}
	}
	printf("%d\n", maximum);
	return 0;
}

C（三重ループ）

-s-1はビット反転演算子を使って~sと書けますので、コードゴルフを目指される方は参考にしていただきたいと思います。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool chmin(int *a, int b) {
	if (b < *a) {
		*a = b;
		return true;
	}
	return false;
}

bool chmax(int *a, int b) {
	if (b > *a) {
		*a = b;
		return true;
	}
	return false;
}

int main() {
	int H, W, M;
	scanf("%d %d %d", &H, &W, &M);
	int A[H][W];
	memset(A, 0x7F, sizeof(A));
	while (M--) {
		int r, c, s;
		scanf("%d %d %d", &r, &c, &s);
		chmin(&A[--r][--c], ~s);
		bool flg = true;
		int d = 0;
		while (flg) {
			flg = false;
			d += 1;
			for (int k = 0; k < d; k++) {
				int Y[4] = { r + k, r + d - k, r - k, r - d + k };
				int X[4] = { c + d - k, c - k, c - d + k, c + k };
				for (int i = 0; i < 4; i++)
					if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W)
						flg = chmin(&A[Y[i]][X[i]], ~s + d) || flg;
			}
		}
	}
	int max = -1;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			chmax(&max, A[i][j]);
	printf("%d\n", max);

	return 0;
}

C++

#include <iostream>
#include <vector>
using namespace std;

bool chmin(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

bool chmax(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

int main() {
	int H, W, M;
	scanf("%d %d %d", &H, &W, &M);
	vector<vector<int>> A(H, vector<int>(W, INT32_MAX));
	while (M--) {
		int r, c, s;
		cin >> r >> c >> s;
		chmin(A[--r][--c], ~s);
		bool flg = true;
		int d = 0;
		while (flg) {
			flg = false;
			d += 1;
			for (int k = 0; k < d; k++) {
				vector<int> Y = { r + k, r + d - k, r - k, r - d + k };
				vector<int> X = { c + d - k, c - k, c - d + k, c + k };
				for (int i = 0; i < 4; i++)
					if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W)
						flg = chmin(A[Y[i]][X[i]], ~s + d) || flg;
			}
		}
	}
	int maximum = -1;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			chmax(maximum, A[i][j]);
	printf("%d\n", maximum);

	return 0;
}

C#

using System;

class Program
{
	private static bool chmin(ref int a, int b)
	{
		if (b < a)
		{
			a = b;
			return true;
		}
		return false;
	}

	private static bool chmax(ref int a, int b)
	{
		if (b > a)
		{
			a = b;
			return true;
		}
		return false;
	}

	public static void Main()
	{
		int[] HWM = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		int H = HWM[0];
		int W = HWM[1];
		int M = HWM[2];
		int[][] A = new int[H][];
		for (int i = 0; i < H; i++)
		{
			A[i] = new int[W];
			for (int j = 0; j < W; j++) A[i][j] = int.MaxValue;
		}
		while (M-- > 0)
		{
			int[] rcs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
			int r = rcs[0] - 1;
			int c = rcs[1] - 1;
			int s = rcs[2];
			chmin(ref A[r][c], ~s);
			bool flg = true;
			int d = 0;
			while (flg)
			{
				flg = false;
				d += 1;
				for (int k = 0; k < d; k++)
				{
					int[] Y = new int[] { r + k, r + d - k, r - k, r - d + k };
					int[] X = new int[] { c + d - k, c - k, c - d + k, c + k };
					for (int i = 0; i < 4; i++)
						if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W)
							flg = chmin(ref A[Y[i]][X[i]], ~s + d) || flg;
				}
			}
		}
		int max = -1;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				chmax(ref max, A[i][j]);
		Console.WriteLine(max);
	}
}

Go

package main
import "fmt"

func chmin(a *int, b int) bool {
	if b < *a {
		*a = b
		return true
	}
	return false
}

func chmax(a *int, b int) bool {
	if b > *a {
		*a = b
		return true
	}
	return false
}

func main() {
	var H, W, M int
	fmt.Scan(&H, &W, &M)
	A := make([][]int, H)
	for i := 0; i < H; i++ {
		A[i] = make([]int, W)
		for j := 0; j < W; j++ {
			A[i][j] = 0x7FFFFFFF
		}
	}
	for m := 0; m < M; m++ {
		var r, c, s int
		fmt.Scan(&r, &c, &s)
		r -= 1
		c -= 1
		chmin(&A[r][c], ^s)
		d := 0
		flg := true
		for flg {
			flg = false
			d += 1
			for k := 0; k < d; k++ {
				Y := []int{ r + k, r + d - k, r - k, r - d + k }
				X := []int{ c + d - k, c - k, c - d + k, c + k }
				for i := 0; i < 4; i++ {
					if 0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W {
						flg = chmin(&A[Y[i]][X[i]], ^s + d) || flg
					}
				}
			}
		}
	}
	max := -1
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			chmax(&max, A[i][j])
		}
	}
	fmt.Println(max)
}

Java

import java.util.*;

public class Main {

	private static boolean chmin(int[][] A, int i, int j, int b) {
		if (b < A[i][j]) {
			A[i][j] = b;
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int M = sc.nextInt();
		int[][] A = new int[H][];
		for (int i = 0; i < H; i++) {
			A[i] = new int[W];
			for (int j = 0; j < W; j++) {
				A[i][j] = Integer.MAX_VALUE;
			}
		}
		while (M-- > 0) {
			int r = sc.nextInt() - 1;
			int c = sc.nextInt() - 1;
			int s = sc.nextInt();
			chmin(A, r, c, ~s);
			int d = 0;
			boolean flg = true;
			while (flg) {
				flg = false;
				d += 1;
				for (int k = 0; k < d; k++) {
					int[] Y = { r + k, r + d - k, r - k, r - d + k };
					int[] X = { c + d - k, c - k, c - d + k, c + k };
					for (int i = 0; i < 4; i++) {
						if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W)
							flg = chmin(A, Y[i], X[i], ~s + d) || flg;
					}
				}
			}
		}
		sc.close();
		int max = -1;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				max = Math.max(max, A[i][j]);
		System.out.println(max);
	}
}

JavaScript

function chmin(A, i, j, b) {
	if (b < A[i][j]) {
		A[i][j] = b;
		return true;
	}
	return false;
}

const [HWM, ...RCS] = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n').map((s) => s.split(' ').map(Number));
const [H, W, M] = HWM;
let A = Array.from({ length: H }, () => Array(W).fill(Number.MAX_SAFE_INTEGER));
for (var m = 0; m < M; m++) {
	let [r, c, s] = RCS[m];
	chmin(A, --r, --c, ~s);
	let d = 0;
	let flg = true;
	while (flg) {
		flg = false;
		d += 1;
		for (var k = 0; k < d; k++) {
			const Y = [r + k, r + d - k, r - k, r - d + k];
			const X = [c + d - k, c - k, c - d + k, c + k];
			for (var i = 0; i < 4; i++) {
				if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W)
					flg = chmin(A, Y[i], X[i], ~s + d) || flg;
			}
		}
	}
}
let max = -1;
for (var i = 0; i < H; i++)
	for (var j = 0; j < W; j++)
		max = Math.max(max, A[i][j]);
console.log(max);

Kotlin

import java.util.*

fun chmin(A: Array<Array<Int>>, i: Int, j: Int, b: Int): Boolean {
	if (b < A[i][j]) {
		A[i][j] = b
		return true
	}
	return false
}

fun main() {
	val sc = Scanner(System.`in`)
	val H = sc.nextInt()
	val W = sc.nextInt()
	val M = sc.nextInt()
	val A = Array(H) { Array(W) { Int.MAX_VALUE } }

	repeat(M) {
		val r = sc.nextInt() - 1
		val c = sc.nextInt() - 1
		val s = sc.nextInt()
		chmin(A, r, c, s.inv())

		var d = 0
		var flg = true
		while (flg) {
			flg = false
			d += 1
			for (k in 0 until d) {
				val Y = arrayOf(r + k, r + d - k, r - k, r - d + k)
				val X = arrayOf(c + d - k, c - k, c - d + k, c + k)
				for (i in 0 until 4) {
					if (0 <= Y[i] && Y[i] < H && 0 <= X[i] && X[i] < W) {
						flg = chmin(A, Y[i], X[i], s.inv() + d) || flg
					}
				}
			}
		}
	}

	var max = -1
	for (i in 0 until H) {
		for (j in 0 until W) {
			max = Math.max(max, A[i][j])
		}
	}
	println(max)
}

PHP

<?php
	function chmin(&$a, $b) {
		if ($b < $a) {
			$a = $b;
			return true;
		}
		return false;
	}

	function chmax(&$a, $b) {
		if ($b > $a) {
			$a = $b;
			return true;
		}
		return false;
	}

	[$H, $W, $M] = array_map("intval", explode(' ', trim(fgets(STDIN))));
	$A = array_fill(0, $H, array_fill(0, $W, PHP_INT_MAX));
	while ($M--) {
		[$r, $c, $s] = array_map("intval", explode(' ', trim(fgets(STDIN))));
		chmin($A[--$r][--$c], ~$s);
		$d = 0;
		$flg = true;
		while ($flg) {
			$flg = false;
			$d += 1;
			for ($k = 0; $k < $d; $k++) {
				$Y = [$r + $k, $r + $d - $k, $r - $k, $r - $d + $k];
				$X = [$c + $d - $k, $c - $k, $c - $d + $k, $c + $k];
				for ($i = 0; $i < 4; $i++) {
					if (0 <= $Y[$i] && $Y[$i] < $H && 0 <= $X[$i] & $X[$i] < $W)
						$flg = chmin($A[$Y[$i]][$X[$i]], ~$s + $d) || $flg;
				}
			}
		}
	}
	$max = -1;
	for ($i = 0; $i < $H; $i++)
		for ($j = 0; $j < $W; $j++)
			chmax($max, $A[$i][$j]);
	echo $max, PHP_EOL;
?>

Perl

sub chmin {
	my ($a, $b) = @_;
	if ($b < $$a) {
		$$a = $b;
		return 1;
	}
	return 0;
}

sub chmax {
	my ($a, $b) = @_;
	if ($b > $$a) {
		$$a = $b;
		return 1;
	}
	return 0;
}

my ($H, $W, $M) = map { int($_) } (split ' ', <STDIN>);
my @A = map { [(~0) x $W] } (1..$H);
while ($M--) {
	my ($r, $c, $s) = map { int($_) } (split ' ', <STDIN>);
	chmin(\$A[--$r][--$c], -($s + 1));
	my $d = 0;
	my $flg = 1;
	while ($flg) {
		$flg = 0;
		$d += 1;
		for (my $k = 0; $k < $d; $k++) {
			my @Y = ($r + $k, $r + $d - $k, $r - $k, $r - $d + $k);
			my @X = ($c + $d - $k, $c - $k, $c - $d + $k, $c + $k);
			for (my $i = 0; $i < 4; $i++) {
				if (0 <= $Y[$i] && $Y[$i] < $H && 0 <= $X[$i] && $X[$i] < $W) {
					$flg = chmin(\$A[$Y[$i]][$X[$i]], $d - $s - 1) || $flg;
				}
			}
		}
	}
}

my $max = -1;
for (my $i = 0; $i < $H; $i++) {
	for (my $j = 0; $j < $W; $j++) {
		chmax(\$max, $A[$i][$j]);
	}
}
print "$max$/";

Python3

def chmin(A, i, j, b):
	if b < A[i][j]:
		A[i][j] = b
		return True
	return False

H, W, M = map(int, input().split())
A = [[float('inf')] * M for _ in range(H)]
for _ in range(M):
	r, c, s = map(int, input().split())
	r -= 1
	c -= 1
	chmin(A, r, c, ~s)
	d = 0
	flg = True
	while flg:
		flg = False
		d += 1
		for k in range(d):
			Y = (r + k, r + d - k, r - k, r - d + k)
			X = (c + d - k, c - k, c - d + k, c + k)
			for y, x in zip(Y, X):
				if 0 <= y < H and 0 <= x < W:
					flg = chmin(A, y, x, ~s + d) or flg
			
print(max(max(max(A[i]) for i in range(H)), -1))

Ruby

H, W, M = gets.split.map(&:to_i)
A = Array.new(H) { Array.new(W, Float::INFINITY) }

M.times do
	r, c, s = gets.split.map(&:to_i)
	r -= 1
	c -= 1
	A[r][c] = [A[r][c], ~s].min
	d = 0
	flg = true
	while flg
		flg = false
		d += 1
		d.times do |k|
			y = [r + k, r + d - k, r - k, r - d + k]
			x = [c + d - k, c - k, c - d + k, c + k]
			y.zip(x).each do |i, j|
				if 0 <= i && i < H && 0 <= j && j < W
					if ~s + d < A[i][j]
						A[i][j] = ~s + d
						flg = true
					end
				end
			end
		end
	end
end

puts [A.map { |row| row.max }.max, -1].max

Scala

import scala.io.StdIn._

object Main extends App{

	def chmin(A: Array[Array[Int]], i: Int, j: Int, b: Int): Boolean = {
		if (b < A(i)(j)) {
			A(i)(j) = b
			true
		} else {
			false
		}
	}

	val Array(h, w, m) = readLine().split(" ").map(_.toInt)
	val territory = Array.fill(h, w)(Int.MaxValue)

	for (_ <- 0 until m) {
		var Array(r, c, s) = readLine().split(" ").map(_.toInt)
		r -= 1
		c -= 1
		chmin(territory, r, c, ~s)
		var d = 0
		var flg = true
		while (flg) {
			flg = false
			d += 1
			for (k <- 0 until d) {
				val Y = Array(r + k, r + d - k, r - k, r - d + k)
				val X = Array(c + d - k, c - k, c - d + k, c + k)
				for (i <- 0 until 4) {
					if (Y(i) >= 0 && Y(i) < h && X(i) >= 0 && X(i) < w) {
						flg = chmin(territory, Y(i), X(i), ~s + d) || flg
					}
				}
			}
		}
	}

	var max = -1
	for (i <- 0 until h) {
		for (j <- 0 until w) {
			max = math.max(max, territory(i)(j))
		}
	}
	println(max)
}

Swift

func chmin(_ a: inout Int, b: Int) -> Bool {
	if b < a {
		a = b
		return true
	}
	return false
}

let HWM = readLine()!.split(separator: " ").map { Int($0)! }
let H = HWM[0], W = HWM[1], M = HWM[2]

var A = Array(repeating: Array(repeating: Int.max, count: M), count: H)

for _ in 0..<M {
	let line = readLine()!.split(separator: " ").map { Int($0)! }
	let r = line[0] - 1
	let c = line[1] - 1
	let s = line[2]
	
	_ = chmin(&A[r][c], b: ~s)
	
	var d = 0
	var flg = true
	while flg {
		flg = false
		d += 1
		for k in 0..<d {
			let Y = [r + k, r + d - k, r - k, r - d + k]
			let X = [c + d - k, c - k, c - d + k, c + k]
			for i in 0..<4 {
				let y = Y[i], x = X[i]
				if y >= 0 && y < H && x >= 0 && x < W {
					flg = chmin(&A[y][x], b: ~s + d) || flg
				}
			}
		}
	}
}

var maximum = -1
for i in 0..<H {
	for j in 0..<W {
		maximum = max(maximum, A[i][j])
	}
}
print(maximum)