AOJ PG入門 #9

問1.１つの単語 W と文章 T が与えられます。T の中にある W の数を出力するプログラムを作成して下さい。

• input
  １行目に単語 W が与えられます。
  続いて、複数の行にまたがった文章与えられます。END_OF_TEXT という文字列が文章の終わりを示します。
• output
  単語 W の数を出力して下さい。

PHP

AOJ.php

<?php
$w = strtolower(trim(fgets(STDIN)));
$cnt = 0;
while(true){
    $line = trim(fgets(STDIN));
    if($line == "END_OF_TEXT")break;
    $array = explode(" ",strtolower($line));
    foreach($array as $arr){
        if($arr == $w)$cnt++;
    }
}
echo $cnt."\n";
//文字列(単語)wを受け取る。大文字小文字の区別をなくすため全部小文字にする computer
//複数文字列を受け取る（while）END_OF_TEXT という文字列でbreak。小文字にしてから配列に格納。
//ループで配列内の文字列検索していく。カウント変数を用意し、該当文字列があればカウント増やす
?>

• strpos() は部分一致になるので使ってない

別解

other.php

<?php
	$w = trim(fgets(STDIN));
	$cnt = 0;
	while (!feof(STDIN)) {
		$t = trim(fgets(STDIN));
		$cnt += preg_match_all("/\b".$w."\b/i", $t, $match);
	}
	echo $cnt . "\n";

• feof()関数は、開いているファイルの「ファイルの終わり」(EOF)に達したかどうかをチェックする
  →feof(STDIN) は 標準入力 (STDIN) の終端に達したら true になるので、 !feof(STDIN) で EOFに達するまでループ
• preg_matchは検索対象である文字列を発見したらそこで1を返して処理を終了する
• preg_match_allは文字の最後まで検索を行うため今回のようにマッチ回数などを取得したい場合などに適している。戻り値はパターンがマッチした総数

Java（イテレーター、Pattern,Matherクラス練習用解法）

AOJ.java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.regex.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 単語 W を受け取る
        String w = sc.nextLine().toLowerCase();
        int cnt = 0;
        
        ArrayList<String> arrays = new ArrayList<String>();
        
        // 文章の入力を受け取る
        while (true) {
            String t = sc.nextLine();
            if (t.equals("END_OF_TEXT")) break;
            arrays.add(t.toLowerCase());
        }

        // 正規表現を使って検索
        Pattern p = Pattern.compile("\\b" + w + "\\b");  // 正規表現パターン作成
        Iterator<String> it = arrays.iterator();

        // 配列内の各行について調べる
        while (it.hasNext()) {
            String line = it.next();　//Iterator の現在位置にある要素を変数lineに格納
            Matcher m = p.matcher(line);
            //指定した文字列に対してマッチングを行うための Matcher オブジェクト を作成

            // マッチする単語がある場合はカウント
            while (m.find()) {
                cnt++;
            }
        }
        
        // 結果を表示
        System.out.println(cnt);
    }
}

• arrays.iterator() で、ArrayList の各要素を順番に取り出すための Iterator オブジェクト を作成
• Pattern クラスは、正規表現パターンを定義するために使用。
• Pattern.compile() メソッドには、正規表現を文字列として引数に渡し、それに基づいた Pattern オブジェクトを返す。今回の正規パターンは単語 w の前後に他の文字がない場合にのみ、つまりw が完全に独立した単語として現れる場合にだけ一致するというもの
• matcher() は Pattern クラスのメソッド で、Matcher オブジェクト を作成する。
• Matcher クラスは、指定した文字列に対して Pattern を適用し、一致する部分を検索するために使用。
• Matherクラスのmatherメソッドの引数に検索対象文字列を指定
• Matherクラスのfindメソッドで一致しているか調べる
• newしてインスタンス化ができないのは抽象クラスかコンストラクタがprivate指定されているもの。
• 抽象クラスだった場合、サブクラスはnewできる。
• コンストラクタがprivate指定されている場合そのクラスの外部から new できないがクラス内部のメソッドで new することは可能
• PatternクラスもMatherクラスもjava.util.regexに属する。どちらもコンストラクタがprivate指定されておりnewしてインスタンスを作成することができない。

