はじめに
Webエンジニアのりゅうです。
これまで競プロにはあまり触れてこなかったのですが、アルゴリズム力を高めたいという気持ちに加えて、自分がどこまでできるのかを試してみたいと思い、AtCoder Beginner Contestに初参加してみました。
投稿が遅くなってしまいましたが、この記事では初めての参加で感じたことや当日の流れをまとめています。
これから挑戦してみたい方や同じように競プロ初心者の方の参考になれば幸いです。
当日の流れ
前日に参加登録を行い、9月14日 21時から開催されたAtCoder Beginner Contest423にRatedで参加しました。
AtCoderでは、参加方式としてRatedとUnratedを選べます。
Unratedは、特別な事情でパフォーマンスが出せない場合のみに選択するものになるため、基本的にRatedで参加となります。
（※参考：公式の説明ページはこちら → Rated/Unrated登録機能追加のお知らせ）
使用言語は普段から慣れているPHPを選びました。
問題ページではコードを直接テスト実行できないため、最初は「どうやって進めればいいのだろう」と迷いました。
そのため、主にコードテスト用ページを使用して問題を解きました。
別タブでコードテスト用ページを開き、その中でコードを書き問題文に記載された入力例を使用して動作確認を行いました。
標準出力の結果が問題文の期待する出力と一致したことを確認してから、問題ページの下部の提出フォームにコードを貼り付けて提出する手順で進めました。
結果と振り返り
結果としては、A〜GのうちB問題だけ正解でした。
まずはA問題から取り組みましたが、テストケースの一部が通らず、約30分ほど格闘したものの解決できませんでした。
その後、B問題に切り替えたところ、約20分ほどで解くことができました。
続いてC問題に取り組もうとしましたが、問題文を読んだ時点で残り時間では間に合わないと判断し、再びA問題に戻りました。
残り時間で再挑戦しましたが、結局A問題は解けず、D～Gは時間が足りず問題文を読むことすらできませんでした。
Aの振り返り
問題URL：https://atcoder.jp/contests/abc423/tasks/abc423_a
この問題は、銀行から1000円単位でのみ引き出しが可能で、引き出し額が1000円増えるごとに手数料も増加していきます。
その条件のもとで、残高に対していくらまで引き出せるかを求める問題でした。
不正解でしたが、私の処理の流れは以下の通りです。
- 残高を
x、手数料を「出金額1000円ごとにc円」とする - 必要な金額を「出金額 + 手数料の合計」とみなす
- 「出金額 + 手数料の合計」が残高
xを超えない最大の出金額を、whileで探す
以下が実際に提出したコードです。
<?php
fscanf(STDIN, "%d %d", $x, $c);
// 引き出し可能額
$a = $x;
// 引き出せない場合のチェック
if($a - $c < 1000){
echo 0;
}else{
while($x < $a + ($a * ($c / 1000))){
$a = $a - 1000;
}
echo $a;
}
考え方
もっとシンプルに考えることができました。
残高をx、手数料を「1000円引き出すごとにc円」とすると、
- 1000円引き出すたびに、実際には
1000 + c円残高から減る - 「
xから1000 + cを何回引けるか」を数える - その回数に
1000を掛けたものが、引き出せる最大金額になる
という方針に落とし込めます。
式にすると、x // (1000 + c)回だけ引き出せるので、 - 引き出せる金額 =
1000 * (x // (1000 + c))
と一行で書けます。
今回の自分のコードでは、「出金額 + 手数料の形でwhileを使用してシミュレーションする」という方針を取ってしまい、考え方や実装も複雑になっていました。
次回以降は、まず1回あたりいくら減るのか、何回繰り返せるかという視点で シンプルな式にできないか考えてから実装するようにしたいです。
Bの振り返り
問題URL：https://atcoder.jp/contests/abc423/tasks/abc423_b
この問題は、2人が移動する中で、どちらのルートからも到達できない部屋の個数を求める問題でした。
2人は、それぞれ部屋0と部屋Nにいる状態からスタートします。
私は、「部屋0から部屋Nに到達するまでに最初に閉まっている扉の位置」と「部屋Nから部屋0に到達するまでに最初に閉まっている扉の位置」の差が、2人のどちらからも到達できない部屋の数になると考えました。
処理の流れは以下の通りです。
- 閉まっているすべての扉の位置
iを取得する - 扉が1つも閉まっていない場合は
0を出力する - それ以外の場合、最初と最後に閉まっている扉の位置の差を出力する
以下が実際に提出したコードです。
<?php //提出したコード
fscanf(STDIN, "%d", $n);
$line = fgets(STDIN);
$array = explode(" ", $line);
// 閉まっている全て扉の位置iを取得
$keys = array_keys($array, 1);
// 閉まっている扉がない場合
if(empty($keys)){
// 全ての部屋に到達できるため、0を返す
echo 0;
// 閉まっている扉が1つでもある場合
}else{
// 部屋0から部屋Nに到達するまでの最初に閉まっている扉の位置
$first = $keys[0];
// 部屋Nから部屋0に到達するまでに最初に閉まっている扉の位置
$end = end($keys);
// 閉まっている扉の位置が同じ場合
if($first == $end){
// 2人で手分けすることで全ての部屋に到達できるため0を返す
echo 0;
// 同じではない場合
}else{
// それぞれの最初に閉まっている扉の位置の差を返す
echo $end - $first;
}
}
改善点
ネストが多くなってしまったので、今後は早期returnや条件分岐の整理を行い、もう少しネストを浅く書けるようにしたいと感じました。
まとめ
コンテスト終了後に他の参加者の結果を見てみると、A問題やB問題を数分で解いている人も多く、自分との実力差をかなり実感しました。コンテスト時間も本当にあっという間で「もう終わり？」という感覚でした。
また現時点では自分なりの「問題の解き進め方」がまだ固まっておらず、少しやりづらさも感じました。
どのように問題を読むか・どの順番で取り組むかなど、みなさんがどんな進め方をしているか教えてもらえると嬉しいです。
次回は、少なくともC問題までは解けるように、他の過去問を解きながら練習していこうと思います。