見出し画像

AtCoderにてRating4桁に突入しました（入千記事）

かみなり

これは何ですか

競技プログラミングサイトAtCoderにて、Ratingが1000を突破しましたので、その報告です。
本来Ratingが400の倍数を境にユーザーネームなどの文字色が変わり、その記念に色変記事を書くのが一般的ですが、書くタイミングを逃してしまったためにこのようなタイトルになりました。
ですので、変な記事名ですが、中身的には「入緑記事」とほとんど変わらないです。

自己紹介

  • AtCoder ユーザーネーム KA37RI

最近のコンテスト(ARC162)までのレート推移

  • 2023/6/23（記事投稿）時点 Rating: 1003 (ARC162にて1000突破)

  • 大学の化学系学科卒

  • Pythonを使っています

本編

やったこと・やりたいこと

AtCoder Problemsの実績一覧（2023/6/23時点）

AC数は多いとも少ないとも言えないのではないでしょうか。それでも私が特に力を入れたものがあります。

茶問題は全埋めです

茶問題(Diff400-800)は全て解いています。茶問題を制す者は茶レートを制すと信じ、解けるようにすべき難易度帯の問題を頭に叩き込みました。現在は茶問題を落とすことはかなり減っている（無いことはない）ため、効果はあると思います。（自身にとっての）中難易度帯を確実に取ることによるメリットは、大失敗する確率が減少し、レートやモチベの維持につながることだと思います。大成功したい方々へ、大成功は後からでもついてきます。まずは目の前の大失敗をなくしませんか？

習得したアルゴリズム・データ構造など

本番コンテストで学ぶタイプなので、事前に学習したのがコンテストに出たのは少ないです。また、アルゴリズムをいつ学習したか、なんて覚えてないです。のでいくつかピックアップします。

  • BFS・DFS
    とても良く使います。最初にアルゴリズムやるぞーといって学んだのはこれが初めてだと思います。
    BFSはキューをスタックに変えるだけでDFSになるのすごいなー…え？DFSは再起で書く？ハハッ何のことだか

  • トポロジカルソート
    グラフがサイクルをなしているかの確認に使用。ABC285-Dを解くためにコンテスト中にやり方を調べ、写経しただけなので習熟度は低いです。

  • bit全探索
    ABC-Cで頻出のやつです。 $${0}$$ から $${2^N}$$ までの整数と各bitを使う使わないの全組み合わせが対応しているのって綺麗ですよね。

  • エラトステネスの篩・素因数分解
    素数系の問題を解く上では必須なやつ。

  • 二分探索
    Pythonではbisectライブラリが使えますが、自分で実装する必要も多い。

  • BIT・セグメント木
    区間を対象にした取得や演算をするやつ。本番中に使ったことはないですが、非再帰セグ木をとても気に入っています。（参考にしたやつ）

Python特有の難所

  • 遅い
    Pythonは実行時間が遅いです。しんどいポイントではあるが、現状気になるほど（非本質な定数倍高速化をする羽目になるほど）ではないです。

  • ACLが使えない
    こっちのほうがきつい。ですが、Pythonにはbisect, itertools, collections, numpyなどに代表される便利ライブラリが多数用意されています！これを使わない手はない！
    そこにもないものも存在します。代表例はSortedSetと呼ばれるもの。しかしSortedSetはtatyamさんがPythonで実装したものがあります！（ $${O(\sqrt{N})}$$ だがAtCoderの制約においては十分早いらしい）tatyamさんに感謝…

蛇足

以下は思い出話やお気持ちなどが書かれています。最近(2022/10以降)のABC-A-E問題、ARC-A,B問題のネタバレをちょっと含みます。

灰時代（2022/10-2022/11）

競技プログラミングを始める前は、JavaやPythonを、趣味程度に触っていました（今も趣味の範囲ですが）。
JavaはMinectaftのソースコード読みやMod開発のため使っていましたが、コード作成の手軽さを理由にPythonに転向。
そんな中AtCoderに参加したのが2022年10月、初参加コンテストはABC273でした。
はじめのうちは3完を目標に、ABCのA問題やB問題で問われるプログラミングの基礎的な部分をしっかり落とさず取り、C問題で問われる主に計算量に関する工夫（setを使う、累積和で二重ループを解消、など）をクリアできるように、と頑張っていました。

茶時代（2022/11-2023/02）

