競プロプレイヤー

聴く音楽のラインナップが固定化されてきた苅田です。

一曲だけGreeeenの愛唄とかなり古い曲が混じってて外すかどうか迷ってましたが結局外すの忘れてそのままでした。

さて、今日は題名にもある通り競プロについてのお話をしたいと思います。

競プロとは競技プログラミングの略で数学の問題みたいなものをプログラミングでいかに早く解くかというのを競い合います。

日本でよく使われる競技プログラミングのサイトとしてAtCoder、Paizaなどがあります。(Paizaは転職サイトなので競技プログラミングというより転職時のスキルチェックという要素が強いですが難易度は低めなので入門にはうってつけです。)

AtCoderは毎週土曜日(コンテストによって異なります)にコンテストが開かれコンテスト中に問題を解ければレートを上げることができますが、参加しなければどんどんレートが下がっていきます。

Paizaは公開されている問題を解けばレートが上がります。

実際にAtCoderの練習問題を解いてみましょう。

問題文

意訳すると入力されたN個の整数がすべて偶数の時、２で割った数字に置き換える。何回操作したときにすべてが偶数でなくなりますか？

これをPHPで解いていきます。

<?php

$n = trim(fgets(STDIN));

$arr = explode(" ", trim(fgets(STDIN)));

$count = 0;
while(true) {
    if (!isAllEven($arr)) {
        echo $count;
        return;
    }

    foreach($arr as $i => $value) {
        $arr[$i] = $value / 2;
    }
    $count++;
}

echo $count;

function isAllEven($arr) {
    foreach($arr as $value) {
        if ($value % 2 != 0) {
            return false;
        }
    }
    return true;
}

<?php

$n = trim(fgets(STDIN));

$arr = explode(" ", trim(fgets(STDIN)));

$count = 0;

while(true) {

if (!isAllEven($arr)) {

echo $count;

return;

}

foreach($arr as $i => $value) {

$arr[$i] = $value / 2;

}

$count++;

}

echo $count;

function isAllEven($arr) {

foreach($arr as $value) {

if ($value % 2 != 0) {

return false;

}

return true;

}

処理の流れを見ていきましょう。

まず何個の整数を入力するかのnとｎ個の整数を入力する処理があります。

PHPの場合nは使うことがないので関係ないですが、競技プログラミングの性質上処理速度を求めるので本来はC、C++向けなのでnというものが設けられてます。

whileで無限ループしています。

競プロではよく使います。

全てが偶数かどうかを判別する。

isAllEven関数の中ですべてが偶数か判断しています。偶数でなかった時点でfalseを返し終了します。これは早期リターンという考え方で無駄な処理をせずに済みます。ifの条件式で!isAllEvenとしています。これも同じ理由で偶数でないものが一つでも含まれているをわかった瞬間countを出力してプログラムを終了します。