はじめに
はじめまして、Rin_statisticsです。
先日開催されたキーエンスプログラミングコンテスト2024で入緑したので勉強法や体験談を綴っていこうと思います。
自己紹介
私立工業大学（電気系）中退の25歳
仕事は製造業の派遣で設備制御見習いをやっています。
いわゆる「ものづくりエンジニア」というやつです。
制御だからプログラマーやんと思われるかも知れせんが、設備制御はラダー言語など特殊な言語を扱っているので、世間一般のプログラミング言語は書けない人が多いです。
(というか私のいるグループではラダー書かないのでそもそも関係ないです...）
プログラミングを始めたのは大学中退が決まってから「何かしら武器はあった方がいいなー」と思い始めたのきっかけ
AtCoderは2021年12月に一度ABC参加したものの仕事の都合で離れる。
昨年の10月に転職して生活環境が整ったので同年12月にAtCoderを再開
入緑するまでの勉強法
主な勉強法は2つ
・PAST本の読破
・バチャコンを使った問題演習
PAST本
Pythonメインでコードを書くならばPAST本が結構おすすめです。
知識的な面に関しては本書の内容+UinonFindを覚えておけば十分戦えると思います。
最近、鉄則本を読み素晴らしい内容だと感銘を受けましたが
・前提として基本的なプログラムの書き方を知っていないといけない
・本のサンプルはC++で書かれている（GithubにPythonのサンプルがありますが）
・入緑には不要ところも多々あり、どう読み進めればいいか分かりにくい
以上の3点の理由で1冊でまとまりがよく読み進めやすいPAST本をおすすめします。
あまりPAST本で入緑したという事例を見たことがなかったのでPAST本でも入緑できるんだ程度に参考にしていただけると幸いです。
バチャコンを使った問題演習
問題演習はお馴染みAtCoder Problemsですね
私はA問題、B問題はほぼ埋めましたがD問題は演習量が少ないです。
だからと言ってD問題の演習をしなくていいかというと、絶対やった方がいいのでこれは反省です。
精選問題集みたいなものもありますが私は使わなかったです。
私はどの媒体の何をやるのかいちいち考えるのが面倒くさかったのでバチャコンの◯問題を埋める会を利用して全て解くようにしていました。
時間が許すなら全部やった方が確実ですしね。
他には仕事の昼休み中に10分のバチャコンを開催して解いていたりしました。
10分しかないので簡単な問題の早解きの力はかなりついたと思います。
色々と書きましたが結論としては、変にどの問題を解くかで悩むよりかはとにかく手を動かして量をこなすことが大事だと思います。
コンテストの際にやったこと
体調を整える
・飲酒状態、寝不足の状態ではRatedで参加しない。
・コンテスト1時間前にはシャワーを浴びて、10分瞑想する。
・コンテスト10分前に過去のA問題を2、3問解いて指を慣らしておく
以上のことをコンテスト前に実践していました。
体調によって考察の際の頭の働きが全く違うのでコンテスト前のルーティンは大事です。
正しく生成AIを活用する
当たり前ながら問題文を読み込ませるのはNGですが、書いたコードのチェックはOKなので使うことが多かったです。
コードを読ませておかしい処理がないか指摘してもらうこともありました。
実際ABC374 D問題は出力する答えの変数の更新が不適切でしたが、これを発見してもらい時間短縮できました。
正直、ここでハマってたら入緑できてなかったので感謝です。
あとはこんなデータ構造ない？と聞くこともありました。
ABC370 D問題は時間が足りず実装できなかったものの、Chat-GPTに聞いたデータ構造を使って方針までは正しく立てることができました。
使ったアルゴリズム
PAST掲載順+αで記載しています。
| アルゴリズム | 使用頻度 | コメント |
|---|---|---|
| 幅優先探索 | ◯ | C問題ですら使う機会があるので必須 |
| 深さ優先探索 | × | 使わなくても解ける問題が多い |
| 動的計画法 | ※ | 訳ありで使わなかった |
| bit全探索 | ◯ | C問題でよく見る |
| 累積和 | △ | Ratedで使う機会はあまりなかった |
| 貪欲法 | ◯ | 知らなくても解けるが方針を立てる際に |
| 二分探索 | ◯ | bisectが殆どだが1から実装することもあり |
| ダイクストラ法 | ◯ | 知らないと解けないタイプの問題なので必須 |
| ワーシャルフロイド法 | × | 未使用 |
| プリム法 | × | 未使用 |
| UnionFind | ◯ | 基本的な使い方ならよく出る印象 |
| メモ化再帰 | △ | 最近出ないね |
| 辞書型DPモドキ | △ | 後述しますが動的計画法はこっちで解いていました |
以上が主に使用したアルゴリズム、データ構造です。
まずは幅優先探索と二分探索を抑えた方がいいです。
これだけで対応できる問題が格段に増えます。
上記で×のものも全然使う可能性自体はあるので知っておいた方がいいでしょう。
他にこれあった方がええやろ！という意見があればコメントをいただけると勉強になります。
辞書型DPモドキに救われる
使用したアルゴリズムに「辞書型DPモドキ」という見慣れないものがありましたね。
これは私が勉強を進めていく中で
「DPが全然わからん！！！！！」
という壁にぶつかったので、自己流で辞書型のDPの解き方を編み出しました。
（もしこの解き方の記事があれば教えて欲しいです。私が探した限りでは見つからなかったです...）
これ自体は半年前くらいには編み出していたのですが
・D問題までだとDPが出る頻度がそこまで高くない
・出た回に限って私がポンコツを発揮する
以上、2点の理由からお披露目する機会がありませんでした。
ですが、ついにABC374 D問題でDPモドキ活用形が活躍し入緑の原動力になりました。
（嬉しい！）
実際にのコードの一部を載せますが、概要としては二次元配列のi-1のような一つ前を配列の情報を辞書のコピーで再現しています。
これは意外と書けることが多いので別で記事を書こうと思います。
D = defaultdict(lambda:INF)
D[(0, 0)] = 0
for a, b, c, d in pattern:
Dc = D.copy()
D = defaultdict(lambda:INF)
for key in Dc.keys():
x, y = key
move = math.sqrt(abs(c-a)**2+(d-b)**2)/T
score1 = math.sqrt(abs(x-a)**2+(y-b)**2)/S
score2 = math.sqrt(abs(x-c)**2+(y-d)**2)/S
D[(c, d)] = min(D[(c, d)], Dc[key]+score1+move)
D[(a, b)] = min(D[(a, b)], Dc[key]+score2+move)
おわりに
最後に競技プログラミングをやっていてよかったと思うことは、仕事で周りがプログラムを書けないからとても重宝されます。
（仕事が増えるよ！やったね！泣）
冗談は置いといて...
派遣という立場上できることに限りがあり意外と暇な時間というのもありますが、その時間で業務改善アプリの作成など色々仕事を振ってもらい評価していただけることが一番大きいと実感しています。
あと純粋に楽しいです、競技プログラミング。
今までは胸を張って趣味といてるものがなかったですが、熱中できるものが見つかって何だかんだ日々楽しいです。
とりえずで今後は知識、演習量が足りていないのでしばらくはUnratedで力を蓄える期間にしたいです。
また、Heuristicの方が私の性に合っているのでC++や最適化の勉強にも力を注いでいこうと思います。（実はHeuristicの方が先に入緑してたりします）
ここまでこんな駄文を読んでいただきありがとうございます。
記事は今後も出したいと思っているので、またどこかでお会いできたら幸いです。