AOJ PG入門 #6

問1.与えられた数列を逆順に出力するプログラムを作成して下さい。

PHP

AOJ.php

<?php

    $n= intval(trim(fgets(STDIN)));
    $num = explode(" ",trim(fgets(STDIN)));
    
        $num = array_reverse($num);
        echo  implode(" ",$num)."\n";   
?>

Java

AOJ.java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(sc.next()); 
        }
        sc.close();

        for (int j = n - 1; j >= 0; j--) { 
            System.out.print(arr[j]); 
            if (j != 0) {
                System.out.print(" ");
            }
        }
        System.out.println(); 
    }
}

• Integer.parseInt は文字列を整数に変換するためのメソッド

問2. 不足しているカードの発見

太郎が花子と一緒にトランプ遊びをしようとしたところ、52枚あるはずのカードが n 枚のカードしか手元にありません。これらの n 枚のカードを入力として、足りないカードを出力するプログラムを作成して下さい。
太郎が最初に持っていたトランプはジョーカーを除く52枚のカードです。

• 52枚のカードは、スペード、ハート、クラブ、ダイヤの４つの絵柄に分かれており、各絵柄には13のランクがあります。

• 最初の行に太郎が持っているカードの枚数 n (n ≤ 52)が与えられます。

• 続いて n 組のカードがそれぞれ１行に与えられます。各組は１つの空白で区切られた文字と整数です。文字はカードの絵柄を表し、スペードが'S'、ハートが'H'、クラブが'C'、ダイヤが'D'で表されています。整数はそのカードのランク(1 〜 13)を表しています。

• 足りないカードをそれぞれ1行に出力して下さい。各カードは入力と同様に１つの空白で区切られた文字と整数です。出力するカードの順番は以下のとおりとします：

• 絵柄がスペード、ハート、クラブ、ダイヤの順番で優先的に出力する。

• 絵柄が同じ場合は、ランクが小さい順に出力する。

PHP

AOJ.php

<?php

$suits = ["S", "H", "C", "D"];
$allCards = [];
foreach ($suits as $suit) {
    for ($i = 1; $i <= 13; $i++) {
        $allCards["$suit $i"] = true;
    }
}


$n = trim(fgets(STDIN));
for ($i = 0; $i < $n; $i++) {
    list($suit, $rank) = explode(" ", trim(fgets(STDIN)));
    unset($allCards["$suit $rank"]);
}


foreach ($allCards as $card => $value) {
    echo "$card\n";
}
?>

• 今回使いたいのは連想配列のキー→値はプレースホルダー
• foreachでas cards)としてしまうと値（true）が出力されてしまう

別解

Other.php

<?php

$all_cards = [];
foreach (['S', 'H', 'C', 'D'] as $suit) {
   for ($i = 1; $i <= 13; $i++) {
       $all_cards[] = "$suit $i";
   }
}

// 持っているカード
$n = trim(fgets(STDIN));
$have_cards = [];
for ($i = 0; $i < $n; $i++) {
   $have_cards[] = trim(fgets(STDIN));
}

// 不足分を算出して出力
$missing = array_diff($all_cards, $have_cards);
foreach ($missing as $card) {
   echo "$card\n";
}
?>

• array_diff() は、2つの配列を比較して、最初の配列に存在しているが、2番目の配列には存在しない要素を返す。

Java

AOJ.java

import java.util.*;

public class Main{
    public static void main(String[]args){
        
        ArrayList<String> allCards = new ArrayList<String>();
        String [] suits = {"S","H","C","D"};
        for(String suit:suits){
            for(int i=1;i<=13;i++){
                allCards.add(suit+" "+i);
            }
        }
        
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();
        Set<String> existingCards = new HashSet<>();
        for(int i=0;i<num;i++){
            String cards = sc.nextLine();
            existingCards.add(cards);
        }
        for(String card:allCards){
            if(!existingCards.contains(card)){
                System.out.println(card);
            }
        }
        sc.close();
    }
}
//「すべてのカード」をつくる
//入力をもらう
//「手持ちのカード」をつくり入力されたカードを追加していく
//「すべてのカード」から「手持ちのカード」だけを除いて表示させる

• Scannerは入力をトークンとして読み取るが、nextInt() は 数字の部分だけ を読み取り、改行文字 \n はバッファに残す という動作をする
  →int num = sc.nextInt();で数字を読み取っても改行がバッファに残るため、その次のループ内にあるnextLine()では残った改行を読み取ってしまう
  →そのため、最初の card には 何も入らず空白の出力 になってしまう。
  →sc.nextLine(); を nextInt(); の直後に入れることで、改行を消費し、次の nextLine(); が正しく機能する ようにする

• ArrayListは順序付きのデータの保持に、HashSetは高速な検索と重複排除に強い

• 今回は重複してなかったらそれを表示というコードにしてるけど「重複してたら取り除く」なら以下のようなコード例になる。

• 配列は宣言時にサイズを決める必要があるため、サイズが変わらない場合に適している。

