やってみよう！競技プログラミング

はじめまして、UXシステム開発部のチダです。
花粉にめげずに春風に立ち向かう毎日です。

写真は神棚にご神体として顕現していたうちのこ（長女）です。
他にもキジトラとチンチラを飼っています。
多頭飼いだと賑やかで退屈しないのがいいですね。

…賑やかすぎて、夜中テンションが上がった長女によく起こされますが。

―――

さて本題。
みなさんは競技プログラミングという単語を聞いたことはあるでしょうか？

聞いたことがない！という方に説明しますと

1. お題が出される
2. 要件を満たすプログラムを書く
3. 速さ（解くまでの速さ、プログラムの実行速度）と精度を競う

といった競技です。

私は開発を仕事にして3年ですが、その間の勉強法の一つとして競技プログラミングに参加していました。
参加することのメリットとして、様々なアルゴリズムの習得ももちろんですが
標準入出力、条件式、繰り返し、配列操作等の基本構文を必ず用いることになるので
「あの言語触ってみたいけどきっかけがなぁ～」といった時のスタートとしても適切かと思います。

~~個人的にはパズルゲームを解いている感覚に近いので、遊び半分でもあったりしますが。~~

さて、そんな競技プログラミング、どこではじめればいいのかと言いますと
日本語であること、問題数の充実、コンテストの開催頻度の高さからAtCoderがオススメです。

試しにチュートリアルにあるように、AtCoder Beginners Selectionにある問題からいくつか抜粋して
弊社で主に用いているPHPで解いてみようと思います。

ABC081A – Placing Marbles

やることは単純で、入力された文字列にいくつ「1」が含まれているかを数えて出力するだけです。
一文字ずつ分割して配列にし、すべて比較して数えるのが一番素直な方法でしょうか。

<?php
fscanf(STDIN, "%d", $s);
$r = 0;
foreach (str_split($s) as $v) {
  if ($v === '1') {
    $r++;
  }
}
echo $r;

…実はPHPの場合、標準関数にsubstr_count()があるので、これでもOKだったりします。

<?php
fscanf(STDIN, "%s", $s);
echo substr_count($s, '1');

AC085B – Kagami Mochi

問題文通り素直にいくなら標準入力で受け取った配列を作って降順ソートして前のkeyと比較して小さかったら答えに+1して・・・

となりますが、もっと単純にできます。
最後まで走査するのだから実は順番は関係無くて、ユニークな数の個数を数えれば十分ですね。

<?php
fscanf(STDIN, "%d", $ln);
$d = [];
for ($i=0; $i < $ln; $i++) {
  fscanf(STDIN, "%d", $k);
  $d[$k] = true;
}
echo count($d);

平面があって、毎秒必ず移動するので総移動距離は必ずtになります。
つまり (x, y)までの距離＜ t がゴールへの必要条件（1）です。
また、必ず移動するため同じマスに留まりたいときは距離1の移動を1往復する必要があります。
つまり(1)が満たされているとき、(x, y)までの距離 + 2 * 往復回数 = tで十分条件となります。
そのためには(x, y)までの距離とtの偶奇が一致していれば十分です。
あとはこれをプログラムに起こすだけとなります。

<?php
fscanf(STDIN, "%d", $ln);
$t = [0];
$x = [0];
$y = [0];

for ($i=1; $i<=$ln; $i++) {
  fscanf(STDIN, "%d %d %d", $a, $b, $c);
  $t[$i] = $a;
  $x[$i] = $b;
  $y[$i] = $c;
}

$result = true;

for ($i=0; $i<$ln; $i++) {
  $dt = $t[$i+1] - $t[$i];
  $dist = abs($x[$i+1] - $x[$i]) + abs($y[$i+1] - $y[$i]);
  if ($dt < $dist) {
    $result = false;
    break;
  }
  if ($dt % 2 !== $dist % 2) {
    $result = false;
    break;
  }
}

echo $result ? 'Yes' : 'No';

このようにゴリ押すものから数学的な解法が使えるものまで、様々なアプローチを試すことができる問題がそろっています。
書いたコードが合っているかどうか、オンラインで即採点してくれるので助かりますね。

ちなみに、他の人がどうやって解いているのか気になる人は
【提出一覧】→【検索】→【詳細】で実際に書かれたコードを見ることもできます。

なので、「Ｄ問題何度やってもWA（Wrong Answer:不正解）だ！どこが間違っているのかすら分からない…。」とか
「TLE（Time Limit Exceeded:実行時間制限オーバー）しちゃったけど他の人はどうやって処理を短くしたんだ？」
といった時に他の人のコードから学んで、どこがダメだったのかをはっきりさせるのもgood✨

また、今回解いた問題と同程度の出題がされる
AtCoder Begginer Contestと題される初心者向けのコンテストも（ほぼ？）毎週開催されているので
興味を持った人はぜひ参加してみましょう！
~~そしてフルボッコにされて~~自分の実力がどの程度の位置にいるかを把握するのは大切なことです。

書いている私自身はと言うとARCでまったく歯が立たない程度です…

ここで学んだことは、もちろん実務にも活きてくるので
少しでもプログラミングに興味がある人はぜひ一度触ってみることをオススメします。

ご精読ありがとうございました。