FatherScorpion's diary

年1更新!...できたらいいなぁ。

AtCoder緑になりました。

久しぶりの更新です。タイトルの通り、AtCoder緑になれたので色変記事とやらを書いてみようと思います。基本的には感想多め、入茶~現在までにやってきた事を書いていこうと思います。

ABC167にて緑化

f:id:FatherScorpion:20200511021910p:plain
2020年5月10日開催のAtCoder Beginner Contest 167にて緑化しました。


目標パフォは1081.67でした。当時私は4桁パフォなど数える程しか取ったことがなかったので、上手く行けば緑化できるかなぁ~程度の気持ちで挑みました。問題の内容としては、Cがbit全探索、Dが考察実装系と得意分野が重なった事もあり、4完時点で緑パフォ4桁後半。この時点で希望が見え始めました。
ただ、この時点で予想レートは810ぐらいだったので、割と心臓バクバクでした。

それでもなんとか


無事緑化できました。
ちなみにこの回で色変した人がTLで結構多かったです。

感想

素直に嬉しいです。同時に、ここから厳しくなるぞとも感じています。

なぜ緑になれたか。

ぶっちゃけて言うと殆ど某ウイルスのせいです。

私は高専という学校に通っていて、ただでさえ高専は春休みが長い(2月中には春休みが始まる)です。その上授業開始が遅れたので、4ヶ月近くも休みがありました。とにかく時間が余っていたので、APG4bを進めたり、螺旋本を買って読んだりと、競プロにかける時間が明らかに増えました。これが緑化に繋がった事は明らかだと思います。

緑になるまでに何をしたか

自分を振り返りつつ、何が緑になるために必要なのかも考えてみています。果たして緑になりたての人が偉そうに語ってよいのでしょうか。

競プロ的思考を身に着ける

他の方もおっしゃっていましたが、緑になる為には「競プロ用の訓練」が必須だと思います。私は高専プロコンでの開発が実質初のプログラミングでしたが、自分が開発した範囲では使ったアルゴリズムは全探索だけでした。完成版は先輩方がリファクタリングをして下さったおかげでスッキリしたコードになっていると思いますが、開発中のコードは兎に角無駄が多い、極端な話、x=100-nの計算をする時にfor文でx--をn回するみたいなクソコードを書いていた気がします。

流石にそれは大袈裟と思うかもしれませんが、灰コーダーの時期は冗談抜きでこんなコードを書いてたと思います。何故ならそれで動くから。競プロerの皆さんは計算量が多いと聞くと10^18ぐらいを想像すると思いますが、当時の私は1000でも多いと感じ、それを一瞬で計算し終わるコンピューターすげーという感じでした。

競プロ的思考とは言い換えると「無駄を削ろうとする考え方」だと思っていて、「ここの処理無駄が多いな」となった時に、「別に動くしいいや」となるか、「どうにかして削ろう」となるか、あるいはそもそも無駄な事をしている事に気が付けるかだと思っています。

これはアルゴリズムを学ぶきっかけにもなったと思います。私はどうやったら無駄を削れるんだろうと考える様になってから初めて、数多のアルゴリズムに触れる様になりました。

数学(算数)は必ずしも必要ではなさそう

最初に言うと私は相対的には数弱な人間だとは思います。なので、今でも数学問題はパスか未証明偶然ACが8割近くを占めています。それでも緑にはなれたので、数学が必ずしも必要である、とは思いませんでした。勿論解けるに越したことはありませんが、どちらかと言うとアルゴリズムに重点を置いた方が良い気はします。

とはいえ、数学的な問題をアルゴリズム的観点からばかり考察してしまい、「この問題、競プロの問題じゃなくて数学の試験で出てたら解けてただろうなぁ」となった経験も度々ありました。これはかなり勿体ない気がするので、一応数学的な考察もするだけしてみる方が良いとは思います。

早解きは狙ってする物ではない

早解きは大事です。早解き出来ると出来ないではパフォーマンスに大きく差が出ますし、同じ3完なのにあいつは水パフォで俺は灰パフォ...とかになると早解きをせねば...!!!となると思います。

ただ、私は早解きは「する」物ではなく、「出来るようになる」物だと思っています。自分を例にすると、昔の私はC問題に90分フルで使うのもザラでしたが、今は安定して30分以内にはCが解けるようになってはいます。ですが、実を言うと早解きを意識しているのはむしろ昔の方で、今は「絶対にペナを出さない」という真逆のスタンスでコードを書いています。

ここで言う昔と言うのは灰~茶前半の頃なのですが、当時はCが解けず2完という事が多く、AとBを死ぬ気で早解きする事に心血を注いでいました。今考えるとこれは失敗だと思っていて、テストケースすら通らないコードを大量に投下し、毎度毎度ペナが笑えるぐらいの量になっていました。

当たり前の話ですが、急いで早解きしてペナ5分を貰うより、じっくりとテストケースを通して確実にACする方が遥かにお得です。また、そもそも早解きして上がるレートは安定せず、コンテスト開始直前には常に気が張った状態になりますし、失敗した時の喪失感はエグイ物があるので、精神衛生上宜しくないです。私はこれで一時期コンテストの日になるのが苦しくなったりもしました。

