【最難関ランク】【初心者向け解説】電脳少女プログラミング2088 (paizaランクS相当)

今回は、こちらの[プログラミングゲームの解答コードを投稿しよう！](https://qiita.com/official-events/efe957f155af900604b3)の公式イベントの記事になります。

具体的には、[paizaの新作プログラミングゲーム「電脳少女プログラミング2088 ─壊レタ君を再構築─」](https://ppg.paiza.jp/denno2088)の<font color="red">「思い出の屋上」</font>という問題の解答例とその解説を紹介していきたいと思います。
こちらはpaizaのランクS相当とのことです。:sparkles:

## 前回の記事
こちらでランクA相当のSQL問題も解説しています。
興味がある方は是非ご覧ください。

https://qiita.com/phibi-soon/items/04dc8a0a830844e38ae4

# 問題

https://ppg.paiza.jp/denno2088/challenges/denno2088_c_s_01

# 早速Javaでの解答

私は以下のコードを作成し、提出しました。
これでOKでした！:tada:

```java
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int H = sc.nextInt();
        int W = sc.nextInt();
        int M = sc.nextInt();
        boolean[][] occupied = new boolean[H][W];

        for (int i = 0; i < M; i++) {
            int r = sc.nextInt() - 1; // 配列のインデックスは0始まり
            int c = sc.nextInt() - 1;
            int s = sc.nextInt();

            for (int x = Math.max(0, r - s); x <= Math.min(H - 1, r + s); x++) {
                for (int y = Math.max(0, c - s); y <= Math.min(W - 1, c + s); y++) {
                    if (Math.abs(r - x) + Math.abs(c - y) <= s) {
                        occupied[x][y] = true;
                    }
                }
            }
        }

        // 最大サイズを探索
        int maxTerritorySize = -1;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                // 中心が既に占有されていればスキップ
                if (occupied[r][c]) continue;

                // サイズを広げられる最大値をバイナリサーチで探索
                int low = 0, high = Math.max(H, W);
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (canPlaceTerritory(r, c, mid, H, W, occupied)) {
                        maxTerritorySize = Math.max(maxTerritorySize, mid);
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
            }
        }

        // 結果を出力
        System.out.println(maxTerritorySize);

        sc.close();
    }

    // 指定された中心とサイズで縄張りを設置可能かを確認
    private static boolean canPlaceTerritory(int r, int c, int size, int H, int W, boolean[][] occupied) {
        for (int x = Math.max(0, r - size); x <= Math.min(H - 1, r + size); x++) {
            for (int y = Math.max(0, c - size); y <= Math.min(W - 1, c + size); y++) {
                if (Math.abs(r - x) + Math.abs(c - y) <= size && occupied[x][y]) {
                    return false;
                }
            }
        }
        return true;
    }
}

```

# 解説

## 1.まずは入力値の取得
まずはタイトルに書いたとおり、落ち着いて入力値を取得しましょう。
Sランクとはいえ、他の簡単な問題と同様に、入力値の取得を行っていきましょう。

```java
import java.util.*;

public class Main {
    Scanner sc = new Scanner(System.in);
    
    int H = sc.nextInt();
    int W = sc.nextInt();
    int M = sc.nextInt();
    
    for (int i = 0; i < M; i++) {
        int r = sc.nextInt() - 1;
        int c = sc.nextInt() - 1;
        int s = sc.nextInt();
    }
}
```

ここで、取得している情報は以下のとおりです。
- エリアのサイズ`(H, W)`と既存の縄張りの数`M`を取得
- 既存の縄張りの中心座標`(r, c)`とその縄張りのサイズ`s`を取得

また、`r`と`c`は座標であり、最小で、`(1, 1)`をとります。
一方、次の解説の中で説明しますが、私は図から**多次元配列を使う**べきと判断しました。
そのため、座標を配列に合わせる必要があり、上のソースでは、`r`と`c`をそれぞれ`-1`しました。

これにより、例えば多次元配列における`[0][0]`は、座標`(1, 1)`に該当することになります。

## 2.図に合わせて2次元配列を作成する

図には、H × W のサイズのマスが描かれています。
これを表現する際には、2次元配列を利用します。
また、それぞれのマスは「**縄張りになっているか**」、「**縄張りになっていないか**」の情報が必要になります。
もちろん、各縄張りで色を持つことができれば良いのかもしれませんが、一旦条件としては上記の情報で十分と思われるので、`boolean`型で`True`なら縄張りであるとする配列を作成しておきます。

```diff_java
...
int H = sc.nextInt();
int W = sc.nextInt();
int M = sc.nextInt();
+ boolean[][] occupied = new boolean[H][W];
...
```

## 3.縄張りの影響範囲をマンハッタン距離を用いて計算する
割と肝になる部分です。
が、まぁそうなるか、といったものになります。

ここで実装する内容としては、**縄張りの中心`(r, c)`から マンハッタン距離`s`以下の範囲を`occupied[x][y] = true`にすることで、<font color="red">「この場所はすでに占領されている」</font>とマーク**する処理になります。

:::note info
問題文より、
> マンハッタン距離とは、2 座標 (p, q)、(s, t) に対して、|p - s| + |q - t| で計算される距離を表します。
:::

縦方向と横方向でそれぞれ考える必要があるので、分けて考えていきます。

### 縦方向

縄張りの影響範囲は`(r, c)`を中心に、上`s`マスから下`s`マスまで広がるので、縄張りの取りうる範囲`x`は`r - s`から`r + s`になります。

ただし、座標の最小は`(1, 1)`で配列なら`[0][0]`であることから、
`x`の最小値は、
- `r - s`が正なら`r - s`
- `r - s`がゼロ以下なら`0`

となります。
つまり、`r - s`と`0`のうち、大きい方が`x`の最小値となります。
**大きい方**を算出したい際には、**`Math.max`メソッド**が利用できます。

AとBのうち大きい方は`Math.max(A, B)`で取得することが可能になります。

また、最大値も同じく、エリアの縦のサイズが`H`(座標では`H - 1`)なので、
- `r + s`が`H - 1`より大きければ`H - 1`
- `r + s`が`H - 1`以下なら、`r + s`

となります。
つまり、`r + s`と`H - 1`のうち、小さい方が`x`の最大値になります。
**小さい方**の算出には、**`Math.min`メソッド**が同様に利用できます。

以上を踏まえて、`x`の取りうる範囲における`for`文を書くとしたら、以下のようになります。

```java
for (int x = Math.max(0, r - s); x <= Math.min(H - 1, r + s); x++)
```
少々長いですが、上述のことを`for`文に書き起こしたものなので、よく解説と照らし合わせると、理解はできるかと思います！

### 横方向

横方向も縦方向と同じ考え方で問題ないかと思います。

`y`の最小値は、
- `c - s`が正なら`c - s`
- `c - s`がゼロ以下なら`0`

となりますし、最大値は
- `c + s`が`W - 1`より大きければ`W - 1`
- `c + s`が`W - 1`以下なら、`c + s`

となります。

これらを踏まえると、`for`文は以下のとおりです。

```java
for (int y = Math.max(0, c - s); y <= Math.min(W - 1, c + s); y++)
```

### 計算量について

さて、縦方向・横方向において、`x`、`y`の取りうる範囲(`for'文)が出来上がったので、合体させていきます。

```diff_java
...
    
for (int i = 0; i < M; i++) {
    int r = sc.nextInt() - 1;
    int c = sc.nextInt() - 1;
    int s = sc.nextInt();

+    for (int x = Math.max(0, r - s); x <= Math.min(H - 1, r + s); x++) {
+        for (int y = Math.max(0, c - s); y <= Math.min(W - 1, c + s); y++) {
+            // ここに、occupied[x][y] = trueを記述する
+        }
+    }
}

...
```

綺麗な3重ループになっていることがわかります。
競技プログラミングにおいて、多重ループは注意が必要です。

10回のループ処理が2重にあった場合、その計算量は[10 × 10]で、100回の繰り返し処理が行われます。
10,000回のループが2重であれば、100,000,000(1億)回の処理が行われることになります。
このように計算量が増えると、処理が完了するまでに時間がかかります。

:::note warn
競技プログラミングでは、処理時間の上限が定められており、それを超過するような時間のかかる処理があった場合、プログラム上には問題がなくても、TLE(Time Limit Exceeded、実行時間制限超過)となり、正解となりません。

一般的に、1変数のループ回数が、10^5となるような多重ループ処理は実装に気を付け、むしろ多重ループを使わない方法をとるように考えるそうです。
:::

さて、今回の最大ループ数は、[Mの最大値] × [r+sの最大値] × [c+sの最大値]となりますが、
問題の「条件」に

> ・1 ≦ H, W ≦ 200
> ・1 ≦ M ≦ 200
> ・1 ≦ r_i ≦ H (1 ≦ i ≦ M)
> ・1 ≦ c_i ≦ W (1 ≦ i ≦ M)
> ・0 ≦ s_i ≦ 200 (1 ≦ i ≦ M)

とあることから、計算量は大したことないことがわかります。
したがって、上記に示した3重ループはTLEの対象にはならないと判断してよさそうです。

### 縄張りの影響範囲に対して、`occupied[x][y] = true`にする

さて、ループは問題ないことがわかったので、最後に縄張りの影響範囲に対して、`occupied[x][y] = true`にしていきます。

改めて、この項目での目的は「縄張りの中心`(r, c)`からマンハッタン距離`s`以下の範囲を`occupied[x][y] = true`にすることで、<font color="red">「この場所はすでに占領されている」</font>とマークする」ことです。

読み替えると、**縄張りの中心`(r, c)`と`(x, y)`のマンハッタン距離が`s`以下である`(x, y)`に対して、`occupied[x][y] = true`にする**ということになります。

:::note info
(再掲)
問題文より、
> マンハッタン距離とは、2 座標 (p, q)、(s, t) に対して、|p - s| + |q - t| で計算される距離を表します。
:::

絶対値の計算には、`Math.abs`メソッドを利用します。
よって、
```diff_java
...
    
for (int i = 0; i < M; i++) {
    int r = sc.nextInt() - 1;
    int c = sc.nextInt() - 1;
    int s = sc.nextInt();

    for (int x = Math.max(0, r - s); x <= Math.min(H - 1, r + s); x++) {
        for (int y = Math.max(0, c - s); y <= Math.min(W - 1, c + s); y++) {
-            // ここに、occupied[x][y] = trueを記述する
+            if (Math.abs(r - x) + Math.abs(c - y) <= s) {
+                  occupied[x][y] = true;
*            }
        }
    }
}

...
```

これで、やっと、各縄張りを表現することができました。
ただ、まだこれはゴールではありません。

もう一度問題を読んでみましょう。

> エリアに既に存在する縄張りの位置とサイズが与えられるので、

ここは対応しました。縄張りにより占有されているかどうかは`occupied`配列に保持したところです。

> エリア内で新たに縄張りの中心を作成する場合の可能な最大サイズを求めるプログラムを作成してください。すでに全てのエリアが縄張りになっていて、新たに縄張りの中心を作成できない場合は -1 と出力してください。

ゴールはこれですね。
この続きも解説していきます。

## 4.それぞれのマスに対する判定処理
次にそれぞれのマスが**新たな縄張りの中心になれるかどうか**を判定する処理を実装していきます。
新たな縄張りの中心になれるかは、そのマスが占有されていなければ良いので、判定自体は単純です。
また、計算量も多くないことがわかっているので、`H` × `W` 個の全てのマスを検査していきます。

もし、検査したマスが縄張りの中心になれない(＝既に占有されている)なら、出力値を-1として次の繰り返し処理に進むようにします。

```diff_java
import java.util.*;

public class Main {

    public static void main(String[] args) {

        // ... (省略)

+        int maxTerritorySize = -1;
+        for (int r = 0; r < H; r++) {
+            for (int c = 0; c < W; c++) {
+                // 中心が既に占有されていればスキップ
+                if (occupied[r][c]) continue;
+                
+                // (以下、占有されていないので、新たに作成する縄張りのサイズを算出する)
+            }
+        }
    }
}

```

## 5.新しい縄張りの最大サイズの算出

さて、各マスについて、占有状況を確認し、占有されていなかった場合は、新しい縄張りの中心にすることが可能です。

問題文には、

> エリア内で新たに縄張りの中心を作成する場合の可能な最大サイズを求めるプログラムを作成してください。

とあるので、新たな縄張りの最大サイズを求める必要があります。
縄張りのサイズは、
- 最小: 0 (中心のみ)
- 最大: `H`と`W`の大きい方 = `Math.max(H, W)`

という条件があります。

`H`や`W`の最大値は200なので、この新縄張り最大サイズの計算も計算量は大したことがないので、[0から`Math.max(H, W)`まで]の`for文`でよさそうです。
ただ、少しはアルゴリズムを利用しておきたいところなので、今回は<font color="red">**二分探索**</font>を利用することにしました。

:::note info
二分探索(Binary Search)は、**ある範囲の中で「条件を満たす最大(または最小)の値」を探す**のに使われる方法です。  
普通のループ(O(N²) など)だと時間がかかりますが、二分探索を使うと **O(log N)** で高速に計算できます。

この問題では、**可能な最大の縄張りサイズ `s`** を求めるのに二分探索を利用しました。
:::

```diff_java
import java.util.*;

public class Main {

    public static void main(String[] args) {

        // ... (省略)

        int maxTerritorySize = -1;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                // 中心が既に占有されていればスキップ
                if (occupied[r][c]) continue;

+                int low = 0; // 新縄張りサイズの最小値
+                int high = Math.max(H, W); // 新縄張りサイズの最大値
+                
+                while (low <= high) {
+                    int mid = (low + high) / 2; // 最大値と最小値の中間値
+                    if (canPlaceTerritory(r, c, mid, H, W, occupied)) {
+                        // サイズがmidの縄張りを作ることが可能であれば、midとmaxTerritorySizeとで大きい方を保持する
+                        maxTerritorySize = Math.max(maxTerritorySize, mid);
+                        low = mid + 1;
+                    } else {
+                        high = mid - 1;
+                    }
+                }
            }
        }
    }
+    // 指定された中心とサイズで縄張りを設置可能かを確認する処理
+    private static boolean canPlaceTerritory(int r, int c, int size, int H, int W, boolean[][] occupied) {
+        return true; // 一旦仮の戻り値
+    }
}

```

処理としては、常に縄張りが取りうる最小サイズ`low`と最大サイズ`high`をそれぞれ保持し、これらの上下関係が逆転するまで`while`で処理を繰り返します。

繰り返す処理の流れとしては、以下の通りになります。
二分探索が初めての人にとっては複雑な処理になっているので、しっかりと読んでもらえたらと思います。

1. `low`と`high`の中間値(平均値)を`mid`として取得
2. `mid`サイズの縄張りを作成できるかを判定
(※判定処理`canPlaceTerritory`に関しては[ステップ6](#6.指定された中心とサイズで縄張りを設置可能かを確認する)で解説)
3. 2.の判定結果に応じて処理分岐
    1. **`mid`サイズの縄張りを作成できる場合**
        1. `mid`もしくは既に変数として保持している`maxTerritorySize`のうち、大きい方を保持
        2. `mid`サイズの縄張りを作成できるということは、より大きいサイズの縄張りが作成できる可能性がある。また、`mid`より小さい縄張りの判定は不要なので、`low`を`mid + 1`で上書きする
    2. **`mid`サイズの縄張りを作成できない場合**
        1. `mid`サイズの縄張りを作成できないということは、より小さいサイズの縄張りの判定をしていく必要がある。また、`mid`より大きい縄張りの判定は不要なので、`high`を`mid - 1`で上書きする

:::note info
上記フローにおいて、[3.]の[2.`mid`サイズの縄張りを作成できない場合]のパターンは、
**「サイズ`mid`で新しい縄張りを作成しようとすると、すでにある縄張りと重なってしまい、サイズ`mid`では作れない」**
ことを指します。
:::


## 6.指定された中心とサイズで縄張りを設置可能かを確認する

5.でも少しソースコードに書かれていますが、判定処理`canPlaceTerritory`の実装をしていきます。
引数の`r`と`c`の座標`(r, c)`を中心に`size`の縄張りを作れるか判定します。
**`occupied`に`true`が含まれていないかチェックし、もし`true`なら設置不可能と判定**します。

ただ、ここの処理についてはほとんど[ステップ3](#3.縄張りの影響範囲をマンハッタン距離を用いて計算する)と同じ考え方になっているので、そちらが理解できていれば、実装は容易かと思います。

`if`文は後半が少し異なりますが、上述の[`occupied`に`true`が含まれていないかチェック]するための処理で、複雑ではないかと思います。

```diff_java
private static boolean canPlaceTerritory(int r, int c, int size, int H, int W, boolean[][] occupied) {
+    for (int x = Math.max(0, r - size); x <= Math.min(H - 1, r + size); x++) {
+        for (int y = Math.max(0, c - size); y <= Math.min(W - 1, c + size); y++) {
+            if (Math.abs(r - x) + Math.abs(c - y) <= size && occupied[x][y]) {
+                return false;
+            }
+        }
+    }
    return true;
}
```

## 7.答えの出力処理

最後に答えになる`maxTerritorySize`を出力します。
私は、癖というか、思想というか、昔の諸先輩方のありがたいお言葉からか、**`Scanner`は開いたら閉じる**ようにしていますが、これは競技プログラミングでは自由らしいですね。
```diff_java
import java.util.*;

public class Main {

    public static void main(String[] args) {

        // ... (省略)

        int maxTerritorySize = -1;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
            
                // ... (省略)
                
            }
        }
+        // 結果を出力
+        System.out.println(maxTerritorySize);
+        sc.close();
    }

    // ... (省略)
    
}

