AtCoderで青コーダーに...なれた...

regiです。まずTwitterでは迷惑になるのでここで叫ばせてください。

ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああやったーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーうわうわうわうわうわうわうわうわうわうわうわうわうわほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほほ

失礼しました。この記事では色変記事で必要不可欠そうなもの(解いた問題数や学んだアルゴリズム・データ構造等)を書き、その後で水コーダーから青コーダーになるまでのおおまかな軌跡(大体ふざけてるので注意してください)や、これからのこと(真面目)を書きました。精進法などは前回の色変記事にまとめたので、それを見たい方はこちらをクリック。

regichan.hatenablog.com

 水コーダーの頃に解いた問題数

まずは水コーダーなりたての頃と青コーダーなりたての頃とでのAtCoderのAC数を比較してみましょう。

水コーダーなりたての頃　↓

青コーダーなりたての頃　↓

こう見てみるといっぱいやりましたね。(otherはJOI埋めをやってたら増えました)

水コーダーの頃に学んだアルゴリズムとデータ構造

 水コーダーの頃は以下のようなものを学びました。ここでは、学んだ=仕組みを理解して自分でライブラリを作ったと定義しています。(そうしないとACLの扱いに困るため)

• 2^61を用いたローリングハッシュ
• 複素数を用いたFFT
• NTTを用いたFFT
• modint
• エラトステネスの篩(は？)
• LCS
• 遅延評価セグメント木
• 拡張ユークリッドの互除法
• 原始根を求めるアルゴリズム
• BIT(フェニック木)
• 重心分解

 ちょっと一つだけ「え、この時期に...？」というものが混じっていますがあまりお気になさらずに。

これはあまり関係ない事ですが、ちゃんとしたライブラリを書くため、また、強い人のコードを理解するために独習を買いました。気合い入ってる、偉い。

あと、独習買ったら今後役立つことあるかなあ、なんちゃってとも思った。(ただ、ACLでしばしば用いられる高速化はこの本ではあまり載っていなかったので泣いています。ACLのコードむずすぎ案件)

水コーダーから青コーダーになるまで

ここからは昔話のお時間です。私は水コーダーになった後も精進をし続けました。青コーダーになるために。そのためには、私はどうしてもボトルネックになっているなあ...と感じていた早解きを習得する必要がありました。これは水コーダーになる前からもやっていたことですが、今まで解いた中で橙diffや赤diff、金diffでない問題はほぼ全て、問題を見てからACするまでの時間を測って解いたと思います。Twitterにも解いた問題を貼るときは決まってその時間も添えていました。以下のように。

 見栄っ張りなのでかなりうまくいったものも貼る！！！

提出 #16562667 - AtCoder Regular Contest 050 https://t.co/NokQqClSYF
(diff 2328) 17分
解法の正当性を完全に示してから一発でバグがないコード書いて一発でAC、気持ちいい

— regi (@Re_code_A) 2020年9月7日

 また、この問題かなり面白かったのでおすすめです。少し脱線しましたが、このような精進を重ねたことで、着々と早解きできるようになりました。(最終的に、ABC178でお気に入り内の青コーダーの方の誰よりも早くA～Eを通せるようにまでなったので結構嬉しかったです←)

ただ、青コーダーの神様はそう簡単に私を青コーダーにはしてくれなかったんです...。

災難１. 些細なうろ覚えでM-SOLUTIONSプロコンオープン2020にて入青を逃す

このコンテストでの私の提出一覧です。

コンテスト前のレーティングが1549だったため、もしFがコンテスト中に通っていれば黄パフォが出て入青でしたが、WAが出て敗北。(MLEってそんな出ないけど、いざ出たら笑っちゃうのありがち)　それからメモリをやりくりしてもサンプルと出力が合わず、椅子を温めるtouristとなっていたわけです。このサンプルと出力が合わなかったわけ、今でも笑ってしまいます。私はstd::setのイテレータ操作をうろ覚えのままにしたために、そのイテレータ操作がうまくできなかっただけでした。問題のコードがこちら。(これだとイテレータ操作できません)

この後ちゃんと前置に直したらAC出ました、競プロは面白いですね。C++言語ちゃんをもっと戯れてあげるべきだったと思っています...。