• ArrayList（またはList）は動的にサイズを変更できるため、要素の追加・削除が必要な場合に適している。

removeAll.java

//removeAll()を使う場合
allCards.removeAll(existingCards);
for(String card : allCards) {
    System.out.println(card);
}

iterator.java

//イテレーターを使う場合
Iterator<String> iterator = allCards.iterator();
while(iterator.hasNext()) {
    String card = iterator.next();
    if(existingCards.contains(card)) {
        iterator.remove();
    }
}
for(String card : allCards) {
    System.out.println(card);
}

別解

other.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String suit = "SHCD";
        // 2次元配列で各カードの存在を管理。デフォルトではfalseで初期化される
        boolean[][] exist = new boolean[4][14];  
        int n = scan.nextInt();

        for (int i = 0; i < n; i++) {
            String s = scan.next();
            int num = scan.nextInt();
            exist[suit.indexOf(s)][num] = true;  
        }

        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                if (!exist[i][j]) {
                    System.out.println(suit.charAt(i) + " " + j);
                }
            }
        }
        scan.close();
    }
}
//「すべてのカード」を定義する。あるか否かで判断したいのでboolean型にする。
//　最初は全部ない状態にしておく
//「すべてのカード」配列のうち、持っているカード（要素）をtrueで記録する。
//　「すべてのカード」のうち持っていないカードを表示する。

• suit.indexOf(s)：入力されたスート（S,H,C,D）の文字がsuit文字列の何番目にあるかを返す
  例：'S'なら0、'H'なら1、'C'なら2、'D'なら3
  exist[スートの位置][カードの数字] = trueでそのカードが存在することを記録
• 各カードについて「存在するかしないか」という2つの状態だけを管理すれば良い→boolean型の配列で管理
• charAt()→文字列からn番目の文字列を抜き出す

other2.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();  // 入力されるカードの枚数
        int[][] array = new int[4][13];  // 4スーツ（S, H, C, D）、13枚のカードの存在管理

        // カード情報を入力して、配列に反映
        for (int i = 0; i < a; i++) {
            String suit = scanner.next();  // スーツ（S, H, C, D）
            int number = scanner.nextInt();  // カード番号（1〜13）
            
            // スーツに対応するインデックスにカードを追加
            int suitIndex = getSuitIndex(suit);
            array[suitIndex][number - 1] = 1;  // 配列の番号は0から始まるので、number-1
        }

        // カードが足りないものを出力
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                if (array[i][j] == 0) {  // カードがない場合
                    System.out.println(getSuitName(i) + " " + (j + 1));  // スーツと番号を出力
                }
            }
        }

        scanner.close();  // Scannerのリソースを閉じる
    }

    // スーツ名に対応するインデックスを返す
    private static int getSuitIndex(String suit) {
        switch (suit) {
            case "S": return 0;  // スペード
            case "H": return 1;  // ハート
            case "C": return 2;  // クラブ
            case "D": return 3;  // ダイヤ
            default: throw new IllegalArgumentException("Invalid suit: " + suit);
        }
    }

    // インデックスに対応するスーツ名を返す
    private static String getSuitName(int suitIndex) {
        switch (suitIndex) {
            case 0: return "S";
            case 1: return "H";
            case 2: return "C";
            case 3: return "D";
            default: throw new IllegalArgumentException("Invalid suit index: " + suitIndex);
        }
    }
}

問3.公舎の入居者数(難)

• Ａ大学は１フロア１０部屋、３階建ての公舎４棟を管理しています。公舎の入居・退去の情報を読み込み、各部屋の入居者数を出力するプログラムを作成して下さい。

• n件の情報が与えられます。各情報では、４つの整数b, f, r, vが与えられます。これは、b棟f階のr番目の部屋にv人が追加で入居したことを示します。vが負の値の場合、-v人退去したことを示します。
  最初、全ての部屋には誰も入居していないものとします。

• Input
  最初の行に情報の数 n が与えられます。
  続いて n 件の情報が与えられます。各情報には４つの整数 b, f, r, v が空白区切りで１行に与えられます。

• Output
  ４棟について入居者数を出力して下さい。各棟について、１階、２階、３階の順に入居者数を出力します。各階については、１番目、２番目、・・・、１０番目の部屋の入居者数を順番に出力します。入居者数の前には１つの空白を出力して下さい。また、各棟の間には####################(20個の#)で区切って下さい。

PHP

AOJ.php

<?php
$num = trim(fgets(STDIN));

$zero = array_fill(0,10,0);
$arr = array($zero,$zero,$zero);
$entire = array($arr,$arr,$arr,$arr);