初めての色変を済ませ、この頃になると3完が安定し、4完を取れるようにもなり、成長を実感しました。
ちなみに入茶したコンテストはABC279でした。D問題を、「二分探索？知るかーー！！」と言いながら数学（微分）をしてゴリ押しで通し、パフォーマンス929を獲得していました。
この期間中の印象的な問題は、ABC284-Dでした。2023年最初に行われたコンテストで、 $${2023=7 \times 17^2}$$ で表されることから生まれた問題ですが、受験数学でよくある西暦にまつわる問題（ $${3^{2023}}$$ は何桁か、など）に似たものを感じ、感動してしまいました。

VRC競プロ部との出会い（2023/02）

実は私、VRChatをしています（プロフィール）。
茶色も終盤、入緑が見えてきたというところでした。VRChat内で競技プログラミングについて語る会があると聞き、競プロerかつVRChatterである私は、ABC290の感想会に足を踏み入れたのでした...

ABC290の感想会の写真がこれしかなかった

めっちゃ上振れしていた（パフォーマンス1347、初の水パフォでした）のもあって、とっても楽しかった！！！
感想会では、ABCの各問題について、解説をしながら情報共有していきます。自身がACした問題でも、別解や、言語特有の豆知識や注意点が知れるので、A問題やB問題の解説からも学ぶところがあります。
（あと最近多いですが、「実装難なB問題」に対して文句を言い合う笑いの種にすることもあります）


緑（1回目）～茶落ち(2023/03)

ABC292にて、入緑しました！
ギリギリでしたが、Ratingが800に到達したので良しとします。
その後もう1度ABCを挟み、ARC158に挑んだところ、悲劇が起きました...
0完、パフォーマンス240、茶落ち！
ここからは、緑復帰に目標を設定し、なるべく落ち込まないようにしていました。元々Ratingはさほど気にしないようにしていましたが、茶落ちしたことは悔しく思っていました。
毎回のコンテストでは、4完は絶対取る、その上でコーディング速度にも気を配ることを目標にしていました。

緑復帰まで(2023/03-2023/04)

ここが現時点までの一番挫折したポイントかも知れません。
ABC295、ABC296では、D問題が緑問題であったこともありどちらも3完止まり。なかなかRatingを戻せずにいました。
この頃は、2022年11月から始めていた茶問題埋めが大詰めになり、灰～茶レベルの問題には凡そ自身がついてきたのですが、どうもコンテスト本番で成果が出ず、半グレ状態になったときもありました...
ABC297ではわずかにRatingを取り戻し、今度こそ、と意気込んだABC298ではさらなる悲劇が私に襲いかかります。
D問題を解き終わり、提出しようとしていた頃でした。AtCoderのサイトに繋がらない...終いにはサーバーが落ちてしまった...
そして、

悲しい

DDoS攻撃を受け、コンテストがUnratedになってしまいました。
緑復帰のチャンスを奪われ、更に意気消沈。ABC299もUnratedとなり、どうしたAtCoder。大昔はともかく、最近はUnratedになることなんてなかったのに、と愚痴を漏らしてしまいました。
そうこうしている内に、記念すべきABC300がやってまいりました。
実装難に苦しめられながら、D問題を見てみると、かなり見覚えのある形式で、解法はすぐに浮かびました。

＜問題概要＞
$${300 = 2^2 \times 3 \times 5^2}$$ のように $${X = a^2 \times b \times c^2}$$ （ただし $${a, b, c}$$ は素数で、 $${a < b < c}$$ ）となる $${X}$$ は、 $${N}$$ 以下にいくつあるか？

＜解答概要＞
$${a, b, c}$$ は高々 $${3 \times 10^5}$$ なので、エラトステネスの篩で素数を列挙。
$${a < b}$$ となるように $${a, b}$$ を全探索、 $${c^2}$$ は $${\lfloor \frac{N}{a^2 b} \rfloor}$$ 以下であるので、 $${f(\lfloor \frac{N}{a^2 b} \rfloor) - f(b)}$$ （ただし、 $${f(n)}$$ は $${n}$$ 以下の素数の個数）を答えに加算する。 $${f(n)}$$ は二分探索で求めるが、$${f(\sqrt{n})}$$ も求められるようにする。具体的には列挙した素数を２乗した配列を別に用意して二分探索をする。

結果、パフォーマンスは1046で、再入緑しました！ちゃんとRatedになってよかった！実は入緑記事は書く予定でしたが、先延ばしにしてここまで書かなかったという過去があります…

入千まで(2023/05-2023/06)