別解（むしろこっちが正解）

other.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        String W=scan.next();
        W=W.toLowerCase();
        int ans=0;
        while(true){
            String T=scan.next();
            if(T.equals("END_OF_TEXT"))break;
            T=T.toLowerCase();
            if(T.equals(W))ans++;
        }
        System.out.println(ans);
        scan.close();
    }
}

問2 シャッフル

１つのアルファベットが描かれた n 枚のカードの山をシャッフルします。

1回のシャッフルでは、下から h 枚のカードをまとめて取り出し、それを残ったカードの山の上に積み上げます。

カードの山は以下のように１つの文字列で与えられます。

abcdeefab

最初の文字が一番下にあるカード、最後の文字が一番上にあるカードを示しています。

例えば、これを h が 4 でシャッフルすると、最初の4文字 abcd が、残りの文字 eefab の末尾へ連結されるので以下のようになります：

eefababcd

このシャッフルを何回か繰り返します。

カードの山の最初の並び（文字列）と h の列を読み込み、最後の並び（文字列）を出力するプログラムを作成して下さい。

• input
  複数のデータセットが入力として与えられます。各データセットは以下の形式で与えられます：

最初の並びを表す文字列
シャッフル回数 m
h1
h2
  .
  .
hm

最初の並びを表す文字列が "-" のとき入力の終わりとします。

• output
  各データセットに対して、最後の並び（文字列）を１行に出力して下さい。

PHP

AOJ.php

<?php

while (true) {
    $line = trim(fgets(STDIN));
    if ($line === "-") break; // 入力が "-" なら終了

    $input = str_split($line); // 文字列を配列に変換
    $m = intval(trim(fgets(STDIN))); // シャッフル回数

    for ($i = 0; $i < $m; $i++) {
        $h = intval(trim(fgets(STDIN))); // h を取得
        $bottom = array_splice($input, 0, $h); // 下から h 枚を取り出し
        $input = array_merge($input, $bottom); // 上に積む
    }

    echo implode("", $input) . PHP_EOL; // 結果を出力
}
//文字列が "-" ではない場合最初の並びを表す文字列を受け取り、配列に入れる。
//シャッフル回数 mをうけとる
//m回ループ内でhをうけとる
// h 文字分を取り出して、文字列の末尾に連結して更新
?>

• array_splice関数は、配列の任意の場所に要素を追加したり、既存の要素を置き換えたり削除したりといった処理を行う。書式は→array_splice(配列, 開始位置, 取り出す個数);
  →指定した位置から、指定した個数の要素を 配列から取り出し、元の配列を更新する。
  取り出した要素は返り値として取得できる。
• 今回の挙動としては＄input の先頭 h 個の要素を取り出し、それを ＄bottom に格納する。（$input から取り出された部分は 削除される）つまり、array_splice() を使うことで、先頭の h 個を削除しつつ、削除した部分を ＄bottom に取得できる。
• なお、array_sliceだと元の配列は変更されない（削除や更新はなくて、ただ要素をコピペして新しい配列に入れるだけのイメージ）＆開始位置が負の値だと配列の後ろから取得する
• array_merge（複数の配列を結合し、新しい配列を作成する）で切り取り済みの配列と切り取った配列を結合する
  挙動をコードに起こすとこんな感じ

ex.php

$input = ['a', 'b', 'c', 'd', 'e'];
$h = 2;

// 先頭2つ（['a', 'b']）を取り出し、$bottom に格納
$bottom = array_splice($input, 0, $h);

// 結果
print_r($bottom); // ['a', 'b']
print_r($input);  // ['c', 'd', 'e']

$input = array_merge($input, $bottom);

// 結果
print_r($input); // ['c', 'd', 'e', 'a', 'b']

別解

other.php

<?php
	while (true) {
		$card = trim(fgets(STDIN));
		if ($card == "-") break;

		$m = trim(fgets(STDIN));
		for ($i = 0; $i < $m; $i++) {
			$h = trim(fgets(STDIN));
			$card = substr($card, $h) . substr($card, 0, $h);
		}
		echo $card . "\n";
	}

