競技プログラミングをやってみた。

タイトルにもある通り競技プログラミングをやってみました。

IT系の仕事をしてる人、競技プログラミングに少しでも興味ある人は是非最後まで見てください。
競技プログラミング経験者は温かい目で見守ってください。

競技プログラミングとは

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。

Wikipedia より引用

ウェブ上で定期的にコンテストが開催されており、コンテストの成果に応じてレートが変動します。
仕事で書くようなプログラムではなく、ゲーム感覚で楽しく書くプログラムだなと思いました。

どんなものかイメージがつき辛い方は、武器(プログラム)を作ってボス(課題)を倒す(解決する)ゲームだと思ってください。

始めようと思ったきっかけ

昔ゲームで知り合った方が競技プログラミング関係者だったのもあり、以前から競技プログラムの存在自体は知っていました。
ただ、当時は他人事というか、そんな世界もあるんだなーくらいにしか思っていませんでした。

そんな昔の出来事から月日は経ち、いつの間にか私もXX歳になっていました。
年とともに(何かしないまずいのでは…)と焦燥感に駆られるようにもなりました。
とりあえず何か始めようと思い、以下の理由から競技プログラミングを始めました。
・仕事であまりプログラムを書いていないので、プログラムを書く力を付けておきたい。
・転職時にもアピールできそう。
・レート機能があり楽しそう。

初コンテスト参加までにやったこと

競技プログラミングを知る

競技プログラミングという存在自体は知っていましたが、具体的にどういうものなのかは全然知りませんでした。
以下のサイトを見て競技プログラムとはどういうものなのかを調べました。
https://qiita.com/e869120/items/f1c6f98364d1443148b3

すごく分かりやすくまとめられており、読めば大体のことが分かりました。
どうやら競技プログラミングをやるにはC++がお勧めらしいです。

アカウント登録

以下のリンクから AtCoder の新規登録を行いました。
https://atcoder.jp/
私が登録したのは AtCoder だけです。

環境構築

C++で競技プログラミングをやりたかったので、Visual Studio 2022 をインストールしました。
最初はテキストエディタだけでやろうと思いましたが、無理でした。
ビルドできる環境は整えておいた方が良いです。(当たり前)

練習問題を解く

AtCoder のアカウント登録が完了すると、以下の練習問題を解くように言われます。
https://atcoder.jp/contests/abs

上のタブから問題を選び、実際に解いていきます。

まずは Welcome to AtCoder から…

問題は「整数 a,b,cと、文字列 s が与えられます。 a+b+c の計算結果と、文字列 s を並べて表示しなさい。」というもの。
標準入力や標準出力が分かればすぐに解けそうな問題ですが、C++はあまり経験が無くそれすら分からない状態です。

なんでC++を選んだの？って思われそうですが、実行速度が速くて競プロに有利という情報を見たら選ぶしかなかったです…。
// ゲームでもとりあえず強キャラを選ばないと気が済まないタイプです。

色々調べたり答えを見たりしながらなんとかクリア。
同じ要領で Shift only まで解きました。
なんとなくのイメージがつかめたので、後は実際にコンテストの問題を解いてみようと思い休憩。

ちなみにここの練習問題は以下のサイトで解説してくれています。
https://qiita.com/drken/items/fd4e5e3630d0f5859067

初コンテスト参加

6/16(日) 15:00 から、トヨタ自動車プログラミングコンテスト2024#6 が始まりました。
https://atcoder.jp/contests/ahc034/tasks/ahc034_a
私が初めて参加したコンテストです。

えっ…難しすぎ…？

なぜか問題は1つしかないし、その1つは今まで解いていた練習問題とは全然形式が違うし、はてながいっぱいです。

どうやら競技プログラミングのコンテストには種類があり、練習問題と今回のコンテストで形式が異なるようです。

アルゴリズム
・練習問題で解いたやつ。
・正解か不正解かを判定し、正解したプログラムを提出した早さを競う。

ヒューリスティック
・今回のコンテストで解いたやつ。
・スコアの計算方法が与えられ、スコアの高さを競う。

問題の概要
20×20 の計 400 マスがある。
各マスには高さがあり、-100 ～ 100 の高さが設定されている。
全てのマスの高さを合計すると 0 になる。

以下のルールに沿って、なるべくコストをかけず全てのマスの高さを 0 にしたい。
・マスの中をダンプカーで移動し、高さの整地を行う。
・ダンプカーに土砂を積むことでマスの高さは減り、ダンプカーに積んでいる土砂が増える。
・ダンプカーから土砂をおろすことでマスの高さが増え、ダンプカーに積んでいる土砂が減る。
　※ おろせる土砂は、ダンプカーに積んでいる土砂の量まで。
・ダンプカーを移動する場合は、ダンプカーに積んでいる土砂が多いほどコストがかかる。
・コストが少ないほどスコアが高くなる。

な、なるほど…。

超ざっくり問題をまとめるとこんな感じ。
・デコボコな地面があるよ～
・ダンプカーを使って土砂を積んだり下ろしたりして、地面を平らにするよ～
・ダンプカーにたくさん土砂を積んだ状態で移動するとコストがいっぱいかかるよ～
→ コストが高くならないようなルートを選択して地面を平らにしよう！

色々と試行錯誤しながら、最終的に私が解いた回答はこちら。
(この色々と試行錯誤の部分が大事で面白い気もしますが、うまく言語化できる気がしないので省略)

む、難しい…(2回目)
ちゃんとダンプカーが動くプログラムを書くまでに2時間以上かかり、この答えを出すのにさらに1時間くらいかかっています。
初めてダンプカーが動くプログラムをかけた時は感動モノでした。

感想

初めて競技プログラミングというものをやってみましたが、思ったよりも楽しかったです。
ほぼ4時間ぶっ続けでコンテストの問題と向き合っていました。

今回のコンテストを解いてみた感じ、コーディングの力よりもアルゴリズムを考える力が重要だなと思いました。
人が書いたコードも見れるので勉強になるな～と思いましたが、大体のコードは何書いているか分からないので勉強にならなかったです。

みんなにもこの面白さを伝えたいのですが、普段活字からかけ離れた生活をしているのでうまく伝えることができません。
本でも読もうかな。