雑記

魔法少女になりたい

AtCoderで黄色になりました。

これはなに

色ポエムです。ポエムなので大抵が自分語りです。許してください。「黄色になるまでに何をしたのか」を純粋に読みたい場合は、記事を最後まで読む必要はありません。(おまけはおまけなので)

はじめに

2019/06/29に行われたABC132にて、AtCoderで黄色になりました。苦節20ヶ月、とりあえず1つのマイルストーンに到達することができたことを嬉しく思っています。

 

 

黄色になるまでにしたこと

注意 : 途中まで書いて気がついたのですが、「青下位から青中位までにしたこと」の記憶が完全に飛んでいるため、「青中位から黄色になるまでにしたこと」になっている気がします。ただ、記したことは一般論のようなものなので、概ね影響がないと思います。

問題を解く

言うまでもなく、問題を解きました。自分にとって最も効果的だった精進は、「自分がコンテストに出た時に通せたら嬉しい範囲の問題」を解くことです。レート1800台の時は700-800点程度でしょうか。以下のツイートの青くらいの範囲を二日に一問程度解ければ理想だと思います。

 

これにより実力は上がっている実感は実際のところありませんでしたが、明らかに成績は向上しています。自分の考察スタイルは論理的に詰めるのではなく、考察をとにかく手当たり次第に行って考察を進めるスタイルです。解法ガチャとか呼ばれてますね。ガチャの当たり率が上がった気がしました*1

以下のツイートは黄色になった時点での自分の精進量です。

 

精進グラフです。

f:id:keymoon:20190630222735p:plain

注意ですが、この数を真に受けないでください。自分はJOIの低難易度やABC-A/B等を全て埋めているため、相当「盛られて」います。(2018年冒頭のそれが盛った形跡ですね。)

また、自分の場合は考えることで導き出した答えがより身に入るため、解説ACは行いませんでした。その代わり、テクニックに貪欲になるよう心がけました。

面白い性質や問題を見た際、「その性質がどこまで一般的に通用するか?」ということを考えるクセを付けると良いと思います。これは「素振り典型」とか勝手に呼んでいるものとも近く、「今回の問題はこういう性質があったからこういう方法が取れたんだな!」とか思えると良いです。また、同じくアルゴリズムはできる限り抽象化して理解することをお勧めします。「累積和を二本合わせるテクはXORでも使える!GCDでも!」と個別に理解するより、「累積和を二本合わせるテクは順序を入れ替えても結果が変わらない演算*2全てに使える!」と理解したほうが効率は良いです。

勉強したアルゴリズムは例題を解くだけでなく、ライブラリを作りました。自分は比較的マイナー言語であるC#競技プログラミングをしているためライブラリは自作せざるを得なかったですが、ライブラリを書くことは確実に理解に繋がります。また、上記の抽象的な性質を捉えることの助けにもなります。

また、面白そうなアルゴリズムの記事を見つけたら貪欲に読み、理解し、ライブラリを生やしましょう。リツイートして #後で読む とするだけに留まりがちではないですか?(自戒)

メンタリティを意識する

コンテスト中の精神管理は、コンテストの成績に直結すると言っても良いであろう事項です。しかし、あまり言及を見かけません。みなさんも以下のような経験はありませんか?

  • いつもならば解けなさそうな高難易度の解が見え、緊張してしまったため自明な嘘だと見抜けなかった。
  • 残り5分で実装を終えるも緊張してデバッグが不可能になり、自明なバグを見落とす。
  • 自明であろう問題でWAを出してしまい、その後の問題が読めなくなる。
  • 順位表を見て、自分の順位の低さと推定パフォーマンスの色に動揺してしまう。

自分は全てありました。そして、これを克服できればパフォーマンスが上がることも明らかでした。

ここで、自分の行った対処を紹介します。

まず、通常時から成功体験を積むことです。高難度を何問か通せた経験があれば、コンテスト中もある程度落ち着けるようになります。また、WA判定を受けた際、できる限り平常心を保つよう心がけました。練習でもWAに動揺していたら本番でも動揺するのは当たり前です。さらに、普段の精進中にもコンテスト中に行う思考を心がけることも大切です。動揺するとどうしても頭が真っ白になり、何をするべきかがわからなくなってしまいます。普段からやるべきことを心がけていれば、自然と本番でもできるようになるものです。

