LoginSignup
90
75

More than 5 years have passed since last update.

ドワンゴAdvent Calendar 2015Day 5
@yoshikyoto(yoshiyuki sakamoto)in株式会社 ドワンゴ

PHPで競技プログラミングしてみた

Last updated at Posted at 2015-12-04

はじめに

この記事は、 ドワンゴ Advent Calendar 2015 の12/5の記事です。

私は、大学院1年の終わりごろから競技プログラミングを始め、大学院を卒業後ドワンゴに入社し、業務ではScala, PHP の2つの言語を利用してきました。PHPはほぼ初めて触りました。私は、初めて触る言語は、とりあえず競技プログラミングの問題を解きながら慣れることにしているため、今回は競技プログラミングでPHPを使った話をします。

PHPが使える競技プログラミングサイトは、AtCoderやAizu Online Judgeなどがあります（topcodeでは残念ながら使えません）。今回はAtCoderの問題を解いてみました。

競技プログラミングとは

数学的な問題が与えられるため、それを解くプログラムを時間内になるべく早く書くという競技です。実行時間やメモリに制限があるため、一筋縄では行かない場合があります。
後に問題と解答が出てくるので、それを見るとイメージが付きやすいかと思います。

AtCoderとは

AtCoder (http://atcoder.jp/) は、AtCoder社が運営する、数少ない日本語の競技プログラミングサイトです。 ドワンゴからの挑戦状 など、エンジニアの採用に繋がるようなコンテストも実施しています。今年は、第2回ドワンゴからの挑戦状 なるものもあるらしいです。 べつにこれを書きたいが故にこの記事を書いたわけではありません。AtCoderは使用できる言語が多いのが魅力です。

今回はこのAtCoder問題をいくつか解いてみることにします。

標準入出力

競技プログラミングでは標準入出力を扱うことが多いですが、いろいろと面倒なことも多いので、ラッパークラスを書きます。

標準入力

プログラミングコンテストでは、標準入力を受けてスペース区切りでパースする必要があるのですが、毎回それを書くのは面倒なので、便利クラスを適当に作ります。

class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}

これで

$sc = new Scanner();
$n = $sc->nextInt();

とするだけで、空白区切りのintを受け取ることができます。JavaのScannerみたいなものです。

標準出力

この手のプログラミングコンテストは、解答を出力して最後に改行を入れる、というのが定番で、初心者は改行を忘れて誤答判定を受けるのがテンプレです。これもなるべく楽をしたいので便利クラスを適当に作ります。

class out {
    public static function println($str = "") {
        echo $str . PHP_EOL;
    }
}

とりあすコンテストに参加してみた

取り合えず標準入出力だけ準備して、AtCoder Beginnter Contest 029 に参加してみました。

2時間で4問を解く簡単なコンテストです。結果はこちら。

20150919224204.png

20150919224200.png

全問正解して、 66位/470人くらい中 でした。AC とは Accepted、つまり「正解した」ということです。WA は Wrong Answer、つまり「誤答した」ということです。AtCoderでは誤答を提出すると5分のペナルティが課されます。全問正解で満点なのですが、同点の場合は解答までの時間が早い方が上位になるので、僕は66位とまりました。
詳しくは 僕のブログ を参考にしてください。

いくつか典型的な問題を解いてみる

これだけではよくわからないので、いくつか問題を解いてみました。その中で、競技プログラミングでよくある問題をピックアップして紹介し、競技プログラミングにおけるPHPの特徴や、PHPを使うメリット・デメリットについて考えてみます。

※以下、入出力クラス部分は省略します。

数値計算

問題: 勝率計算

試合数と勝数が与えられるので、勝率を計算して、どちらの勝率が高いかを出力するだけの問題です。

$sc = new Scanner();
$a = $sc->nextInt(); // 高橋くんの試合数
$b = $sc->nextInt(); // 高橋くんの勝利数
$c = $sc->nextInt(); // 青木くんの試合数
$d = $sc->nextInt(); // 青木くんの勝利数

$takahashi = $b / $a; // 高橋くんの勝率
$aoki = $d / $c;      // 青木くんの勝率

// どっちが勝率が高いか
if($takahashi > $aoki) {
    out::println('TAKAHASHI');
} else if($takahashi < $aoki) {
    out::println('AOKI');
} else {
    out::println('DRAW');
}

PHP独特な点としては、int同士で除算をしたときに、勝手にfloatに変換される点です。知らないとはまりそうですが、コードは直感に即した感じになります。クラスも作らなくて良いので、かなりスッキリしたコードになります。

文字列操作

問題: 複数形

入力文字列に 's' を付けて出力するだけの問題。

$sc = new Scanner();
$s = $sc->next();
out::println($s . 's');

文字列の結合は + ではなくて . なので注意が必要です。

問題: カキ

文字列にrが含まれているかどうかをチェックする問題。

$sc = new Scanner();
$cnt = 0;
for($i = 0; $i < 12; $i++) {
    $str = $sc->next();
    for($j = 0; $j < strlen($str); $j++) {
        if($str[$j] === 'r') {
            $cnt++;
            break;
        }
    }
}

out::println($cnt);

$str[0] とかでその文字を取り出すことができます。競技プログラミングにおいてはかなり便利な仕様です。

for文を書く時にもいちいち $ を書くのは面倒ですが、for はよく使うのでいい感じにテンプレート登録しておきましょう。

再帰/深さ優先探索

問題: 倍々ゲーム

この辺りから一言では説明しづらい問題なのですが、再帰（深さ優先探索）で解く問題です。

// 入力
$sc = new Scanner();
$n = $sc->nextInt();
$player = [0 => 'Takahashi', 1 => 'Aoki'];