という訳で、早解きをするよりかは、CやDを解けるようになる為の勉強をする方が精神的にも楽ですし実力もつくと思っています。結果としてはこちらの方が早解きが自然と出来るようになりました。

そしてやっぱりアルゴリズム

最終的に一番大事なのはこれだと思います。考察を頑張る必要があったり、実装が重めだったりする問題は、頑張れば解けます。ですが、特定のアルゴリズムが必要な問題は、知らなければどうあがいても解けません。

...ですが、今の私が使えるアルゴリズムは、実は二分探索とbit全探索、後は再起関数での木グラフ探索ぐらいです。DPは何ですかそれはという感じですし、累積和あたりもネットで調べながらなら...といった感じです。幅優先探索、深さ優先探索あたりは頭では分かりますが実装はうーん。

何でこんな感じになっているかと言うと、アルゴリズムは「必要になったら覚える」というスタイルで覚えてきたからです。一時期、F問題の解説にDPと書かれていたり、TLでDP便利、DP覚えた!というツイートが流れて来たりとDPという単語を目にする機会が多くなったことがありました。そこで当時の私はDPを覚えようと「DP アルゴリズム」で検索したり、DPで解く問題にチャレンジしたりしてみましたが...結果挫折しました。

なぜなのか、と考えた時、一番の理由は「そもそもDPで何が出来るか」を良く理解できていなかった(今でもそうですが)からだと思います。

分かりやすいように、逆にアルゴリズムを理解できた時の話をします。私が最初に覚えたアルゴリズムは二分探索なのですが、そのきっかけとなったのはこの問題です。
atcoder.jp
この問題は、色々処理をした結果、tan(x)=定数 となるxを見つければ良い事が分かります。ここで、xの取り得る範囲は0 < x < 90だと分かるので、この範囲を総当たりで探索すればxが見つかるのですが...。このx、整数だけではなく小数、さらには10^-6刻みまで取る事が分かります。なので全探索となると、0.000001~89.999999まで、つまりO(9*10^7)となり間に合いません。また、私もこの範囲であればxが90に近づけば近づくほどtan(x)は大きくなるという事は知っていました。ここで、今の状況を纏めると、

  • 総当たり以外の方法はなさそう
  • xが大きくなる程数値は大きくなる(単調増加)

という事が分かっています。色々工夫はしてみますがどうしても駄目、当時の私はここで解説PDFを見て、二分探索という文字列を見つけます。当時伸び悩んでいた私は、ここで初めてアルゴリズムを覚えてみるかという気になり、「二分探索　アルゴリズム」で検索をしました。出てきたサイトを読み進めてみると...なんと分かる、分かるのです。先ほどのDPの例と違い、解説が何を言っているのか手に取るように分かるのです。

なぜ分かるのか、それはやはり、二分探索がどのような時に使えるのかという事を理解していたからでしょう。ある巨大な数列の中から目当ての数を探すとき、その数列に単調性があれば、まずその数列のちょうど半分の数を取る。もしその数値が目当ての数よりも大きい(あるいは小さい)ならば、それよりも大きい(小さい)数はどう考えても目当ての数ではない。ならば、目当ての数はそれよりも小さい(大きい)所にあるので、取り上げた半分の数よりも大きい(小さい)全体の半分にもなる数は比べるまでも無く切り捨てられる...。そのような状況を身をもって体験した私には、二分探索という物が何を目的としていて、いかに素晴らしいのかが良く理解できたのでした。

という訳で、私は新しいアルゴリズムを、「良い所まで解けたが明確な課題が見つかり解けなかった問題」の解説に名前が登場した時に覚えるようにしていました。

例外として、APG4bに登場したアルゴリズムはその通りではありません。自分は1週間に1度程度の頻度でAPG4bを進めているのですが、そこで登場するという事は自分の身の丈に合ったアルゴリズムという事ですし、理解できない事は無いと思うからです。実際ABC167のC問題はbit全探索でしたが、bit全探索をAPG4b以外でACしたのは今回が初だったりします。覚えられるときに貪欲にアルゴリズムを覚える事は決して無駄ではないと思います。

長い!まとめろ!

  • どこかに無駄があるか、その無駄をどうやったら削れるか考えよう!
  • 数学は必須ではないが最初から諦めはせず、手札の1つとしては考えておこう!
  • 早解きを狙うよりは新しい事を覚えよう!その方が早解きはいつの間にか出来るようになっている!

以上になります。

最後に

次なる目標は水色ですが、まだ水パフォを出した事が無いので今後何かしらの努力はしないといけないなとは思います。レートの停滞期がすぐそこに迫っている事をひしひしと感じますが、今年中に水色になる事を目標に頑張ります。

本当の最後に私事ですが、新しい後輩に青コーダーがいるらしいのでいつの日か彼を超えたいです。未来の自分よ、頑張ってくれ。