自分が最もコンテスト中のメンタル管理に成功したと思った事例は、終了40分前から考え続けて10分前に考察が終わり、3分前に提出したものがTLE判定を受けた際の対処に成功したものです(画像)。これは成功体験となり、自分のメンタルの強さに対する大きな自信となりました。

f:id:keymoon:20190630233103p:plain

また、コンテスト外での精神状態も重要です。

highestを更新しない期間が(たった4ヶ月程ですが)ありました。この時は問題をコンテスト外で解いていなかった上に競プロにフォーカスしていなかったので当たり前ではありますが、コンテストに出る習慣を失わなかったのは結果として良かったと思います。継続することは衰えを減速させることが可能です。

精進に気持ちを向かわせることも大事です。ただし、これは自分があまり上手くないのでなんとも言えないです。自分の場合は「精進したい気持ちになるまで待つ」ことを心がけました。焦ると焦りが先行していいことがない気がします。寝ようと無駄に焦っておふとんの中で眠れなくなるアレと同じですね。

それと、人のやり方/言説に惑わされないようにしました。人のやり方は参考に留めるべきです。もちろんこの記事も。using namespace std;をやめるかは自分で判断することですし、解法ガチャも無証明もOEISエスパーも、自分の判断で行うべきことです。やるかを決定する過程で人の意見は当然参考にするべきですが、無条件に意見を信奉して自分を見失うことは避けた方が良いです。自分の体に合った方法を見つけましょう。

最後に

まだまだ書きたいことがあった気がしましたが、多分これくらいで十分な気がします。コンテストで使った知識を載せて終わりにしたいと思います。思いつく限り列挙しているため、抜けは確実にあります。許してください。

使った知識

 

おまけ1:茶~青色になるまで

色ポエムをそもそも今まで書いたことがないということで、青になるまでの分を書いてみました。

最初は本編に入っていましたが、あまりにも自分語りが過ぎるので分離しました。個人的にはこれよりおまけ2を見てほしいです。

競技プログラミングを始めるまで

はるか昔、Objective-CiOSアプリケーション開発の触りをやりました。思えばあの頃、塾の課題を全探索してサボっていた僕は本質的に競技プログラミングがやりたかったのかもしれません。当然競技プログラミングなんて知らない僕は次第に飽き、フェードアウトしていきました。

プログラミングを再開したのは2016年の12月です。その当時ハマっていた筐体音ゲーを家でプレイしたいという欲求からUnityに手を出します。結果としてプレイアブルなものが完成しました。ここでプログラミングの楽しさを知り、NAudioを弄ってサンプル単位でループ再生が可能な音楽プレイヤーを作ったりTwitterbotを宅鯖で運用するなどしてしました。

2017年10月初頭、以下のツイートを見かけます。

このツイートを見て「競プロ」という概念を知りました。

2017年11月初頭、文化祭が終わって労働から開放された僕は暇になります。AtCoderC#も使えることを知った僕は、競技プログラミングでもを始めようかとぼんやり思っていました。

さて、僕はその後開催されたABC077に出損ねます。これは、かの有名な「Small Multiple」による大虐殺回でした。これに出ていたら恐らく競プロを継続していないでしょう。運命に感謝。

茶色になるまで

f:id:keymoon:20190630193506p:plain

紀貫之みたいなノリでABC078に参加しました。

このコンテストはDの入力受け取りのみにしかfor文を要求されないようなコンテストで、なんと初回参加で17位を取ることができました。

f:id:keymoon:20190630200900p:plain

 完全に味を占めた僕は、こうして茶色に、競技プログラマになりました。

  • 使ったテクニック/知識 : 入出力、for文

緑色になるまで

あまり覚えていません。コンテストに継続的に参加し、無事緑まで到達することができました。

f:id:keymoon:20190630203612p:plain

水色になるまで

ここで、僕は大きな失敗を経験します。JOI予選落ちです。バチャをしていて勝率が80%程度だったため、高を括っていたら無事落ちました。残念。

ABCと間違えてARCに出たショックからTwitterアカウントを動かし始めた*3僕は、2017年最後のABCで水色になることができました。

  • 使ったテクニック/知識 : DP、シミュレーション、埋め込み*4

