LoginSignup
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

プログラミングゲームの解答コードを投稿しよう！
@anonymously115

【電脳少女プログラミング2088 ─壊レタ君を再構築─】「思い出の屋上」をやってみた。

Posted at

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$の状態（濃い色の所が縄張りです）
    territory1.png
  • 縄張り2、$d=4$（$d-s-1=3$）まで（緑色が更新部分）
    territory2.png
    さて、縄張り2により行列成分が3に更新されることはありませんでした。ここで処理を打ち切って大丈夫です。外側に1マス行けば$d-s-1$も1増えますが、現時点での行列成分も$+1$しか変化しないので、それ以上行列成分を更新することはありません。
  • 縄張り3（$d=3$（$d-s-1=1$）で打ち切り）
    territory3.png
  • $(1,6)$成分が最大なので、3を出力
    territory4.png

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

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)
4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?