災難２. 寸　　止　　め　　笑

文字通りです。以下の画像がそれ。

コンテスト終了10分前、AtCoder垢10,000個くらい作って全垢でABC参加したら相対的にパフォ上がるかなあと思いましたが、良い子なのでそんなことしませんでした。

災難３. やはりAGCは苦手だ

レーティング1597になってからの次のコンテスト、それはAGCでした。私はAGCかなり苦手で、そんな状況をどうにかしようと思い、AGCまでの1週間とてつもなく頑張ったわけです。毎日黄diffや橙diff、赤diffに立ち向かって考察し抜く力をその1週間で付けようとしました。PCの前に座っているときはもちろん、食事をしているときも風呂に入っているときも照明を消して布団に入った後も、しつこく考えていました。ねちねちねちねちと。その結果、暖色diffの自力ACは結構増え、考察力はかなり付いたと実感していました。しかし、AGCはそこまで甘くなかったわけで...実際に出た問題はロリハやらFFTやら、私が使ったことのなかったようなアルゴリズムを必要とする問題が多かったため、解けた問題数は「「 0 」」でした。私自身がやってきたことは、このAGCでは完全に無駄だったというわけです。ここだけの話、NoSubはギリギリまで考えていましたが、もし通れば青ということを考えてしまうと心臓が高鳴り、冷や汗も出てくる出てくる。こうなるともはや自分では冷静な判断を下せなくなり、とうとう投げてしまいました。非ロリハの劇遅コード。それは数秒でTLEを吐き、その瞬間、1ヶ月も続いた地獄に落とされました。カイジもこんな感じだったんですかね？(は？)

それからどうやって立ち直ったのか

そのAGCで、1597あったレーティングは1541になりました！！！！！

青パフォを2回も取ってくれた過去の私の努力を水の泡にしました。そう思ったら流石にかなりメンタルをやられてしまいました。その頃は多くの期末レポートにも追われていて踏んだり蹴ったりでした。私はしばらく競プロのことを考えたくなかったし、期末レポートを始末しないといけなかったので、1週間失踪しました。その間はもう期末レポートとにらめっこする日々。おかしくなりそうだったので、お菓子やアイスを買い溜めするようになりました。人間、やはり美食を求めるのは最大のメンタル回復手段の一つ、異論は...一応認める。そう、さまざまなコンビニやスーパーを転々として、私自身の知らなかったお菓子を探す旅に出ていました。あ、別に私は美食殿のギルドメンバーではないです。本当に素敵な子達と出会えましたよ、これは普通に今後も趣味にしていきたいと思う。その中でも特に愛らしかった子...それはmeijiのチョコミントアイスパフェ...。実は今までチョコミントはこの人生であまり食べたことが無かったが、本当に運命の出会いだった。ミントがしつこくない上にチョコがミントを殺していない...それに食べやすい量であった。何より見た目が可愛い、全人類ググってその姿を目に焼き付けろ。それだけではなく私はチョコミントの虜になってしまい、今ではアイスの主流フレーバーの中では2番目に好きですね。(ちなみに1番は抹茶で、あれは抹茶が強すぎるんだよ仕方ない...チョコミントは悪くない...)　そんなわけで、今まで買ったことのなかった会社のチョコミントアイスも結構買いました。アオイちゃんの気持ちが分かった気がしますね。もしもチョコミントに詳しい方いらしたらオススメのチョコミントアイス教えてくださいお願いします。

ここで皆さん忘れているとは思いますが、これは食レポ記事ではなく色変記事です。何が言いたかったかというと、やはりメンタルを壊してしまったらすぐ逃げて他のことに打ち込むというのは最強でした。蜂の巣状態になっていたメンタルはこれでおおよそ回復しました。

災難４. 無精進って怖いよ

 メンタル回復！良かったあ！で終わると思った？何か忘れてない？私は1週間精進をしていないということに。

「ABCって...あると出たくなっちゃいますよね...。」

そういって私はコーナーケースにハマって1541あったレーティングを1505にまで減らしました！！！！！