• substr(＄card, ＄h) → $card の h 文字目以降 を取得
• substr(＄card, 0, ＄h) → $card の先頭から h 文字分 を取得
• つまりこのコードは h 文字分を取り出して、文字列の末尾に連結する動作をしている（挙動的にはarray_splice,array_mergeと同じ）

Java

AOJ.java

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        while(true){
        String line = sc.nextLine();
        if(line.equals("-"))break;
        int m = sc.nextInt();
        for(int i =0;i<m;i++){
            int h = sc.nextInt();
           line = line.substring(h)+line.substring(0,h);
        }
        System.out.println(line);
        sc.nextLine(); //改行消費
        //最初の並び文字列を受け取る
        //シャッフル回数mを受け取る
        //m回、h枚を受け取り文字列の先頭からh文字を切り取って末尾に連結し更新→substring()
        }
        sc.close();
    }
}

• 別の問でもあったが、Java の Scanner クラスで nextInt() を使うと、数値を読み取った後、入力の改行（Enter キー）を消費しないため改行が入力バッファに残る→そのあとnextLine() を使うと、その残った改行文字（空の行）を読み取ってしまうことがあるため、意図しない動作が発生する。
• よって対策としてnextInt()のあとにnextLineで改行を消費する
• この問題を解く過程で文字列を受け取って一文字ずつ配列に格納するアイデアを考えたがその際迷ったのはsplit()かcharAt()どちらがいいのかということ
  →メモリ効率やパフォーマンス速度的にcharAt（ただしループが必要）のほうがいいらしいのでここにメモとして残しておく

問3.カードゲーム

太郎と花子がカードゲームをする。二人はそれぞれn枚のカードを持っており、nターンの勝負を行う。各ターンではそれぞれ１枚ずつカードを出す。カードにはアルファベットからなる動物の名前が書かれており、辞書順で大きいものがそのターンの勝者となる。勝者には３ポイント、引き分けの場合にはそれぞれ１ポイントが加算される。

太郎と花子の手持ちのカードの情報を読み込み、ゲーム終了後のそれぞれの得点を出力するプログラムを作成せよ。

• input
  一行目にカードの数ｎが与えられる。続くn行に各ターンのカードの情報が与えられる。１つ目の文字列が太郎のカードに書かれている文字列、２つ目の文字列が花子のカードに書かれている文字列である。
• output
  １つ目の数字が太郎の得点、２つ目の数字が花子の得点として１行に出力せよ。２つの数字の間に１つの空白を出力せよ。

PHP

AOJ.php

<?php
$n = trim(fgets(STDIN));
$cntT = 0;
$cntH = 0;
for ($i = 0; $i < $n; $i++) {
    list($line1, $line2) = explode(" ", trim(fgets(STDIN))); // 1行から2つの単語を取得
    $result = strcmp($line1, $line2);
    
    if ($result > 0) {
        $cntT += 3;
    } elseif ($result < 0) {
        $cntH += 3;
    } else {
        $cntT += 1;
        $cntH += 1;
    }
}
echo $cntT." ".$cntH."\n";
//カードの枚数を入力からもらう
//n回のループ内で2個ずつ文字列の入力をもらう
//それぞれの点数を保持するcntT,cntHを用意する。0で初期化
//文字列の大きさ比較→n1とn2を比較する。strcmp(n1,n2)→戻り値は$resultに格納
//→正の値が返る=n1>n2なのでcntTに+3,0が返る＝n1=n2なのでcntTにもcntHにも+1,負の値が返る=n1<n2なのでcntHに+3
//cntT,cntHを表示
?>

• 入力が1行に2単語なのでもらい方としては＄line1 = fgets(STDIN);,＄line2 = fgets(STDIN);とするよりexplode→list使った方がシンプル
• strcmp()→文字列の大小比較をしてくれる（辞書順）。strcmp(string ＄string1, string ＄string2)でstring1 が string2 よりも小さければ -1 を、string1が string2よりも大きければ 1 を、 等しければ 0 を返す。なお、この比較は大文字小文字を区別する。大文字小文字を区別しないのはstrcasecmp()