// このターン数になった時の位置で勝敗が決まる
$border_turn = (int)log($n, 2) + 1;
// $border_turn % 2 === 1 の場合、$border_turn は高橋くん
// この時高橋君は下に行きたがることになるので
$takahashi = $border_turn % 2;
$aoki = 1 - $takahashi;
$direction = [0 => $takahashi, 1 => $aoki];

// これを元に探索
function dfs($x, $turn) {
    global $n;
    if($n < $x) {
        return $turn;
    }
    global $direction;
    return dfs(2 * $x + $direction[$turn], 1 - $turn);
}

out::println($player[dfs(1, 0)]);

関数の外で宣言されている変数を利用する場合は、 global 宣言をしなければいけません。関数の中身がグローバル変数で汚染されることはないので、普通なのですが、知らないとハマるかもしれません。引数が異常に多くなったりしないので、こちらも見た目がすっきりします。

もしクラスを作成するなら以下のような感じになります。

class Main {
    static $n;
    static $direction;

    public static function solve() {
        // 入力
        $sc = new Scanner();
        self::$n = $sc->nextInt();
        $player = [0 => 'Takahashi', 1 => 'Aoki'];

        // このターン数になった時の位置で勝敗が決まる
        $border_turn = (int)log(self::$n, 2) + 1;
        // $border_turn % 2 === 1 の場合、$border_turn は高橋くん
        // この時高橋君は下に行きたがることになるので
        $takahashi = $border_turn % 2;
        $aoki = 1 - $takahashi;
        self::$direction = [0 => $takahashi, 1 => $aoki];

        return $player[self::dfs(1, 0)];
    }

    // これを元に探索
    public static function dfs($x, $turn) {
        if(self::$n < $x) {
            return $turn;
        }
        return self::dfs(2 * $x + self::$direction[$turn], 1 - $turn);
    }
}

out::println(Main::solve());

グローバル宣言の代わりに self:: になっているだけです。問題によって使い分けると良いかもしれません。

豆知識ですが、競プロで dfs という名前の関数が出てきた場合、それは深さ優先探索(depth-first search)または再帰のコードです。bfsは幅優先探索です。

動的計画法

問題: ロボット

部分点が動的計画法で解けます。

// 入力
$sc = new Scanner();
$s = $sc->next();
$n = strlen($s); // 命令の長さ

// 部分点狙う
if($n > 1000) exit;

$prev = [];
$prev[0] = 0;
for($i = 0; $i < $n; $i++) {
    $curr = [];
    foreach($prev as $position => $value) {
        $ope = substr($s, $i, 1);
        if($ope === '+') {
            $nextValue = $prev[$position] + $position;
            if(!array_key_exists($position, $curr)) {
                $curr[$position] = $nextValue;
            } else {
                $curr[$position] = max($curr[$position], $nextValue);
            }
        } else if($ope === '-') {
            $nextValue = $prev[$position] - $position;
            if(!array_key_exists($position, $curr)) {
                $curr[$position] = $nextValue;
            } else {
                $curr[$position] = max($curr[$position], $nextValue);
            }
        } else if($ope === 'M') {
            // +1
            if(!array_key_exists($position + 1, $curr)) {
                $curr[$position + 1] = $prev[$position];
            } else {
                $curr[$position + 1] = max($curr[$position + 1], $prev[$position]);
            }
            // -1
            if(!array_key_exists($position - 1, $curr)) {
                $curr[$position - 1] = $prev[$position];
            } else {
                $curr[$position - 1] = max($curr[$posision - 1], $prev[$position]);
            }
        }
    }
    $prev = $curr;
}
Out::println($curr[0]);

PHPの配列は特殊で、 配列＝連想配列 になっています。つまり、キーには 何でも（intでない値も、型が混在していても） 取れるので、マイナスの値をキーにすることができます。これがDPをするにあたり非常に便利です。
その他に、DPあるあるとして、「配列を0で初期化してしまい、"最適解が0である状態"と、"初期化して値がまだ入っていない状態"を区別できていなかった」バグがあると思います。 array_key_exists 関数を使うことによって、そのようなバグは回避できます。ただし、記述量は増えます。

これもまた競プロ豆知識なのですが、dp という名前の配列が出てきたら、それは動的計画法(dynamic programming)かメモ化再帰のコードです。

問題を解いてみた感想

  • 標準入出力ラッパークラスがないと異常に苦痛なプログラミングになる
    • C++のcinの便利さを実感する
  • 全体的に記述が簡潔になるため、タイプ量は少なめで、コードもすっきりする
  • ただし、複雑な問題になり、クラスを使いはじめると、global, $this->, self:: が増加し、途端に記述量が増える。
  • 配列のキーになんでも取れるなど、わりと何でもできるゆるふわ言語のため、競プロにおいては便利なことが多い
  • ゆるふわ故バグに気づかないことがある
    • 存在していないメソッドを呼んでいても、普通に実行できたりする
  • $をいちいち書くのが面倒かと思いきや、慣れると特に何も思わなくなってくる
    • ただし$を忘れていて怒られるのはあるある
  • <?php をコピペしてなくて爆死することがある
  • PHPで解いている人が少ないため、言語:PHP で絞ると、正解者が自分だけだったりする。優越感に浸れる。
    • 強い人は大体C++とか使ってるので

特に一番最後はポイントが高いな、と思いました。

まとめ

そこまで大きな問題でなければ、すっきりかけるので、競プロ向きな言語ではないかなぁと思います。問題の種類によって、記述が楽な言語、複雑な言語、様々あると思うので、言語の選択肢が多いことは良いことだと思います。

1/23（金）に、第2回ドワンゴからの挑戦状の予選があるので、みなさんぜひ参加してみましょう。 賞金が出たりするみたいです。

90
75
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
90
75