完全に競プロの勘が鈍っていましたとしか言えません。その回ではDPの問題もありましたが、DPは得意寄りのはずなのにコンテスト中に解法を思いつくことができませんでした。後日やったら普通に一瞬で解法分かりました、はい。無精進って怖いよ。競プロは1日休んだら3日分下手になると思った方が良い気がしました。当然メンタルまたダメになってしまった。あ、でも期末レポート終わった分、AGC事件と比べたらまだ傷は浅く、なんとか致命傷で済んだかなという感じでした。

それからどうやって立ち直ったのか②

いつも通り、まだ知らないお菓子やアイスを探す旅に出かけていましたが、この時期に私はなぜかHUGっと!プリキュアを観始めました。理由はよく分かりませんが、人間はメンタルが壊れると幼児退行してしまうのかもしれません。しかしまあこのアニメ、小さい女の子が観るアニメとしてはえげつないことしてたり、なかなか話が重めでびっくりしました。ルールー・アムールというキャラに感情移入しすぎてしまってとても泣いてしまいました。(どうでもいいけど、声優が田村ゆかりさんでびっくりしました。10年以上前の作品である「ひぐらしのなく頃に」の古手梨花のイメージが強かったため。また、ルールー・アムールについてはネタバレが怖いのでこれ以上の言及は避けます)　また後半では、悪役だった人たちがプリキュアたちと楽しくワイワイしているので、そこに萌えを感じました。その中でもチャラリートはキャラとして結構好きです。思い切り余談ですが、この作品ではプリキュア史上初めての男の子のプリキュア(キュアゴリラ除く)が誕生したことでも有名らしいですね。当時はTwitterでもトレンドになってて何事？と思ったのを今でも覚えていて、実際そのシーンをこの目で観たときは感動しました。

ここで皆さん忘れているとは思いますが、これはアニメのレビュー記事ではなく色変記事です。何が言いたかったかというと、この作品では溢れるほどの元気と勇気をもらいました。多くのキャラから自分を貫く大切さ、夢を追いかける素晴らしさを教えられたことで、私もなんだかんだ言って青コーダーになりたい！という熱意、信念を取り戻すことができました。今では、前に進めずにいた自分を勝利の女神がこの作品を勧めてくれた、だから観始めることになったのかなとさえ思えてしまいます。メンタルが壊れているときは、この作品だけでなく、そのような大切なものを教えてくれるような作品を観るということで、大きくメンタル回復することができるでしょう。

災難５. 数分差でABC177にて入青を逃す

正直これは比較的そこまで災難ではないですが、以下がこのコンテストでの私の提出一覧です。

 コンテスト前のレーティングが1505だったため、もしFがコンテスト中に通っていれば2200以上のパフォが出て入青だったのだが......。(Eの実行時間見るな見るな見るな見るな見るな、後日正しい解法学んでそれで通したので許してください。。。)　それにしても2分差で2200以上のパフォ逃すって...一体どれだけ不運(というよりかは実力不足なだけだが)に見舞われないといけないんでしょうか。とはいうもの、Eまでの早解きでレーティングは1505から1546になり、黄パフォを取れば即入青という状況にやっと戻れたわけです。

これは全く関係無いことですが、実はABC177-Fは普通の遅延評価機能が無いセグメント木でも十分高速に解くことができます。実際私もそのように通しました。需要があるのであれば、その解法を紹介する記事を書くか検討しますがどうでしょうか？コメントやリプ等よろしくお願いします。

有終の美

長かった地獄のような日々も、2020年9月13日、その日に終わりを迎えました。それはABC178が開催された日。そのコンテストでの出来事について書きます。

