今回、ABC452をもって、入水を達成したので報告します。
緑色の期間はたった3か月でした。
[自己紹介]
膳所高校の3年生♂。ADHDです。JMO予選突破を2回したり、mensa会員だったり、駿台全国模試数学全国5位だったり...
ゆーてるのX垢
[何をしたか]
この期間でまた、いくつかの新しいアルゴリズムを習得しました
数強コーダーが年内に入緑しました。
ここで紹介されているアルゴリズムに加えて、次のアルゴリズムを学びました。
○再帰全探索
○耳DP
○Union-Find(今更!?)
・最小全域木
・マンハッタン距離の45度回転
・セグメント木を用いたDP高速化
○木の直径
・全方位木DP
・商列挙
・原始根
・ワーシャルフロイド法
・拡張ダイクストラ法
・メビウス関数、メビウスの反転公式
・Zoblist Hash
・オイラーツアーセグ木
○転倒数(BITを使うのがおすすめ)
・Mo's Algolism
・偏角ソート
・ナップザック問題の特殊な場合
○をつけたものは重要です。高度なアルゴリズムばかりなので、今の時代では入水に必ずしも必要でないアルゴリズムの方が多いと思います。
[やった勉強]
まず、前提として入緑までに鉄則本を勉強しました。入緑ー入水 間でやった勉強の殆どは、最近(ABC319~)のABCの過去問です。多くの寒色がEDPCや典型90を推奨していますが、実は私は殆どやっていません。
しかし、ごく当たり前のことですが、緑色以下は(現時点では)ABCのみでレートが変動するので、その傾向を最も掴んでいるABCの過去問を最も重点的にするべきです。Novistepの解法別で過去問を演習したり、バチャコンを回す人もいますが、私はdiff基準で過去問をガリガリやっていました。多分これが最もオーソドックスです。
私が最も重視するdiffは、青diffです。緑色のみなさん、青diffを解きましょう。
[緑diff演習]
最近の緑diffのD問題が安定していなかったので、緑diffを対策するために、ウルズニャーさんや、直近で解けなった問題などを1日にまとめて演習しました。結果、予め用意した12問全てを解くことができ、2/3以上は30分以内で解けることが分かりました。
それ以降、緑diff以下は精進していませんが、最近になって再びC,D問題が安定しなくなってきているので再び雑魚狩り演習をする必要があります。ABC過去問は面倒なので、代わりに典型90の星が少ないやつを埋める予定です。
ちなみに、最近のE問題で緑色の問題を対策したい場合。これは色がバグ(界隈の異常な成長速度に起因するもの)なので過去問の水色前半のEを演習するべきです。
[水diff演習]
最も多くの問題を精進した色です。基本的に入水を目指すならこれになります。はじめの方は自分が解けそうなものからひたすら解いて、次第に難しい問題も、アルゴリズムを自力錬成するなどして攻略できました。
にゃんぱすさんと銅diff界隈の繋がりで仲良くなったので、入水のために青diffを演習することを推奨すると、ウルズニャーさんに、「そういう事言う人には知識問題の水を投げつけますよ？！」と言われ、水diff3題投げられました。知らないアルゴリズムの問題だったので、アルゴリズムを自力錬成して解いたら、彼はすごく驚いていました。同時に、自分が青色以上のポテンシャルを持つことを確信しました。
しかし、見ての通り苦手な水diffは解くのに時間がかかるので、もっと水diff演習しないといけないと思いました。
[青diff演習]
これが最も効果がありました。私にとっては、青diffは解けるか解けないかの境界辺りの問題で、手強い問題が多く、解くことに快感を感じました。やり方は単純です。解けそうな問題を選り好んで1問1時間を目安に解く。それだけ。これによって、得意を伸ばすことができます。解ける問題を見極める能力、すなわち目利きも手に入れられました。青diff演習のおかげでコンテスト中に青diffを2回ACしただけでなく、青diffで苦しむことによって、水diff以下が容易な問題だと感じられるようになりました。
青diff演習をして強くなれる緑コーダーはぜひ青diffを演習するべきです。しかし、多くの緑コーダーは青diffの適性がないと思います。
だからこそ、青diff適性があるか一度確認してほしいんですよね。効果ある青diff演習の方法についての記事も今後作成する予定です。
[赤diff以上演習]
完全ネタなので読み飛ばしてOKです。たうさんが赤diffを解いたことに影響されて赤diffを5時間かけてACしたのが全ての始まりでした。その後にゃんぱすさんがその界隈に加わり、3人で仲良く銅diff,銀difffを解いていました。めっちゃ楽しかったです。
ちなみに、初期のatcoderの赤diff銅diffは現在の青diff黄diffくらいなので、緑コーダーでもいける人はいます。ウルズニャーさんは緑コーダーが赤diffを1問自力で解いて自信をつけることを推奨しています。
[入水するために重要なこと]
①難しい問題を解くことをモチベーションにしろ！
モチベーション維持のために、見栄を張るためにAC数を増やすことを過剰に意識する人がいいます。はっきり言います。AC数は努力量を大雑把にしか表しません。灰色500ACと、青色100ACを比較すると後者の方が努力しています。だから、目標は「500AC」「1000AC」ではなく、「水色100AC」「青色30AC」などにするべきです。ちなみに私は難易度の高い問題でACを増やすために、あえて少ないACでレートを上げることを意識していました。
streekを繋ぐために灰色「虚無埋め」をする人もいますが、正直緑色が灰色を解いても学びはほとんど得られないので、streekを過剰に意識しすぎるのはよくないと思います。「1週間のうち5日以上、水色以上を解く」などを意識するのがいいと思います。HeatmapのMax Difficultyを意識するのがおすすめで、あなたの目標の色に染め上げましょう。ちなみに私は意図的にカラフルな色合いにするのを意識していたそうです。
難しい問題が分からないことばかりで、何も進まず3時間が経過するとか、よくあると思いますが、めげずに頑張って下さい！
②解説ACを極力するな！
多くの記事が解説ACの重要性を説いていますが、私はあえて逆のことを主張します。分からなかったらすぐに解説を見たい衝動に駆られるかもしれません。緑diff以下ならそれでOKです。水diff以上の場合、その衝動をグッとこらえましょう。水diffでは1時間かけて解くのが目安ですね。1時間かけても分からなかった、その場合、解説を見てはいけません。
atcoderは少しずつ強くなればいいので、別に1問解くのに1か月以上かかってもいいんです。1週間後、1か月後、忘れた頃にもう一度考えてみると新しい発想が降ってくるかもしれません。もしくは、インターネット検索で抵抗しましょう。その問題に似た問題を解くことで、目標の問題の「誘導」が得られることがよくあります。もしくは、ChatGPTにヒントを出してもらいましょう。AIにヒントを出してもらうのはおすすめです。
解いた問題数だけ考えるのは甘い。1問1問にちゃんと熱意を込めることで、似た問題が出題されたときに解けない、を防げるんです。なお、問題を解いた後、公式解説の解法と大きく異なる場合、その解法で解説ACするのはOKです。
理想は、学んだアルゴリズム数≧自力ACできなかった問題の解説AC数 です。解説ACを減らすことで、コンテストで既存のアルゴリズムを「知らなかった」と言い訳にすることが減ると思います。
③SNSで先輩、仲間を作れ！
ほとんどの競プロerって、生活の身近に水色以上がいないんですよね。だから、仲間をsnsで作る必要があります。やることは簡単です。毎週コンテストに参加して、コンテスト結果をXに投稿する。できれば今後の目標に関するポスト、今している精進のポストもすると良いです。もしくは、競技プログラミングのdiscordサーバーにも参加しましょう。
自分の分からない部分を質問できる環境、アドバイスを貰える環境って、大きなアドバンテージです。独学だけでは気付くことのできない、自力の弱点を克服するのに大きく役立ちます。
[私の先輩、仲間の紹介]
希望がある人はここに掲載しますよ...!
・ウルズニャー
私の大先輩です。Novistepsの運営をしたり、キーボードを自作したり、TUNAcampの運営をしたり、すごい人。自分の苦手分野の問題をウルズニャーさんに出してもらったり、いろいろアドバイスをくれたり、私が入水するのに一番お世話になった人だと思います。今までご指導ありがとうございます。これからは...ARC対戦するで！
・りうる
とんでもない量の精進をし、discordサーバーを運営をする、すごい女子高生。りうるさんが精進頑張っていることが、自分も負けてらんねぇと精進するモチベーションになりました。
・岩井星人
2,3か月で入水する人も多い中、2年半以上緑色で生活しているにも関わらずめげずに精進し続ける、熱意に関してはすごい人。以前は岩井星人より先に入水してやる！をモチベーションにしていました。今は純粋に岩井星人を応援しています。
・ありんP
私に競技プログラミングのきっかけを与えてくれた人です。彼がいなければ私はJOI2次突破もしてないし、入水もしてません。とても感謝しています。
・かみゅー
ADOFAIが共通趣味の人です。It Goをクリアしているので上級者。競プロアキネーターで仲良くなりました。
・たう(tau0529)
水色の皮を被った悪魔。ばけもん。彼がきっかけで私は銅diffにハマりました。
・rhyska
元々CTFで繋がりがあった人。今は競技プログラミングで繋がってます。たまにdiscordで話したりします。
・hiro1729
ペンシルパズルが好きな人。JOI春に行ったことのあるすごい人。
[入水ダイジェスト]
※おまけ要素です
①ABC452(入水回)
結論から言うと、決して満足できる回ではありませんでした。
1:30 A問題AC
3:31 B問題AC
25:37 2回REした後に、C問題をAC
読解力が必要な問題でした。このような問題をもっと速く解けるように訓練する必要があります。REの原因は、Ai,BiがNより大きい可能があることをソースコードに反映できていなくて、配列外アクセスしたことです。
この時点でかなりグダグダですが、問題なのはD問題
まず、TにSが含まれるようなSの部分列だと勘違いしてました。ソースコードを書いてサンプル通そうとしたときに気づいたのこの時点で結構萎えていました。それを踏まえた上で再び考察するのですが...分かりませんでした。Sの連続部分列ですから、いつもの耳DPが適用できなかったんです。
20分くらい後、Dに見切りをつけることを決断します。
E問題はすぐに解法が思いつかなかったので、飛ばしてFに行きます。元々、E,Fの選択を間違えないために、Fを最低3分考察することを予め決めていました。3分くらい考察した後、尺取りBITだと分かったので実装します。当然、F問題なので実装事故をします。転倒数がKであるものの個数を求めるには、(K以下であるものの個数)-(K-1以下であるものの個数)と計算するのが理想です。ちょうどK個であるものを尺取り法で数えようとすると、次のテストケースがコーナーケースになりえますね。
N=8
K=1
A=[1,2,3,5,4,6,7,8]
対策するには、「ここの部分の増加部分列の長さ」を別の配列で数えておく必要があります。
こんないざこざがあって、
92:19 F問題をAC
あと8分で、問題がシンプルなEを解きに行きます。
終了1分前にEの解法が天から降ってきました。もう手遅れです。
理想はCとFをもっと速く解き、Eを間に合わせることでしたが、後日Eを実装してみたら、実装事故したので、E,F両方を通すのは難しかったと思います。つまり、Dを落としたのが致命的でした。もっと基礎力と実装力を上げなければ...
結果、1956位。レートが1180→1200でギリギリ入水し、次の日のARCの出場権をもぎ取りました。
②ABC448(爆勝ち回)
パフォーマンス1992、レート+158という、緑コーダーとしてはありえない勝利をした回。先輩のたちに勝利し、これによって岩井星人のレートを追い抜くことに成功しました。
1:17 A問題AC
4:43 B問題AC
13:43 C問題AC
28:59 D問題AC
setを用いるDFSの問題でした。面白かったです。
50:15 E問題AC
数学が得意な人にとってはすごく簡単な問題。レピュニットのダブリングが公式解答でしたが、これ見た時に「は？こんなことしなくいいやろ」と思いました。
今までで最も速く5完できました。この時点でレートが大きく上がることは既に確定していますが、さらなる奇跡が起こりました。
85:18 1WA後にF問題AC
これ、Mo's algorithmと言うらしいです。鳩ノ巣原理のグリッド分割みたいな問題なぁと思ってアルゴリズム錬成しました。200~250個の長方形に分割して解くのですが、私は200個に分割しました。200という値は、手動(紙の上の)2分探索で見つけたものです。ちなみに、WAは、通る頂点を1からスタートさせなければならないという条件を見落としていたことに起因します。
まさか私が6完できると思ってなかったので、FのACを見て絶叫しました。レート大爆発が確定！
結果、293位。レートは990→1148という快挙です。