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

今回は、こちらのプログラミングゲームの解答コードを投稿しよう！の公式イベントの記事になります。

具体的には、paizaの新作プログラミングゲーム「電脳少女プログラミング2088 ─壊レタ君を再構築─」の「思い出の屋上」という問題の解答例とその解説を紹介していきたいと思います。
こちらはpaizaのランクS相当とのことです。

前回の記事

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

問題

早速Javaでの解答

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

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ランクとはいえ、他の簡単な問題と同様に、入力値の取得を行っていきましょう。

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なら縄張りであるとする配列を作成しておきます。

...
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にすることで、「この場所はすでに占領されている」とマークする処理になります。

問題文より、

マンハッタン距離とは、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文を書くとしたら、以下のようになります。

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文は以下のとおりです。

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

計算量について

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

...
    
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億)回の処理が行われることになります。
このように計算量が増えると、処理が完了するまでに時間がかかります。

競技プログラミングでは、処理時間の上限が定められており、それを超過するような時間のかかる処理があった場合、プログラム上には問題がなくても、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にすることで、「この場所はすでに占領されている」とマークする」ことです。

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

(再掲)
問題文より、

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

絶対値の計算には、Math.absメソッドを利用します。
よって、

...
    
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として次の繰り返し処理に進むようにします。

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文でよさそうです。
ただ、少しはアルゴリズムを利用しておきたいところなので、今回は二分探索を利用することにしました。

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

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

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で解説)
3. 2.の判定結果に応じて処理分岐
   1. midサイズの縄張りを作成できる場合
      1. midもしくは既に変数として保持しているmaxTerritorySizeのうち、大きい方を保持
      2. midサイズの縄張りを作成できるということは、より大きいサイズの縄張りが作成できる可能性がある。また、midより小さい縄張りの判定は不要なので、lowをmid + 1で上書きする
   2. midサイズの縄張りを作成できない場合
      1. midサイズの縄張りを作成できないということは、より小さいサイズの縄張りの判定をしていく必要がある。また、midより大きい縄張りの判定は不要なので、highをmid - 1で上書きする

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

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

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

ただ、ここの処理についてはほとんどステップ3と同じ考え方になっているので、そちらが理解できていれば、実装は容易かと思います。

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

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は開いたら閉じるようにしていますが、これは競技プログラミングでは自由らしいですね。

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();
    }

    // ... (省略)
    
}

完成です！！！！！！

おまけ: 解説ステップ3の具体例

簡単な具体例です

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

H = 7, W = 8
縄張りの中心: (4, 5) → 配列上は[3][4]
サイズ: 3

occupied 配列にマークする範囲を可視化すると、

左上を(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 にする

終わりに

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

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

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

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