この記事は理情 Advent Calendar 2024 19日目の記事として書かれました。
自己紹介
Rho17といいます。AtCoderをやっていました。現在は不定期でコンテストに参加しており、レートは2039(黄色)です。実は最高で2200あったんですよ信じて
企画趣旨
「競プロ典型 90 問」とは理情（とパ研）の偉大な先輩E869120氏が2021年に発表したコンテンツで、初級者～中級者の考察・アルゴリズム両面を強化するための問題集です。
E869120氏本人の記事によれば、対象のレート層は200(灰色)~1999(青色)となっています。
では、黄色コーダーでも学びを得られるのか？ということで、2ヶ月かけて全問題を通すことにしました。
結果
提出と問題へのコメントはscrapboxにまとめました。
ここでは難易度ごとの感想と特に印象に残った問題をそれぞれ述べます。
★2～★4
考察は一瞬、実装もあまり苦労しませんでした。
★5
すぐ解けるものがほとんどでしたが、少し詰まった問題もありました。
068 - Paired Information（★5）
068 - Paired Information（★5） あまり言われてないけど難しくない？これ 想定解法がわからず非想定で殴りました（ユーザー解説の解法）
073 - We Need Both a and b（★5）
073 - We Need Both a and b（★5）
これは★5の中でも難しいと言われている 細かいところ詰めるのが大変
★6
知識単体な問題は考察・実装ともにすぐでしたが、そうでない考察寄りな問題でいくつか時間をかけたものもありました。
057 - Flip Flap（★6）
考察はすぐだったがこれを使う問題が青difに来るイメージがあまりない 毎回黄difに届いていそう
083 - Colorful Graph（★6）
ABCで類題を見たことあったので解けた ABC上の類題がdif2287なので...
049 - Flip Digits 2（★6）
ABCで類題を見たことあったので解けた ABC上の類題がdif2738なので...
そもそも典型のキーワードもざっくりしていて抽象的で、考察のステップ数も多くこれだけ★6の中で難易度跳びぬけていると思いました。★7中位と同等はあると思っています。
★7
思ったより難しく驚きました。アルゴリズムはほとんど知っているものでしたが、使いこなせないものも多く実力不足を痛感させられました。
005 - Restricted Digits（★7）
解説を開けた問題 その1
前から順に埋めるのがお勧めできない理由の1つ
059 - Many Graph Queries（★7）
解説を開けた問題 その2
こういうの苦手なの自分だけですか？
023 - Avoid War（★7）
実は最後の部分点の計算量削減はサボれる
053 - Discrete Dowsing（★7）
アルゴリズムがあまり知られていない、知っていても回数に余裕がないため正確に実装しきるのが難しい
090 - Tenkei90's Last Problem（★7）
090 - Tenkei90's Last Problem（★7）
1日がかりで解いた
小課題5までの数え上げは何とかなる範疇。本質は小課題6
感想
個人的な完走した感想：★6以下はほとんど既知の内容でした。黄色だったら★6と★7だけ埋めれば十分だと思います。
思ったよりデータ構造やアルゴリズムそのまま、という問題は少ないです。ほとんどの問題はその前に1ステップ必要でしたが、これが単なるアルゴリズムのVerifierになっていないという点でやりごたえがあり良い点だと思いました。
典型90でアルゴリズムを習得したいと考えている場合、★5まではアルゴリズムをそもそも知らない場合が多いので知らないと感じたら解説と実装を読んでアルゴリズムを適用できる状況を次々インプットしていくことを個人的にはお勧めします。
類題は結構難しいものも多く、無理に埋める必要はないかもしれません。現にAtCoderの橙dif以上相当の問題やJOIの難易度10以上の問題が入っているので、特に★6以上の類題は必須ではないと考えています。
おまけ
ところで、典型064の解説スライドをよく見てみると......
3つ目にyukicoder No.1209 「XOR Into You」という問題がありますね
開いてみると......
なんと、自作の問題が典型90問の類題として紹介されている ことがわかりました！
是非解いてください！