青色になるまで

水色になった僕は蟻本などを読み、本格的にアルゴリズムの勉強を始めました。しかし、精力的にやろうとしなかったためコンテスト3回分ほどの停滞期(?)を迎えてしまいます。

学年が上がるまでに色を変えることが目標だった僕は非常に焦り、少しずつではありますが蟻本を読み進めました。AGC→構築回→速解きと成功を重ね、恐らくこの時点での実力であった青下位に急激に突入しました。この後、その影響で青下位での停滞が続くことになります。

  • 使ったテクニック/知識 : エラトステネスの篩、imos法、UnionFind、next_permutation、テストケース特定

おまけ2:タイムカプセルのはなし

これはなに

 青になった週の僕が「ブログに書くネタにどうせ困ってそうだから」みたいな理由でタイムカプセルを遺してくれていました。生意気ですね。ありがとうございます。

正直すっかり忘れていて、さて記事を書くか!となった時に電撃が走ったかのように思い出しました。思い出した時は本当に感情が爆発しそうになりました。月並みな表現だとエモいって奴です(語彙力)。

読んでいる時に一段落ずつコメントをつけていたら、ちょうど対談のような感じになりました。ということで、対談企画と題して放流したいと思います。現代の社会通念上不適切な表現もありますが、改変するのも何かが違うと思ったのでそのままにしました。

ただ、書いていることは上述の通り記事のネタになっているため、内容の重複も多いです。要するに出涸らしですね。

本編

とりあえず、黄色おめでとうございます。青までは競プロをしていればなれて*5、黄色が実力が保証されるラインだと感じています。

ありがとうございます、本当に。それにしても、「青までは誰でもなれて」って凄いこと言ってますね。全くそんなことはないのに。実力保証されちゃった。わーい。

 

黄色が凄い人なのはどう考えても明らかなので、もし上を見て卑屈になっているなら更に上を見ることを一旦やめ、下を見てみてください。昔の自分がちっぽけに見えることでしょう。

すごい人だって すごい人だってさ。嬉しいです。レートの価値とか云々言われてますけど、あなたから見れば今でも十分凄いですよね。今の僕が橙を見るのと同じように。

まあ卑屈にはなってないですね。ということはあなたが卑屈になってるのかな?もっと素直に喜べばいいのに。でも、あなたからほぼ成長していないみたいな感覚はありました。そんなあなたから見ても十分黄色は凄いんですね。面白いです。成長できたかな。

 

グラフはどんな形でしょうか。ギリギリ掠った?調子が良くてブチ抜いた?青の頃より、更に停滞へのプレッシャーは強くなっているはずです。負けないように、そして「レートを意識しすぎるとつまらなくなる」ということを忘れないでほしいです。

 グラフね、ギリギリ掠りました。本当に2050適正って感じで、漸近していく感じで近づいていきました。これからが大変そうです。

レートを意識しているとつまらなくなる、まあそうかもしれないですね。少し前の停滞期は実際辛かったです。でも不思議と停滞に対する恐怖はないですね。一時期の停滞を克服したからかもしれません。停滞については後述します。

 

ところで、どのような精進を積めば黄になれましたか?今の僕は解説を読む癖もないですし、問題も余り解かなくなってしまいました。600点ですら通せるか怪しく、平常時なら400すら億劫で通せないことが多いです。

 精進、むちゃくちゃありきたりな質問ですねそれ。そう思ったのだけ覚えてますよ。「ありきたりな質問しか出てこない」って。
600ですら通せるか怪しく400ですら億劫、実は今でも変わってないんですよね。やっぱ成長してないじゃないか!(というか青なりたてのあなたが「600を通せるか怪しく」って、それができたら黄色ですから。目標高すぎ。)
でも、(体感は別として)実際600は安定して通せてます。確実に成長はしたんだろうなあ。
「どのような精進を積めばいいか」については次の質問が関連しそうなので、一緒に答えてしまいますね。

 

通常時にやる気を出すコツはなんですか。春への思いでしょうか?それとも、黄色に対する思い?

