見出し画像

文系ギャルが0から始める競技プログラミング#34

マリー

Intro
この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#33

・特別編「茶色になるまでにやったこと」

ご無沙汰しています。
文系ギャルです。
元気に優勝しています！！！！！！！！！！！！！！！！

このたび茶色になりまして、

僭越ながらこれまでのまとめを書きたいと思います。(天才なので)
・プログラミング初学者がAtCoderを"楽しんで"続けるための道案内
・お友達を競プロ沼に沈めるためのエサ
として最近はじめたよ！これからはじめたいな！という人に役立てばと思います。

ようこそAtCoder沼へ！！！！！！！！！！！！！！！！！！！！！！！！

・基本的な入力/出力と、便利なやつ

#0にも載せましたが、とりあえずココで基本の書き方を学びました。

具体的には四則演算とifとforがわかってればOKだと思います。
入力/出力はcinとcoutを使います。

↑これとか見た
そうして、#1につながっていきます。いわば#0.5。
天才伝説の偉大なる第一歩です。

「誰かのコードを読め！」ということが割と言われていると思いますが、
基本的にすごい人は、すごい便利パーツをいっぱい持っていて、便利カスタマイズをして早く、正確に書こうとしています。（説明が雑）

なので、先輩たちのコードを見ても、何言ってんだ…？となると思います。
便利パーツの作り方がわかってくるまでこれを理解することは無謀なので、
自分でも分かりそうな書き方をしてる人を見つけて、その人のコードをこっそり拝見するのがいいかもです。(これに気づくのに時間がかかった)

・便利なものたち

ここからはABCのA問題をときまくり始めたので、
AtCoderで実際に問題を解いたり、コンテストに出るにあたってお世話になった便利なものたちを紹介します。

・@kenkoooさんのAtCoder Problems

過去コンテストの出題から難しさがいい感じの問題を探したり、ACしたやつをマークしてくれたり、埋めていく段階で死ぬほどお世話になるサイト。
優勝！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
上の入力欄に自分のIDをいれよう。

・えびちゃんのAtCoder Scores

これも過去問便利系。点数順にまとめてくれてるので便利！
優勝！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
Twitterでよく見る精進グラフはここ。
挑戦者の欄に自分のIDをいれよう。

・keymoonさんのac-predictor

コンテストにコンスタントに出始めたらほしいやつ！（韻）
コンテスト中に順位表を拡張して予測パフォを載せてくれる。
優勝！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
Chromeの拡張機能で動かしているよ

・Bへのステップアップ

上記便利なサイトをうまく活用しながら、A問題を解きまくること数十問。
なんとなく形式と、かんたんな計算に慣れたら"考える"ステップに移行しました。
#3でB問題に初めて挑戦していますが、まず解き始める前に問題をよく読みます（これ超スーパーミラクル大事）。
わたしは紙を用意して(のちにiPad＆Apple Pencilを買う)、ガシガシ図を書きながら ①問題の前提 ②今の状況 ③動かし方 などを考えながら整理していきました。

画像1

実際の作業的には複雑なものが必要なく、考えがまとまりさえすれば、それを知っている知識でアウトプットすることができれば解けるような気がしていたので（天才だからかも）、"考える"ことに慣れるまでしっかり書きながら考えていきます。

途中で「これ小数点以下どうすんだ？」とか、「配列を順番に並べ替えたい…」とか、「２つの数の大きい方/小さい方がほしい…」とか、できないことが出てきたら、ぐぐると基本的に便利ななにかが見つかるはずなので、その都度それを覚えたらもう優勝確定です。

もうあとはばしばしと解いていくだけ。
ちなみに解く問題はもちろん多ければ多いほどいいと思うので、何でもいいですが
とっつきやすさでいうと(一番最初とかは)↓がおすすめ。

AtCoder Beginners Selectionとは？
このコンテストは、「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集です。
問題は、dr.kenさんの、「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」から選出しています。
まずはこの問題を順番に解いていきましょう！
ー AtCoder Beginners Selection

この問題集はすごい人たちの解説記事が世にたくさん出回っていたりするので、詰まってしまって解説を見ることになっても、かなり勉強になると思います。
過去の記事で扱ってるものも多いので、これから解いていく方はネタバレに注意。

・その先

そうこうしているうちにAtCoder Beginners Selectionも後半に差し掛かり、C問題が出てきます。
#18がABSのラストだったようです。
この辺から、"考える"を強化した問題と、"覚えるテクニック"が必要な問題と、その両方に分岐していく気がするので、まずは"考える"の対策を書いていきます。
数学の定理だったり(これはググり倒せ！)、偶奇をうまく使うことだったり、最大公約数だったり、あとは確率かな？
数学的"考える"テクニックがこのあたりからがっさり増えます。
サンプルから推測したりしながら、「コレにはアレを使う…！？」と思いつけたら優勝です。(天才)
割と物覚えがいい方の自覚があるので(これは天才アピですが)、一度見たことはだいたい忘れないので、類題が記憶にあったら解けたりします。
たくさん解いてみるのが何より大事です。

あとは計算量という概念がこの辺から生まれます。
思いついた道筋が正しかったとしても、AtCoderにはタイムリミットがあり
計算量が多すぎてTLE(時間オーバー)することが多々あります。
なるべく少ない計算量でゴールに辿り着くにはどうするのがいいんだろう？
と考えることも必要になってきます。

・参考書籍

もう一つ、"覚えるテクニック"については、先人の解説や本を読みましょう。
この段階では若干まだ早いのかもですが、いずれ確実に時がきます。

本でのおすすめはこの３つ。
Amazonで定期的にセールをしていたりします。

ブログ記事では、けんちょんさんのQiitaがとても勉強になります。
"覚える"テクニックには、DP、累積和、しゃくとり、DFS、BFS等ほかにもたくさんよくわからないのがあって、テクニックの解説見ても「じゃあどういう問題だったら使うわけよ！？？！？？」みたいなのがピンと来ないと思います。

わたしは、
問題みます→わけわからん→解説みます→「ふーん、DPっていうやつ使うんや〜」→DP 競プロ　C++ [検索] → 類題を解きます→パターンがなんとなくわかる
みたいな感じで、問題文から何を使うか、どう実装していくかひらめけるようにパターンを覚えるように努力しました。（まだ全然だけどね）

まあ今はAtCoder Problemに推定難易度が表記される神機能が備わっているので
簡単そうなのから(灰色で丸があんまり埋まってないやつ)←伝われ 解いてみるのがいいと思います。
解けないと楽しくないので、かんたんなのから埋めていこうね。

・結局何が言いたいの？

こんな感じで解ける問題が多くなり、精進しているうちに茶色になりましたが
一番大事なことは「"正解"を作るには、どのように動かしていったらいいだろうか？」ということを多方面から(考察から、作図から、プログラミング力から、数学力から、日本語力から)考えて実現することだと思うので、1問解けたらもう天才です。(いいことをいった)
より天才になりたければ、足りない力は伸ばせばいいです。

あとはTwitterとかにお友達がいると楽しいので、気軽に絡んでください！


Outro

#35に続く ！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。

いいなと思ったら応援しよう！