ここからは緑コーダーとしての戦いが始まります。各コンテストをダイジェストでお送りします。

  • ABC301: D問題まで早めに通しパフォーマンス1346！やった～～

  • ARC160: A問題は解けました（パフォーマンス1199）。解けた人数Bとほとんど変わらないのなんで

  • ABC302: Eが緑問題だったので5完でした（パフォーマンス1091）。上々！Find Snukeはかなりの実装難でVRC競プロ部でも散々言ってましたね。

  • （AGC062: レートが足りません。問題を見たのですが、実験すれば一発っぽい）

  • ABC303: パフォーマンス1038。E問題でAC×17, WA×4を出してからというもの、正解にはたどり着けませんでした。DFSの到達済み頂点の管理が間違っていたようでした。
    この問題のバグを発見していただいたVRC競プロ部のみなさん（特にあめんばーさん）、本当にありがとうございました！！！！

  • ARC161: 珍しく（？）前2問がARCの中では簡単なやつでした。C問題が解けず足早に撤退を決めたのだが、CとDで難易度が逆転しており、Dを頑張れば解けたのでは？という疑惑が生まれてしまった…パフォーマンスは1006とまずまずの結果。

  • ABC304: Unrated（悲しい）D問題は視点を変えるのが効きましたね。イチゴを主に見る発想をなんで思いついたのか実は分かっていない。

  • ABC305: E問題を10分くらい考えて「解けない！」と思ったのでF問題を見る。解けそうと思ったのでちょっと考えたところ、解けそうという思いが確信に変わりました。実装を気合で行いましたが、間に合わず…コンテスト終了後、サンプルの答えが合ったので提出してみたところ、ACしてしまいました。その時刻なんと22:42:29（コンテスト終了2分29秒後）！
    つまり、どこかで時間を3分ほど削れていれば、解けたということなんです。A, B問題の早解きやEからFに速く見切りをつけるなど、時間短縮できる場面が割とあっただけに、かなり悔しい結果となりました。パフォーマンスは1000を割り980でした。
    悔しい！もう一度言います。悔しい！！！！

  • ABC306: U n r a t e d （ 悲 し い ） （ 2 回 目 ） 度重なるUnratedによって、AtCoderも、コンテスト主催企業も、競プロerもみんなUnhappy…
    それでも原因究明及び解決に尽力し、コンテストを提供し続けているAtCoderさん、本当にありがとうございます！

  • ARC162: このコンテストで念願のレーティング1000を突破します！やった～

ということで2023/6/18、私KA37RIは、ARC162にてパフォーマンス1363（自己最高）を出してレーティングが1003となりました！Ratedで3桁順位を取ったのも自身初で、とても良い結果を最後に出して入千を決めることができました！
昨日のABCがUnratedに終わったため、不安の声があちこちから聞こえましたが[要出典]、Ratedになってよかった！（2回目）

VRC競プロ部に感謝！！！！

先程までも度々現れていたVRC競プロ部ですが、ここで改めてお礼を言わせていただきます。
ありがとう！！！！！！！！
身近に競プロをする人がいて、毎週コンテストについて語る時間があることは、自分にとって勉強になり、モチベーション上昇につながりました。競プロ以外の場面で謎解きワールドなどを一緒に遊ぶこともあり、今、私はとても楽しいです！！！！

脱出成功！

言語選択

唐突ですが、お気持ち表明のお時間です。
言語選択について私は「最初はPythonにしろ」と考えています。
理由：簡単だから
（初心者が０からコードを書くのは）C++なんかよりPythonのほうが簡単なのは異論はないかと思われます。取っ掛かりはPythonで始めてもらって最初に躓かないことが肝心かと思います。
遅いことに嫌気が差したらC++に乗り換えればいいし、Pythonで頂点を目指してもいいし、（そこそこ）早い、モダンな言語Rustを取り入れるのも良いと思います。
現状C++が最も競プロに向いていると言われているのは、ほとんどのトップ層が使っているという事実があるためでしょう。確かにC++でしか解けないような制約の厳しい問題もあるため、世界大会にでも出るようなトップ選手は「解き方は分かってて実装もしたのに、どうしてもTLEが出る！」なんてことはあってはならないでしょう。
しかし、AtCoderで水レートを出すくらいまではその心配は必要ないと思っています。緑以下の難易度の問題でそこまで制約の厳しい問題はまず出ません。（AtCoderが優しいというのはあります。問題を知らないのであまり詳しいことは知りませんがCodeForcesなどではC++じゃないと通らないような制約が出ることも多いらしいです。）
あと、少なくとも緑コーダーまでは実行時間より実装時間を短くしろとも考えています（自戒）。

最後に

書きたいこと（日記）が多すぎて長くなっちゃったよ～
ここまで読んでくださった方、存在するならば深くお礼申し上げます。


この記事が気に入ったらサポートをしてみませんか？