Java

AOJ.java

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine(); // 改行を消費
        int cntT=0;
        int cntH = 0;
        for(int i = 0;i<n;i++){
            String input = sc.nextLine();
            String array [] = input.split(" ");
            int result = array[0].compareTo(array[1]);
            if(result>0)cntT+=3;
            else if(result==0){
                cntT+=1;
                cntH+=1;
            }
            else cntH+=3;
        
        }
        System.out.println(cntT+" "+cntH);
        sc.close();
        //カードの枚数nを受け取る
        //それぞれのポイントを保持する変数cntT,cntHを用意する
        //n回入力を受け取って処理するというループ
        //一行のString入力を受け取る。空白でsplitして配列にまとめる cat dog
        //二つを小文字に変換したうえでcompareToメソッドで二つの要素を比較→返り値が正の値なら+3,0なら+1
        //ループを抜けて計算結果を出力
    }
    
}

• 今回問題の制約に「アルファベットの小文字のみを含む」 とあるため、小文字変換はしていない。

問4　文字列変換

文字列strに対して、与えられた命令の列を実行するプログラムを作成してください。命令は以下の操作のいずれかです：

• print a b: strの a 文字目から b 文字目までを出力する。
• reverse a b:strの a 文字目から b 文字目までを逆順にする。
• replace a b p:strの a 文字目から b 文字目までを p に置き換える。
  ここでは、文字列strの最初の文字を 0 文字目とします。
• input
  1 行目に文字列strが与えられます。strは英小文字のみ含みます。2 行目に命令の数qが与えられます。続くq行に各命令が上記の形式で与えられます。
• output
  各 print 命令ごとに文字列を１行に出力してください。

PHP

AOJ.php

<?php
$str = trim(fgets(STDIN));
$q = intval(trim(fgets(STDIN)));

for($i = 0; $i < $q; $i++){
    $arr = explode(" ", trim(fgets(STDIN)));
    
    $cmd = $arr[0];
    $a = intval($arr[1]);
    $b = intval($arr[2]);
    $len = $b - $a + 1;
    
    if($cmd == "print"){
        echo substr($str, $a, $len) . "\n";//$a 文字目から $len 文字分を取得
    }
    else if($cmd == "reverse"){
        $segment = substr($str, $a, $len);
        $reversed = strrev($segment);
        //前半部分(0文字目から $a 文字目の 直前 まで) + 逆順にした部分($a 文字目から $b 文字目までを逆順にした文字列) + 後半部分($b + 1 文字目から末尾)
        $str = substr($str, 0, $a) . $reversed . substr($str, $b + 1);
    }
    else if($cmd == "replace"){
        $p = $arr[3];
        $str = substr($str, 0, $a) . $p . substr($str, $b + 1);
    }
}
?>

• ＄b - ＄a だと 4 - 1 = 3 で「1文字目, 2文字目, 3文字目」になってしまう
  でも 1文字目から4文字目まで を取るには +1 しないと最後の文字が含まれない

Java

AOJ.java

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int q = sc.nextInt();
        sc.nextLine();
        for(int i = 0;i<q;i++){
             // 命令を空白区切りで配列に格納
            String[] command = sc.nextLine().split(" ");
            String type = command[0];
            int a = Integer.parseInt(command[1]);
            int b = Integer.parseInt(command[2]);
            if(type.equals("print")){
                System.out.println(str.substring(a,b+1));
            }else if(type.equals("reverse")){
                 StringBuilder sb = new StringBuilder(str.substring(a, b + 1));
                    sb.reverse(); // 反転
                    str = str.substring(0, a) + sb + str.substring(b + 1);
            }else{
                String p = command[3];
                String sb = str.substring(a,b+1);
                str = str.substring(0, a) + p + str.substring(b + 1);
            }
        }
        sc.close();
    }
}

• substring(a, b) は a から b - 1 までを返すので注意
• substring()→引数一つのときは「指定したインデックス番号から右側の文字を切り出す」ことに注意