Javaで解く！建物の全悪党を倒すための最小爆撃回数の求め方

問題概要

この問題の目的は、建物の各部屋に潜む悪党（ゴン）たちを、最小限の爆撃回数で全員倒すことです。部屋には1からnまでの番号が付けられており、悪党は最初の爆撃で負傷し、2回目の爆撃を受けることで死亡します。

重要なポイントは、部屋が爆撃されると、悪党たちは建物内の最も近い部屋（特に隣接する部屋）へ逃げ込んで隠れるという点です。この移動ルールを踏まえ、建物内のすべての悪党を倒すために必要な爆撃回数と、その爆撃順序を計算します。

具体例で理解する

例1：部屋数が3の場合

入力： 部屋の数 = 3

出力： 必要な総爆撃回数

4
2 1 3 2

解説： 必要な最小爆撃回数は4回です。まず2番目の部屋を爆撃すると、悪党たちは1番目か3番目の部屋へ逃げ込みます。次に1番目の部屋を爆撃すると、2番目の爆撃で負傷していた悪党の一部が死亡し、1番目の部屋に隠れていた悪党は負傷して最も近い2番目の部屋へ逃げます。続いて3番目の部屋を爆撃すると、2番目の爆撃後に隠れていた悪党が死亡し、3番目の部屋にいた悪党は最も近い2番目の部屋へ逃げます。最後に2番目の部屋を再度爆撃すれば、1番目と3番目から逃げてきた負傷した悪党が全滅し、任務完了です。

例2：部屋数が2の場合

入力： 部屋の数 = 2

出力： 必要な総爆撃回数

3
2 1 2

解説： 必要な最小爆撃回数は3回です。まず2番目の部屋を爆撃すると、悪党たちは1番目の部屋へ逃げます。次に1番目の部屋を爆撃すると、2番目の爆撃で負傷していた悪党の一部が死亡し、1番目の部屋に隠れていた悪党は負傷して2番目の部屋へ逃げます。最後に2番目の部屋を爆撃すれば、残りの悪党が全滅し、任務完了です。

アルゴリズムの考え方

• まず、部屋の総数nを入力として受け取ります。

• 必要な爆撃回数は (n + n/2) で計算でき、これを出力します。

• 第1段階： 建物の偶数番号の部屋をすべて爆撃し、その順序を出力します。

• 第2段階： 奇数番号の部屋をすべて爆撃し、その順序を出力します。

• 第3段階： 再び偶数番号の部屋を爆撃して仕上げとし、結果を出力します。

この「偶数 → 奇数 → 偶数」の順序で爆撃することで、逃げ回る悪党を確実に追い詰め、全員を倒すことができます。

Javaでの実装例

public class TP{
    public static void main(String[] args){
        int n = 8;
        System.out.println("Total Bombings required");
        System.out.println(n + n / 2);
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
        for (int i = 1; i <= n; i += 2)
            System.out.print(i + " ");
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
    }
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

Total Bombings required
12
2 4 6 8 1 3 5 7 2 4 6 8

部屋数が8の場合、必要な爆撃回数は 8 + 8/2 = 12回となり、「偶数部屋 → 奇数部屋 → 偶数部屋」の順に爆撃する戦略が正しく機能していることが確認できます。