カメヲラボ

主にプログラミングとお勉強全般について書いてます

競プロ日記000: ABCはじめました

ABC(AtCoder Beginner Contest)に初参加しました

以前から気になっていたもののスケージュールの都合とか体調の問題で参加を見送っていましたが,重い腰をついに上げユニークビジョンプログラミングコンテスト2022 夏(ABC268)に参加しました.理由は2つあって,1つは単純に「参加している人たちが楽しそう」ということ,もう1つは「ヒューリスティックコンテストの実力を強化したい」ということです.

概要

私はABC初参加とはいえヒューリスティック系のコンテストにはそこそこ参加していて,今年(2022年)の春ごろからATopCoder MM(Marathon Match)やAHC(AtCoder Heuristic Contest)のようなヒューリスティック系のコンテストには好んで参加しています.AtCoderでのヒューリスティックレーティングは現状こんな感じ(1337の水色)です.

AHCのレーティング2022年9月14日現在

MMのコンテスト期間は基本的に1週間で,AHCの場合は1~2週間の場合と4時間だけの場合があります.特に4時間制限のコンテストでは今までまともな成績で終われた経験がなく,短期間で解答を完成させることがなかなかできませんでした.そこで「瞬発力を上げよう!」という考えに至ったわけです.つまり本稿はヒューリスティックでもっと強くなりたいオッサン瞬発力を上げるトレーニンとして短期コンテストに参加するという日記であります.最初は問題の具体的な解法とかコードを中心に書いていこうかと思ったんですが,今は公式な解説があるのと,非公式で多くの方が有用な記事をたくさん書いてらっしゃるので,この辺りはあまり書かないつもりです(余程解説と異なる場合等は書くかも).

はじめて参加した感想

これから競プロを始める人や将来の自分に向けて,気付いたこと等をまとめておきたいと思います.

解答順序

問題のレベル感が全くわからないので,素直にA,B,C,…の順番に解きました.基本的には全部で8問みたいなので,5~6問くらい解けるレベルになってくると取り掛かる問題の順序は考えなければならないかもしれません.当面はAから順に解く方針でいくのが無難かと思いました.

言語の選択

AとBはPython3で解いて,CでTLE(時間制限)に引っかかる問題が出てきたので念のためC++に変えました.おそらく想定解のアルゴリズムではPythonでも十分なのだろうと思うので全部Pythonでも良いかなーと思いつつ,無理やりC++でチューニングしたコードで上手くいく可能性があるかもしれないので,ちょっとよくわかりません.これは何回か参加しながら自分にとって最適な選択を見つけるのが良さそうです.

ローカルテスト

AtCoderではヒューリスティックしか参加したことが無かったので,不正解のコードを提出するとペナルティがあるのをすっかり忘れていました.C問題では愚直にやればO(N2)くらいかー,TLEになりそうだなー,とりあえず提出→TLE→やっぱり😅→ペナルティ→えぇ😱

今回は大きなテストケースを自分で作って確認してから再提出したのですが,おそらくこれは(競プロ的には)良くない方法で,入力の範囲から計算量をできるだけ正確に見積もって,どれくらいのオーダーで解けば良いかを掴めるようになっていなければならないのではと思います.

ソースコードやテストケースの生成

問題が複数あるので,新しく問題を解く際に新規のソースコードとかテストケースのファイルを用意しなければなりません.今回はこの辺をあまり考えてなかったので,問題Aを解くときにAというディレクトリを作って,問題Bを解くときはAを複製してリネームみたいな感じでやっていました.こうすると,CとかDあたりで焦りが出てきたときにかなりワタワタしてしまって,編集ミスとか提出ミスをしやすそうです.しっかり手順を決めておくとか,ある程度自動的に処理できるようにスクリプトを事前に用意するとかしておくと良さそうです.

結果

初参加の結果は,ABCの3問が通って,Dのコードを実装中に時間切れになりました.Dは完成させてから提出すると通ったので,もう少しスピードアップすれば大丈夫そうかなといったところです.

AHCのレーティング2022年9月14日現在

というわけで初参加の結果,レーティングが55になりました.レーティングに関しては何もわかってないですが,

とのことで,最初の数回は少々ひどい結果でも参加さえしていればいくらかは上がっていきそうです.

次回に向けて

過去問とかやれば良いだろうなーとは思いますが,まずABCに参加する時間を捻出すること自体が大変なのと,前述の通り何回も参加してレーティングを上げていく必要があるみたいなので,当面は特に準備せず参加をしていきたいと思います.10回くらい参加したところで現時点での自分の実力が大体わかりそうなので,その頃に次の対策を考えるのが良さそうですね.

競プロ本の新刊!!

この日記をダラダラを書いている最中に,1冊の本が届きました.

競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ)

マイナビ様本当にありがとうございます.もうちょっと頑張って仕事します😅

パラパラと中を見た結果明らかに素晴らしいものだと思ったので,近いうちに紹介の記事を書かせていただきます.

次回に向けて(修正)

基本的には前述のとおりですが,良い本を頂戴しましたので競技プログラミングの鉄則』を読んで勉強しつつ進めることにします.