Todoistで見積時間から完了予定時刻を計算するChrome拡張機能

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

最後に

感想

AtCoderというかプログラミングコンテスト自体初めてだったのですが、実行時間やメモリの制限を意識しつつ制限時間の中で正しいコードを書くという経験が初めてだったのと、目標のD問題を何とか解けたこともあって、思った以上に楽しめました。

コンテストが終了すると、他の人が提出したコードも言語別に見られるようになるのも勉強になって良いですね。

予想以上に楽しかったので、次回のABCにも参加登録して、対策用にこの書籍も買ってみました。

目指せ緑色〜水色

今はまだレーティングの色が最低の灰色なので、参加回数を重ねて上の色に上げていきたいと思います。(参加回数が5回未満の場合は実力よりもレーティングが大幅に低くなるらしい)

ただITエンジニア(WEB系)への転職の場合、アルゴリズム的な能力の証明よりも、WEBサービスのオリジナルポートフォリオ作成の方が優先順位は高いと思うので、あまりハマり過ぎないように気を付けようと思いますw

以下の記事を読むと、緑色かあわよくば水色までいけば十分アピール出来そうなのでそこを目指したいと思います。

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例 – chokudaiのブログ

今回のコンテスト単独のパフォーマンスが緑色なので、おそらく今後もDまで解ければレーティングも緑色には届いてくるでしょう。多分。

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA


Secured By miniOrange