AtCoderのプログラミングコンテストに初めて参加してみた！（PHP7）

アカウントだけは数ヶ月前に作ってたんですが、8月4日（日）に開催されたAtCoderの初級者〜中級者向けのプログラミングコンテスト（AtCoder Beginner Contest：ABC）に初めて参加してみました。

参加の理由は、プログラミングコンテストへの純粋な興味と、未経験からのITエンジニア（WEB系）転職にAtCoderのレーティングが活かせるかなと思ったからです。

結果
提出したコード
最後に
- 感想
- 目指せ緑色〜水色

結果

コンテスト成績証 – AtCoder

言語は全てPHP7で、順位は真ん中よりちょい後ろでした。

得点1000点だけ見ると満点っぽいですが、満点は2100点ですw

過去問やってみて今の実力だとDまで解ければ上出来だなという印象だったので、何とか達成出来て良かったです。

まぁ制限時間100分でD解いたのが99分53秒とめちゃくちゃギリギリですがw

当分はDを安定して解けるようになることを目標にしたいと思います。（それまでEとFは僕の中では存在しない）

前準備としては、AtCoder Beginners Selectionを一通りとAtCoder Beginner Contestの過去数回のA〜Dを解いてから参加しました。

提出したコード

A – Transfer


<?php
fscanf(STDIN, "%d %d %d", $a, $b, $c);
echo ($c - min($a - $b, $c)).PHP_EOL;

提出 #6685527 – AtCoder Beginner Contest 136

($c – min($a – $b, $c)) の部分は、 max($c – ($a – $b), 0) でも良かったですね。

B – Uneven Numbers


<?php
fscanf(STDIN, "%d", $n);
$cnt = 0;
for ($i = 1; $i <= $n; $i++) {
    if (strlen($i) % 2 === 1) {
        $cnt++;
    }
}
echo $cnt.PHP_EOL;

提出 #6691444 – AtCoder Beginner Contest 136

特に書くことはないですけど、 mb_strlen だと Call to undefined function で怒られます。

おそらくAtCoderのPHP環境では mbstring が有効になっていないため、 mb_ 系は使えないっぽいです。

C – Build Stairs


<?php
fscanf(STDIN, "%d", $n);
$h = array_map('intval', explode(' ', trim(fgets(STDIN))));
 
for ($i = $n - 1; $i >= 1; $i--) {
    if ($h[$i - 1] === $h[$i] + 1) {
        $h[$i - 1]--;
    } elseif ($h[$i - 1] > $h[$i] + 1) {
        exit ('No'.PHP_EOL);
    }
}
echo 'Yes'.PHP_EOL;

提出 #6698511 – AtCoder Beginner Contest 136

最初は左から順に処理する方法を考えましたが、思い付かなかったので右から順に切り替えました。

入力を格納した配列の値を直接減らしているのがちょっと気持ち悪いので、 $after のような変数を用意して減らした方が良かったかもしれません。

D – Gathering Children


<?php
$s = str_split(trim(fgets(STDIN)));
$n = count($s);
$res = [];
for ($i = 0; $i < $n; $i++) {
    $res[$i] = 0;
}
for ($i = 0; $i < $n; $i++) {
    if ($i < $n - 1 && $s[$i] === 'R' && $s[$i + 1] === 'L') {
        $x = $i;
    }
    if ($s[$i] === 'L') {
        if (($i - $x) % 2 === 0) {
            $res[$x]++;
        } else {
            $res[$x + 1]++;
        }
    }
}
for ($i =  $n - 1; $i >= 0; $i--) {
    if ($i > 0 && $s[$i] === 'L' && $s[$i - 1] === 'R') {
        $x = $i;
    }
    if ($s[$i] === 'R') {
        if (($x - $i) % 2 === 0) {
            $res[$x]++;
        } else {
            $res[$x - 1]++;
        }
    }
}
echo implode(' ', $res).PHP_EOL;

提出 #6711809 – AtCoder Beginner Contest 136

‘RL’ の部分に集まった後は ‘R’ と ‘L’ を行き来するというのは割とすぐ分かりましたが、紆余曲折あって最終的にこんな実装になりました。

左からのループで ‘L’ のみ集計し、右からのループで ‘R’ のみ集計しています。

最初は、各マスについて1回ずつ移動させていき ‘RL’ に入ったらそれまでの移動回数が偶数か奇数かで最終的な位置を決定するという処理を書いたのですが、これだと実行時間オーバーでダメでした。

提出 #6706983 – AtCoder Beginner Contest 136

あとで改善したコード


<?php
// 入力
$s = trim(fgets(STDIN));
 
$n = strlen($s);
 
// 答え出力用配列に0格納
$ans = array_fill(0, $n, 0);
 
// 計算
$top = 0;
while($top < $n) {
    if ($s[$top] === 'R') $next = 'L';
    else $next = 'R';
 
    $next_top = strpos($s, $next, $top);
    if (!$next_top) $next_top = $n;
 
    $cnt = $next_top - $top;
 
    if ($s[$top] === 'R') {
        $x0 = $top + $cnt - 1;
        $x1 = $x0 + 1;
    } else {
        $x0 = $top;
        $x1 = $x0 - 1;
    }
    $ans[$x0] += ceil($cnt / 2);
    $ans[$x1] += floor($cnt / 2);
 
    $top = $next_top;
}
 
// 出力
echo implode(' ', $ans).PHP_EOL;

提出 #6738627 – AtCoder Beginner Contest 136

解説やら他の人のコードやらを参考に改善してみました。結構分かりやすくなったかなと思います。

1番の収穫は array_fill で一発で配列に初期値をセット出来るということを知ったこと。

ただ実行時間やメモリなどはコンテストで提出したコードの方がなぜか優秀な結果でしたw