2023/10/17のABC323にて入黄したので、いろいろ書きます。
自己紹介とこれまで
そういえばしっかりしてなかったので。
私は中学2年生です*1。私の学校は私しか競プロ勢がいないので、競プロ強豪校ではありません。筑駒でも開成でも灘でもないです。*2
数学が得意教科ではありますが、競プロ的な数学の知識は競プロを始めてから身に着けたので、普通の人という解釈でもほぼ問題ないかと思います。算数オリンピックのファイナル進出経験はあるので数学的な発想はほかの人より若干得意かと。
プログラミング言語の知識については、Scratchは結構長い間やってました*3。小5~6くらいかな?のころに少しPythonをやっていました。
競プロを始めたのは2022/7ころです。確かテレ東の動画を見て興味を持ったのがきっかけだったと思います。
このころはAPG4bでC++を学んでいたと思います。というのも、こいつsplit関数を知らなかったのでPythonで競プロをするのは不便というイメージがあったのです。
そして迎えた記念すべき最初のコンテストの結果は灰上位。このころから灰上位~茶色程度の実力はあったといってよいのではないでしょうか。
そして2022/8/27の回で異常な成功をおさめます。E問題が異常なほどすぐに解け、なんと当時の自分にとっては脅威の緑パフォ上位を叩き出してしまったのです。
しかしこのタイミングで夏休みが終わってしまい、これ以降触ることはほとんどありませんでした…
そう、2023/4まではね。
このころにAtCoderの存在を思い出し、ABC300からまたやってみました。ハマってしまいました。*4
そうしてAtCoderを半年ほど触り続けて今に至ります。AtCoder歴は実質半年といって差し支えないと思います。
写真集
▼レート変化とパフォーマンス
▼精進グラフ
▼優越感*5
▼Problems
▼Type Checker
教材について
ここまで行けたのは、9割質の高い教材のおかげだと考えています。
というわけで、個人の主観ですがおすすめできる教材をいろいろまとめておきます。
おすすめの星は黄色を目指す人へのものです。どの層にもおすすめできないものは書きません。*6
無料の教材
drken - Qiita
- おすすめ度 ★★★★★
- わかりやすさ ★★★★★
- 入黄への貢献度 ★★★
基礎を学ぶのに最も良い教材です。頻出のアルゴリズムを、考え方から書き方まで詳しくまとめられています。
ただし、「基礎を」学ぶのによい教材ですから、直接的に入黄に貢献してくれるかというと微妙なところです。
~水色までの貢献度は非常に高いはずです。人によっては青まで行けるかも。
e869120 - Qiita
- おすすめ度 ★★★★★
- わかりやすさ ★★★★
- 入黄への貢献度 ★★★★★
drkenさんのより競プロに特化した記事を投稿しています。
主にレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 #AtCoder - Qiitaのシリーズを熟読し、問題をすべて解くことを強くおすすめします。ABCのF問題まではこの教材の知識で対応できることがほとんどです。
【Python版】AtCoderのコンテスト中に「問題が解けない！」となった時に読む記事 #Python - Qiita
- おすすめ度 ★★★★
- わかりやすさ ★★★★★
- 入黄への貢献度 ★
教材とは違う気がしますが。
気持ちの問題です。この記事を横で開いておいてコンテストに参加した時の安心感はすごいです。
コンテスト中のパフォーマンスを上げることが可能ですが、直接実力UPにつながるかといえばそうではないと思います。
maspyのHP
- おすすめ度 ★★★★
- わかりやすさ ★★
- 入黄への貢献度 ★
初心者に読ませる教材ではありません。
特に高度な知識がまとめられていますが、前提知識が多すぎて難読です。
入黄への貢献度は皆無に等しいですが、レベルが高いためそれ以上に上達したい人、橙や赤を見据えている人には強くおすすめできると思います。
有料の教材
ちなみにAmazonリンクを貼ってありますが、このブログ経由で買っても私に収益の一部が入るみたいなことはありません。
アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門
- おすすめ度 ★★
- わかりやすさ ★★★★★
- 入黄への貢献度 ★
通称「鹿本」です。
初心者にはおすすめできます。~緑までの貢献度は非常に高いです。
しかし、内容が基礎的過ぎてそれ以上に行くとなると非常に心もとないです。もっと上を見据える人は後述の鉄則本か蟻本をおすすめします。
関係ないですが、累積和の考え方やC - GeT ACの解法を初めて知ったとき、本当に感動した記憶がありますね…
競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~
- おすすめ度 ★★★★
- わかりやすさ ★★★★★
- 入黄への貢献度 ★★
通称「鉄則本」です。
茶色~青におすすめできます。それ以上は心もとないかも。
図が非常に多く、とてもわかりやすいです。フローなどの比較的高度なものも理解しやすいかと思います。
あとヒューリスティックの項があるのも高評価です。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- おすすめ度 ★★★
- わかりやすさ ★★★★
- 入黄への貢献度 ★
通称「螺旋本」です。
競プロが得意な人にとって、前半には興味がないと思います。大事なのは後半の「プロコン必携ライブラリ」です。
特に、計算幾何学の項が非常に充実しています。これだけのために買う価値があると考えるかは人それぞれだと思いますが、私は買う価値はあると思います。
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
- おすすめ度 ★★★★★
- わかりやすさ ★
- 入黄への貢献度 ★★★★★
いわずと知れた「蟻本」です。
競プロ本の中で最もレベルが高いです。内容の密度がえぐい。
非常に高度な内容も取り扱っており、蟻本を読んでたから解けたみたいなことも少なくありません。
しかし、残念ながらわかりやすさは投げ捨てられています。相当の覚悟がある方は手に取りましょう。
Python関連
ほぼ以下の記事の二番煎じですが、私の考えも書いておきます。 maspypy.com
遅いのは事実
Pythonで適当に書いたら落ちたコードを、C++に移植するだけで普通に通ることがよくあるので悲しくなります。割と5回くらいは同じ経験をしています。
しかし、Pythonを使っていることを言い訳にできるかといえばそうでもないと思います。*7
例に挙げた提出はC++でもちょっときわどく、改善の余地は十分にあります。*8自分のアルゴリズムが悪いのを言語のせいにするのは非常にみっともないことだと思いませんか?*9
また、F - Vacation QueryやEx - Make Qだって、Pythonで通すのは難しいですが通している人は少なからず存在しています。*10
なんなら、数名の方が*11Pythonでほとんどの問題が通ることを証明しています。
結論として、「遅くはあるが言い訳できるほどではない」というところではないでしょうか。
Pythonの方が有用な場合も少なくない
Pythonが有用な場合として、以下の場合が挙げられます。*12
- 簡潔に書きたいとき(特に、FAを狙うとき)
- 多倍長整数を使いたいとき
前者は、例えばrin204さんやhiroyuk1さんなどがよくPythonで非常に簡潔なコードでFAをとっているのをよく見ます*13。前半の問題にほとんど時間をとられないのはうれしいです。
それ以前に、型指定とかめんどくさいものがないことが高評価です。コードを書く際に意識をとられすぎず、問題の考察も同時並行で進めやすいのがよいところです。
後者は、例えばB - Product of DivisorsやD - Match Matchingでうれしいのではないでしょうか。自前で実装する必要もなければ、性能も非常に良く、場合によってはこれだけのためにPythonを使う価値があるといえます。
Pythonだけしか使えないのは弱い
これが一番言いたいことです。
場合によって言語を使い分けられるのは非常に強いことです*14。Pythonは軽実装問題などを任せてC++は実装が重めのクエリ問題を任せるなど。
しかし、Pythonしか使えない人になると大きく伸び悩むと思います。考察の本質でないところで非常に時間をとられることになるので。
要するに、Pythonをメインで使う人もC++などの別の武器も身に着けましょうと、そういいたいのです。*15
好きな問題
順位形式です。
ネタバレに配慮して感想とかは折り畳みで置いておきます。
躊躇なく開いてもいいですし、挙げた問題を全部解くみたいなことしてもいいと思います。
5th
atcoder.jp
感想
灰色時代にこれ解けたのは偉くないです?
典型的な期待値DPですが、当時は動的計画法なんてものは知らなかったので、数学の問題として認識していた思い出があります。
別にこの問題が色変の決め手になったわけではありませんが、初めて解けた寒色問題ということで思い出補正は強いです。
今となってはもっと好きな問題が多いため、ここに落ち着きました。
4th
感想
これがフローで解けるのはアハ体験感がありますが、蟻本に似た問題があったおかげで即答できました。*16
すごく典型だと思ったのですが、意外と解けない人がいてびっくりしてました。
問題も面白かったですが、それ以上に蟻本のすごさを再認識するいい機会になりました。
3rd
感想
表記上、自力で解いたものの中では最高難易度の問題です。
この難易度の高さのわりに、必要な前提知識は水青程度のものでいいというのがすごいです。
当然Grundy数の知識は必要ですが、もはやそれ以外必要ないといっても過言でないかもしれません。*17
考えてて非常に楽しかったですし、解いて達成感もありましたが、どうしても上2つよりはその度合いが小さかったためここに落ち着きました。
2nd
感想
自力で解いたものの中では体感最高難易度です。
累積XORの知識は当然最低限必要ですが、それがわかっても考察を詰めるのが難しい。
そして考察を詰め切っても桁DPの実装は非常に手ごわかったです。*18
難易度と達成感は1位なんですが、1位の思い出補正が強すぎたため2位に落ちました。
1st
感想
本番で解けた最高diffです。
単純な問題設定のわりに複雑な考察になりますし、その結果得られた結果は非常に単純という、ほんとうに考えてて楽しかった問題でした。
実装もそこまで重くなくて好印象です。*19
入青の決定的な決め手になった問題なので、思い出補正が強すぎてさすがに1位以外ありえません。
質問返し
本記事のメインです。
ことの発端はここです。
(入黄記事のネタが欲しいので)質問募集します！
— はるく@競プロ (@halc_kyopro) 2023年10月7日
質問は1人3つまで、リプしてください
被ってるものや答えなくないものはそっと無視しますが大体答えます
結構来てくれたので返します。
レートは上がってる、でも実力だけで考えた時成長してないと感じることはありませんでしたか？その時、どのようにモチベをキープしていますか？
まぐれで難問正解してレート爆上げした回はだいたいそうなってる気がします。
が、そういう回は大抵気持ちいいのでモチベ管理には困りません()
そういう回たち
(「当時の自分にとっての」難問たちです)
ちなみに逆の「実力は成長してると思うけどレートは上がらない」ことはあります。
これのモチベ管理は大変ですが、「問題との相性が悪かった」と割り切ってゆっくり復習するようにしてます。
重実装は得意ですか？
まじめな話、この解説のおかげでグリッドの重実装だけ異常に慣れてます。(得意ではありませんが…)
こういう系でそのまま扱って苦戦してる人は一度読んてみることをおすすめします。
無限場合分けとJOI(C++)は得意になれる気がしません…
過去問を解く時、難易度はどのくらいを目安に設定していますか？ また、考察は感覚どのくらいまで粘りますか？
黄~橙前半を意識して埋めてます。このブログでほぼ毎日投稿してるように、少なくとも格上を倒すようにしてます。
考察はたぶん2~3時間は粘ります(もちろん遊んだりしながらですが)
好きなアルゴリズム/データ構造はなんですか？
自作セグ木(遅延含む)が使いやすくてすごく愛着があるので、データ構造はセグ木としておきます。
アルゴリズムはMoですかね～(これも早いライブラリができたから)
どっちも窃盗OKのつもりです。需要はなさそうですが。
セグ木たち
Mo
得意なアルゴリズムは何ですか？
得意なのは圧倒的フロー(使う側)です。
いや、もう普段のブログの内容から明白なんですが。
【今日の精進】ARC085E - MUL - halcの競プロ精進ブログ
【今日の精進】ABC225G - X - halcの競プロ精進ブログ
【今日の精進】ABC241G - Round Robin - halcの競プロ精進ブログ
フロー(作る側)ですかね…
何回か作ろうとしましたが 回挫折しました。
あきらめてACL使ってますが不便なことは何もないので改めて実装しようとも思わない負のスパイラル…
たぶん聞きたいのはこういうことではないと思うので真面目に答えると尺取り法です。
最近dequeで実装する方法を見たので、試してみようかと思っています。
ABCがUnratedになって悲しいですか？
レートを一切気にせず遊べそうなのでむしろうれしいまであるかもしれません。
思う存分変なところのFA狙ったり変な解き方できそうだな～、と思ってます。
いやまぁ、レートはクッソ上がりにくくなりそうだけど
普段の学校生活は崩壊していませんか？(競プロで)
し て ま す
考察してて授業が耳に入らないこともしばしばですね…
良い子のみんなは節度を持ってやろう！
毎日何時間くらい精進に使っていますか？
いうて1~2時間くらいかもしれない
ほとんど難問1問だけ解いて終わりだし
どんな精進をしましたか？
常に意識しているのは「格上を倒す」ことです。セルフ精進鯖です。
たまに蟻本の内容を読み込んだりしています。
ARCはRatedで出たのか、出たならどれくらいの割合で出ているのか を聞きたいです
100%Ratedです。
一番勝てないのがARCなのですが、それでも緊張感をもってやりたいので。
自分は認知されていますか
日本橋ハーフマラソンの懇親会にいた人はほぼ全員認知してます！！！
というか忘れるわけがありません()
今後の目標はなんですか？
橙になってなんか問題を作ることです。いつかA(B/R)C開きたいな～、と。
何年かかるんでしょうねほんとに。
今後の目標は何ですか？そのためにやろうと思っていることはありますか？
目標は上で述べたので。
やろうと思っていることといえば、しいて言えば毎日解く格上のレベルをあげることでしょうかね…
いずれ橙後半くらいを安定して解きたい…
あとはCFのDiv1のバチャに積極的に参加しようと思ってます。nok0さん曰く、ARC以上の難易度らしいのでARCが安定するかなと。
あとゆきこでコンテスト開きたい(アルゴの方)
目標にしている競プロerはいますか？
特に意識しているのはkeisukeさん、shiomusubiさん、PCTさん(レート順)
特にshiomusubiさんはもうなんかいろいろとすごい(語彙力…)
毎年このくらいの時期の中2が最初に入黄してるイメージあるな、と思っていたら今年と去年だけでおととしはしおむすび様が中1で普通に入黄していてびっくり
— ふぁくと (@fact493) 2023年10月7日
挙げた人は中高生の暖色erが多いですが、それより年が上な人は目標というか尊敬という感じですね
終わりに
なんか青に落ちそうで怖いですが終わります。
*1:ちなみに我ながら疑われそうですがガチです
*2:いつかバレそうだけどまだ隠す
*3:ちなみにアカウントは消しました。何人かは私のアカウントだったものを知っていると思います
*4:今までで最大のやらかし
*5:日本の中学生ランキング
*6:私が読んでないものも書いてません
*7:いや、あなためっちゃ言い訳してるじゃないですか
*9:ぶーめらん
*10:私は通してませんよ?
*11:maspyさん・rin204さん・Kiri8128さんなど
*12:numpy?知らない子ですね
*13:私もFA間近までは行ってるもん
*16:でもあなた4ペナしてますよね?
*17:二分探索は?
*19:でもあなた9ペナ叩き出してませんでした?