for($i=0;$i<$num;$i++){
    fscanf(STDIN,"%d %d %d %d",$w,$f,$n,$v);
    $entire[$w-1][$f-1][$n-1]+=$v;
}
//$entire の各 寮（棟） を $arr として取得。
foreach ($entire as $i => $arr) {
//$arr の各階（$floor）をループで処理。
    foreach ($arr as $floor) {
        printf(" %s\n", implode(" ", $floor));
    }
    
    if ($i !== 3) {
        echo str_repeat("#", 20) . "\n";
    }
}
//ワンフロアの構造を定義
//全フロアの構造を定義
//全棟の構造を定義（全体としては４次元配列）
//入力からデータを書き換える

?>

• データの入力を受け取る
  →データ構造（4棟 × 3階 × 10部屋）を作成
  →入力される入居・退去データを配列に反映
  →結果を出力。格棟の各階を表示させる。
• $entire配列の実態

arr.php

$entire = [
    [ // 第1棟（$i=0）
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // 1階
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // 2階
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // 3階
    ],
    [ // 第2棟（$i=1）
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    ],
    [ // 第3棟（$i=2）
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    ],
    [ // 第4棟（$i=3）
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    ]
];

• foreachをネストで使う

ex.php

//基本のforeachの使いかた...配列の 各要素を $value に代入してループ処理
$array = [1, 2, 3];
foreach ($array as $value) {
    echo $value . "\n";
}

//foreachのネストでの使いかた(例①二次元配列)...外側から配列を変数に格納→要素を変数に格納
$data = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

foreach ($data as $row) { // 各配列を $row に格納（1行ずつ取得）
    foreach ($row as $num) { // 各値を $num に格納（1つずつ取得）
        echo $num . " ";
    }
    echo "\n"; // 1行ごとに改行
}
//出力
1 2 3 
4 5 6 
7 8 9 

Java

AOJ.java

import java.util.Scanner;

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

        // 配列のサイズ（棟、階、部屋）を定義
        int num[][][] = new int[4][3][10];  

        // 入力データの数
        int n = scan.nextInt();
        for (int i = 0; i < n; i++) {
            int b = scan.nextInt();
            f = scan.nextInt();
            r = scan.nextInt();
            v = scan.nextInt();
            
            num[b - 1][f - 1][r - 1] += v;
        }

       
        for (int i = 0; i < 4; i++) {  // 4棟
            for (int j = 0; j < 3; j++) {  // 3階
                for (int k = 0; k < 10; k++) {  // 10部屋
                    System.out.print(" " + num[i][j][k]);
                }
                System.out.println();
            }
            if (i < 3) {  // 最後の棟には区切りを入れない
                for (int j = 0; j < 20; j++) System.out.print('#');
                System.out.println();
            }
        }
        scan.close();
    }
}

• 3次元の配列でデータを管理→出力も3重ループ

• 入力が1ベース（棟、階、部屋が1から始まる）→配列は0ベースなら-1ひくことで帳尻合わせる

• 今回のように空白有の連続した入力→PHPではfscanfで受け取れたけどjavaだとひとつずつnextInt()等で受け取る。もしくは文字列ならsplit(区切り文字)←文字列配列が返る

問4.ベクトルと行列の積

n×mの行列Aと、m×1の列ベクトルbを読み込み、Aとbの積を出力するプログラムを作成してください。

PHP

AOJ.php

<?php
fscanf(STDIN, "%d %d", $n, $m);

// 行列 A の読み込み
$A = array();
for ($i = 0; $i < $n; $i++) {
    $A[$i] = explode(" ", trim(fgets(STDIN)));
}

// ベクトル b の読み込み
$b = array();
for ($i = 0; $i < $m; $i++) {
    $b[$i] = trim(fgets(STDIN));
}

// 行列とベクトルの積を計算
for ($i = 0; $i < $n; $i++) {// Aの各行ごとに処理
    $sum = 0;// 各行の計算結果を保持
    for ($j = 0; $j < $m; $j++) {
        $sum += (int)$A[$i][$j] * (int)$b[$j];
    }
    echo $sum . PHP_EOL; 
}
?>

• explode() が返す配列の要素は文字列なので注意
• 行列Aとベクトルbの積は、行ごとに内積を計算する
  →1行の各要素と、ベクトルの要素を掛け算して合計を求める処理が必要になる。
  例

ex.php

n = 3, m = 4    // A の行数は 3、列数は 4（b の要素数も 4）
A = [           //外側＄iのループで一行ずつ処理
    [1, 2, 0, 1],
    [0, 3, 0, 1],
    [4, 1, 1, 0]
]
b = [1, 2, 3, 0]//内側＄jのループで同じインデックス同士の要素を掛け算

Java

AOJ.java

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][] A = new int [n][m];
        for(int i = 0;i<n;i++){
            for(int j =0;j<m;j++){
                A[i][j]=sc.nextInt();
            }
        }
        int [] b = new int [m];
        for(int i =0;i<m;i++){
            b[i] = sc.nextInt();
        }
        for(int i =0;i<n;i++){
            int sum =0;
            for(int j =0;j<m;j++){
                sum  += A[i][j]*b[j];
            }
            System.out.println(sum);
        }
        sc.close();
    }
}