```

**完成です！！！！！！**:tada:

## おまけ: 解説[ステップ3](#3.縄張りの影響範囲をマンハッタン距離を用いて計算する)の具体例
<details><summary>簡単な具体例です</summary>

### 例: エリア 7×8, 縄張り(4, 5) サイズ 3

```text
H = 7, W = 8
縄張りの中心: (4, 5) → 配列上は[3][4]
サイズ: 3
```
`occupied` 配列にマークする範囲を可視化すると、

```text
左上を(1, 1)とした場合、

.  .  .  .  X  .  .  .
.  .  .  X  X  X  .  .
.  .  X  X  X  X  X  .
.  X  X  X  O  X  X  X
.  .  X  X  X  X  X  .
.  .  .  X  X  X  .  .
.  .  .  .  X  .  .  .
```
`O`が縄張りの中心`(3,4)`
`X`がマンハッタン距離`≤ 3`の範囲(`occupied[x][y] = true`に設定)

**処理の流れ**
- `r - s` = 3 - 2 = **1**、`r + s` = 3 + 2 = **5** → `x` の範囲は `[1,5]`
- `c - s` = 4 - 2 = **2**、`c + s` = 4 + 2 = **6** → `y` の範囲は `[2,6]`
- `(x, y)` のすべての組み合わせをチェックし、**マンハッタン距離 `≤ 3` のセルのみ `true` にする**

</details>

# 終わりに

今回の記事では、paizaの新作プログラミングゲーム「電脳少女プログラミング2088」の「思い出の屋上」問題について、Javaを用いた解答例とその解説を詳しく紹介しました。Sランク相当の問題ということで、単純な実装ではなく、計算量を意識した工夫が必要でした。

特に、**マンハッタン距離の計算**や**最大サイズを求める際の二分探索**といったアルゴリズムの適用がポイントでした。このような問題を解くことで、**競技プログラミングの考え方や効率的なアルゴリズムの実装力**を鍛えることができると感じています。

ぜひ、他の言語でも実装してみたり、異なるアプローチを試してみたりすることで、さらに理解を深めてみてください！
また、他の問題にも挑戦し、どんどんスキルを磨いていきましょう:muscle: :sparkles:

最後までお読みいただき、ありがとうございました！:tada: