1.はじめに
はじめまして、raspberryです。一ヶ月ほど前に行われたARC171にて入緑することができたので、新年の目標に掲げていた通り記事を書きます。
2.自己紹介
数学が好きな一般的な普通の高校1年生です。
競プロを始めた理由は高校で情報Ⅰの授業があり、そこでpythonについて軽く触ったことで少し興味を持ったところでblueberryに誘われたからです。（名前の由来はblueberry系統でraspberryが残ってたから選びました）
使っている言語はPythonとC++で、最初は授業で触ったのもありPythonを使用していましたが、blueberryからC++の方が追々良いということを言われ最近はc++の方をメインで使ってます。
3.レート遷移
新年を挟んではいますが、入茶までの期間と入緑までの期間はそれぞれ1ヶ月半とほぼ同じです。ただ、周りを見てみると入緑するまでに3ヶ月というのはかなり早い方なので、この調子でどんどん進んでいきたいです。
4.緑色になるまでに何をしたか
4.1.そもそも茶色になるまで
基本的に情報の授業を真面目に受けていて基礎的な知識(for文やwhile文、四則演算、二分探索など)は学んでいたので、rated参加した最初のコンテストで3完をすることが出来ました。そこからblueberryに何をすればいいか、ということを聞きながらやってきました。
そこでA問題埋めを提案されたので暇なときに進め、一ヶ月ほどで終わらせました。A埋めをすることで文字列の扱い方であったりより短いコードで書くにはどのようにすれば良いか、といったりすることを学ぶことが出来たので個人的には効果があったと思います。（当時の一日ごとに解いていた問題数が下のグラフ）
4.2.入緑まで
茶色になるまでは割と時間かけた3完でもなんとかなりましたが、緑になるためには緑perf以上を取る必要があり、それには早解きの3完もしくは4完が必要になってくるのでその為に何をしたか書きます。
基本的にABCのA,B,Cの灰から茶diffを埋めて行く感じにやってきました。
また、blueberryが校内で行っているプログラミングの講座に参加し累積和やいもす法、dpなどを学び、精選 100 問にも取り組んでいて、大体50番目ほどまでやりました。
それでも自分は4完が安定しませんでした。ただ、自分はdiff700くらいまでの問題はコンテスト中に安定してACできていたので、コンテストで緑perfを取ることはできていました。
また、ARCには積極的に参加していました。実際、自分が入緑したのはARCで1完した回であり、1問解くだけで水perfを出すことができました。0完だとレートが大幅に失われるかもしれないという気持ちが自分を奮い立たせてくれるので、普段より良いパフォーマンスが出せます。
4.3.入緑に必要なこと
緑色になる為に必要だと思ったことは、問題を見た時に「この問題を解くために自分は何を求めたいのか」ということを言語化できるようにすること、いわゆる考察です。
もちろんその言語化できた内容を知っているアルゴリズムで対処できればそれは良いのですが、最悪問題を解くのに必要なアルゴリズムを知らなくても、方針を立てて調べてコンテスト中に通すことができる可能性はあるし、そうやって調べようとするのも大事な技能の1つだと思います。
あと、入緑までには必須ではないと思いますが、上達を早めるのに数学力はある程度必要だと考えていて、ABCのBやC問題で出てくるような難度の数学の問題は周りと差をつける良いチャンスです。
5.学んだアルゴリズム
- 全探索、順列全探索、bit全探索
- 二分探索
- 累積和
- BFS、DFS
- （初歩的な）DP
- ワーシャルフロイド法
6.マシュマロ返答
上記の精選100問をアルゴリズムを覚えるために参考にしています。書籍はblueberryに鉄則本を借りたことはありましたが、鉄則を読むよりも自分で調べて見つけた記事とかの方が個人的にですが分かりやすく早いことが多いので、あんまり書籍は使っていません。
好きなアルゴリズムですか...これと言ったのはないですが、個人的には累積和を好きにならないとやっていけない気がするので累積和ってことにします。
これと言って思いつくものがないのですが、EDPCや典型90問などの優しめの問題は解いておいた方がいいのかなと思います。
何すればいいのかが全くもって分からないのでヒューリスティックには参加するのを避けていたんですよね...でもAJL2024でヒューリスティック部門も開設されるらしいので少しは手を付けてみようかなと思いますね。
7.これからについて
水色がまず1つの目標になりますね。また、同学年の中で自分より上が3人もいるのでそこに追いつきたいです。後は来年度のAJLで学校のスコアにしっかりと寄与出来るようになりたいし、同学年の中で40位より上に入りたいです。
8.おわりに
ここまで読んでくださりありがとうございました。入水したらまた記事を書くと思うのでその時にまたお会いしましょう。