そのコンテストでは、まずA～Eの早解きにかなり成功しました。A～Dはともかく、Eは見てすぐに解法が分かり、その問題を見てから解法の正当性の証明、実装完了、ACまでの流れを5分で終わらせることができたのが大きかったです。それは、数々の精進の中で自分なりに確立していった考察パターンをうまく引き出せたからだと感じました。しかし、Fが壁でした...それは貪欲じみた問題だったからです。私は競プロを始めてから今までずっと、貪欲が大の苦手でした。なぜかというと証明が難しいからです。私は「基本的」には解法の正当性を示す、あるいは証明してからコードを提出するというスタンスで競プロを続けてきました。(グラフ問題も証明が難しいので苦手です)　順位表を見たとき、このFを通さないと間違いなくこのコンテストではまた青コーダーになれないということが明らかでした。とはいえ貪欲を目にした以上、もう私の目の輝きはほぼほぼ消えていたと思います。しかし、やはりどうしても諦めたくなかった、その栄光を時間いっぱいまで追いかけて追いかけて掴みたかった、そういう思いが込み上げてきました。私は最後の最後まで諦めませんでした。今まで貪欲ではどういう手法がありがちだったかを必死に思い出して考えてみました。そしたら思いついてしまった、そのFで使える手法を...そしてある程度の正当性を示すことができましたが、まだ完全に示し切ることはできませんでした...。そのときはとりあえず無我夢中でコードを書き殴り、それを提出した結果...。

......通った───────────────────────────────────。

「AC」という輝かしい表示を見た瞬間、泣いてしまいました。その後はコンテスト終わるまで、ずっとTwitterでてんやわんやしていました。それで、しばらくしてFの解法の正当性をきちんと示すことができてしまい、またてんやわんやしました。まさかあれだけ苦手だった貪欲の問題を通して、なおかつ解法を示して、もっと言えばそこまで得意ではないセットにて全問の解法の正当性を示し、それで全完してゴールをすることができたと考えたら、今までで一番実力を出し切ることができたし、本当にちゃんと精進してきて良かったと思えました。この上ない、最高の青コーダーのなり方だったと強く思っています。

ちなみにFでstd::setのイテレータ操作をしたのですが、一発で書けたため、それもなかなかに嬉しかったです。私はコンテスト終了10分前からは宴がてら、例のmeijiのチョコミントアイスパフェを食べ始めました。しかし残念なことに、その頃からそのmeijiのチョコミントアイスパフェは行きつけの店から消えていました...このとき食べていたそれが最後だったのです。もしかすると、このアイスは私が立ち直れるようにするために私を虜にしたが、その役割を終えたために私の前から姿を消してしまったのではないか...というようなメルヘンチックなことさえふと考えてしまうほど、今の気持ちはとても晴れやかだった...。でも、やはりそのアイスを失ったことは辛いので、またそのアイスが並んでいる店を探したいと思っています...。

そしてコンテストは終了しました。そして私のレーティングは...？ドン！

はい、この日から私も青コーダーです！！！！！！！入青ツイートにリプ,いいねくださった多くの方々ありがとうございました...！青コーダーになることは競プロを本気でやり始めた頃の夢だったので、最高の気分です。

これからのこと

競プロを本気でやり始めた頃に掲げた夢は叶えることができました。しかし、競プロをやるにつれ、私にはまたひとつ大きな夢ができました。それは黄コーダーになることです。もちろん、今まで以上の難解な問題やアルゴリズム、データ構造と向き合うことになるでしょうし、AGCが苦手などと言っていられる場合ではなくなってきてしまうのでしょうが、今はやれるだけやりたいと思っています。応援よろしくお願いします...！ある方も言っていましたが、やはりみんなで黄コーダーになりたいですね。(当時は緑コーダーだった私含むさまざまな人が今では全員青コーダーになりました。本当に皆成長しました。そう考えると目頭が熱くなってきます。)

また、これを機にWeb開発等にも本格的に挑戦していきたいと思っています。「おいおい、黄コーダーも狙うんだろ？大丈夫？」と思った方々、安心してください、私も両立できるか分かりません！！しかし、これは青コーダーになったらやろうと前々から決めていたことなので、時間がかかろうとも並行して頑張っていきたいと思っています！開発に強い方々、私が困っているときはいろいろ質問するかもしれませんが、そのときはよろしくお願いします...（；；）

あとがき

とてもどうでもいいが、あらゆる言葉の意味をうろ覚えしているため、辞書が無いと記事書けないがち。早くこの記事を読んで欲しいので、推敲する前に流しておきます。急いで書いている部分もあるので、意味分からない文章や構成もあるかもしれません、ごめんなさい。また、気分でエピソード追加するかもしれません。そのときはそのときのお楽しみです。

私自身でも見返してて本当に意味の分からない記事ができてしまったのですが、ここまで読んでくださった方々、本当にありがとうございました！