通常時にやる気を出すコツ、僕がうまく行ったのは、「やる気を出すというより「やる気になるまで待つ」」って奴です(眠い時に布団に潜って寝ようと努力するより、眠さを待ちつつ読書をするのと同じですね)。でもすぐやる気が出したいって?その方法は僕もまだ分からないです。ごめんなさい。
僕がやる気を出すきっかけになった話をしましょうか。これが面白くて、「春への思い」ではないんです。あなたは将来、残念ながら春合宿に行けません。怠惰なので精進をしようとせず、本番に自明貪欲を見落とします。それが悔しいのかなんなのかはわからないんですが、何故かやる気が出てきました。今でもそれは継続しています。
で、どんな精進を積んだかですよね。個人的にはこれといったものはありません。

問題を解く際、解説ACはしなくて良いです。(だってあなたは考えたものの方が頭に残るでしょう?)なので、自分が解けるか解けないかギリギリ程度の問題を考えるようにしましょう。

それと同時にやらなければいけないのは、新しいテクニックを身につけるようにすることです。これについてはアルゴリズムの話とかと繋がりますね。後述します。

 

アルゴリズムはどのようにして学びましたか?僕は構築等の地頭ゲーは得意ですよね。しかし、アルゴリズムができなければ黄には行かないはずです。

正直なところ、あなたがその後勉強して必要になったアルゴリズムはありません*6。強いて言うならセグ木で数回殴りましたが。ただ、アルゴリズム/データ構造の勉強は楽しいですよ。実際のところ。それと、恐らく橙を目指すに当たって本格的に必要になってきます。
それよりも大事なのは文字になっていない典型というか、あれです、素振り典型です。直感力とも言えます。
僕は問題を解いたり、何らかの面白いものを見たりした時に「どういう状況であればこのテクニックが使えるか」と一般化することを心がけました。累積和は結合法則云々が成立するなら使える、みたいなやつです。
ああそう、構築は割と出るようになって嬉しいですよ。ちゃんと全て通せています。それにしてもあなた、自分の地頭に謎の自信がありますね?僕はもうないです。

 

必ず青の間に停滞期は訪れている筈です。その時に、どのようにして乗り切りましたか?落ち込んだのはそうですが、気持ちを切り替えることはできましたか?

停滞期ですか…ありましたねぇ。というかJOI後の数ヶ月以外は全てが停滞期でした。
Highestを更新できない期間がとても長いのは本当に心がしんどくなります。ただ、そういう時でもコンテストに出続けました。まだコンテストは楽しいと思えていたので。継続は大事。精進もせずに怠惰に出るのは決して悪いことではありません。いつか成功し、やる気が戻るきっかけとなったりします。

 

勉強など他のするべきこととの両立はできたでしょうか。もしできてないなら、流石にマズいので頑張ってください…

お前お前お前お前~! 言うじゃないですか。分かってるじゃないですか。そうなんですよ、できてないんですよ。マジヤバい。
いや今日でTwitter控えるんで。マジで。明日から本気出ーす。

 

最後になりますが、とりあえず大学卒業までに橙になれると嬉しいですね。応援しています。

これ本気で思ってますか? 去年*7中に黄色とかあなたが言っていたのを覚えているので、その目標が達成できなかったときの精神安定の為に書いたとか。
深読みしすぎか。だとすると、この目標はぶれてないですね。大学卒業までに橙。方針通りに進めているのかもしれません。
頑張ります。まずは受験の方をですけどね。

最後に

過去と現在の深夜ポエムを晒してしまいました…(絶対後悔する。)

タイムカプセル、いいものですね。普段は客観視することができない自分を客観視することができました。もう少し話を聞きたかったな、って思ったりしました。

*1:ちなみにくじ引きサイクルというゲームはガチャの当たり率を上げて当たりを引くことが目標のゲームです。時間が溶けるので絶対にやるべきではありません。自分の最終リザルトは黃229個です。

*2:これを「結合的な演算」または「結合法則が成立する」と呼びます。セグ木に載るやつですね!

*3:当該ツイート(リンク)、しかもパフォ1955の大成功でした。なに凹んでるんだ。

*4:素数リストをネットから落としてきて埋め込み、エラトステネスの篩を使わずに通しました。

*5:これが不適切な表現です。青になりたてで卑屈になってるだけです。全くそんなことはないと思います。許してください。

*6:これは嘘で、BinaryHeapの実装(C#にはないため)、行列累乗が役立ちました

*7:青になった年と同じ年