挨拶
初めまして、katsutaという名前でAtCoderに参加している者です。
最近ようやく入緑を成し遂げたので、灰色と茶色時代のことを語っておこうかなと思いまして、記事を書いている次第です。
ヒューリスティック↓
自己紹介
- ただの中学$3$年生
- AtCoder(というか競プロ)は友達に誘われてやり始めた
- 当時プログラミングなんて触ったこともなく、競プロについても友達に教えてもらうまで存在を知らなかった
- $7$月初めに、ただ何となく競プロを始め、$9$月の終わりに入茶、$12$月の頭に入緑
- 文理で言えば理系ですが、それでも数学は苦手です(
勉強してないだけ) - ちなみにipad勢です(!?!?!?)
- PCが欲しい
初めての参加
私が初めて参加したのは、7月6日に開催された、ABC361でした。
この時、私は過去にプログラミングもやったことがないのに、APG4b(超初心者向けに文字通り1からコードの書き方を練習できる神サイト)もあまりまともにやらず参加した覚えがあります。
確かfor文まではやってたような気がする…（覚えてない）
言語は、私の友達がC++をやっていたこともあってPythonにしました(?????????)
友達からは「基本的にはC++かPythonかのどっちかだと思うし、好きな方を選んだら？」と言われ、両方試したのですが、C++の書き方は頭の弱い私では理解できず、Pythonを選択しました。
いよいよコンテストが始まり、A問題を開きました。
が、よくわからないままにコードを書いて提出しては、"WA"と言われて……ということをコンテスト中ずっとやっていました。
言うまでもなく実装力不足です。
空白区切りで渡される配列を文字列をして受け取っていたりだとか、for文内で添字をバグらせたりしたりしていました。
頑張ってネットで検索をかけていましたが、結局100分考えても答えは導き出せず、初めてのコンテストは残念な結果に終わりました。
溢れ出るやる気
初めてのコンテストを終えて、100分間かけて結局何もできなかった、ということ自体は非常に悲しかったですが、それよりも、楽しかったという思いが強かったです。
これは、何回も "RE" とか、 "WA" とか言われた時、次はACしてやるぞ、という気持ちが芽生えてきたからです。
とはいえ、同じミスを繰り返すのは流石に嫌です。次回のコンテストに向けて、APG4bをやることと過去問を解くことを繰り返しました。
私自身飽き性で、あまり物事は長続きしないタイプの人間ですが、1問も正解することができなかったのにやる気がふつふつと湧いてきたのは、競技プログラミングが自分に合っていたことと、競技プログラミングの面白さがあったからだと思います。
二回目の参加
ということで、経験を積んで生まれ変わった私は、一週間後のABC362に挑戦しました。
前回のABCで手こずったA問題でしたが、今回のABCでは10分程度で解くことができました。
たかだか一週間の頑張りですが、それが報われたことは以降のモチベーションにすごくつながったと思います。
続いてB問題。この回のB問題は幾何問題でした。
三角形の頂点の座標が与えられるので、それが直角三角形か判定せよ、という問題でした。
この問題は、いわゆる "三平方の定理の逆" を用いる問題で、要は、「ある辺の長さの2乗が、他の2辺の一辺ずつの長さの2乗の和と一致すれば直角三角形、出なければ直角三角形ではない」という判定を実装することが求められました。
当時の私にとって、この実装は簡単なようで難しかったです。
というのも、3点の(x,y)、つまり、6個の変数を正しく配置するのが難しかったです。
ただ、案外何とかなるもので、入力例に載っていた図をよく見て丁寧に実装することで、ACすることができました。
C問題は問題の意図の理解すらできずに終わりましたが、最終的に良い結果だったと思います。
茶色になるまでひたすら精進
1回目のコンテストで解けなかったものが2回目のコンテストではあっさり解けた経験がやる気のブースターになり、ますます競プロに打ちこんでいくことになります。
5回目のコンテストではC問題を解いて初めて茶パフォを取ることができ、そして8回目のコンテストでは何と緑パフォを取れました！
そうして11回目のコンテストで、見事入茶を達成しました！
茶色になるためには？
当たり前ですが、茶色になろうとしたら、茶パフォを取る必要があります。
そして茶パフォを取るためには、A,Bはもちろん、Cも解く必要が出てきます。
A・B を解くのに必要なこと
- 簡単なfor文が回せる
- 入力を適切に受け取ることができる
- 問題通りに愚直に実装する力
愚直に実装する、というのは、競プロ特有の言い回しを適切に理解し、それをそのままコードに落とし込むことを指しています。
例えば、文字列Sが与えられるので、複数回文字が現れているものは最初の1文字目以外消去してください、というものであれば、
S = input()
ans = ""
used = set() #すでに使ったものを保存する
for i in range(len(S)):
if S[i] not in used:
ans += S[i]
used.add(S[i])
print(ans)
として実装することができます。
このような書き方もすることができます。
from collections import OrderedDict
S = input()
print("".join(OrderedDict.fromkeys(S)))
ただ、あえて下の実装をする必要性は薄いです。
なぜなら、「知らないと解けない」からです。
もちろん競プロをする上で、知識が豊富であることは大きなメリットであり、強い武器です。というか、C、D以降は、そういう典型パターンを覚えることは必須でしょう。ただ、A、B問題を解く段階でそれを意識する必要はありません。
むしろ、問題文の通りに安全に実装できることの方が圧倒的に大事です。
問題文のまま実装するだけなので、大きなバグが発生しにくいからです。
C問題を解くのに必要なこと
- 問題を適切に読み取る
- 入力例と出力例を見て問題を整理する
AtCoderの入力例には、どうしてその出力になるのか、という部分がstep by step で示されていることが多いです。それを見て、問題を理解するということがとても大事です。
あるいは、出力例から何か法則を見出せることがあります。
例えば、グリッド変換問題だと、問題文を読むだけだとどうすれば良いかわからないようなものでも、入出力例を見てみると案外時計回りに回転させただけ、といったような問題だったりします。
普段は300点であることが多いですが、350点問題の時は大体アルゴリズムを使うことが必要になってくる系の問題であることが多いと感じるので、その時は頑張ってググりましょう。
入茶までにしたこと
AtCoder Problemsという過去問周回に便利な神サイトを使ってA、Bと解けそうな灰diff問題を解く。それだけ。
| 解いた問題 | 数 |
|---|---|
| 灰 | 311 |
| 茶 | 6 |
| 緑 | 4 |
| その他 | 92 |
覚えたアルゴリズム
特になし
強いていうならGrundy数
目指せ入緑！
入茶したことでまたさらにモチベーションアップ！！！！
ということで、茶色は何と2ヶ月程度で終わりました。
入茶した次のコンテスト(ABC374)で、D問題を爆速で解くことによって2041位を獲得し、初の水パフォを達成。レートは140も上がりました(笑)
そしてその後もちまちま増え続けて、ABC380で、18分でABCDを解き水パフォを獲得、レートも751に増え、緑が間近に迫ります。
そして12月7日。ABC383で、得意な約数問題を10分で解いたことでまたもや水パフォを獲得！ついに入緑することができました！
入緑に必要なこと
D問題を解くことが必須になってきます。
そして、 「早解き」 要素がとても大事になってきます。同じ得点でも、順位が全く異なることはよくあります。
例えば、ABC384では次のような結果になっています。
点数が1000点の人(ABCD4完想定)
| 内容 | 速い | 遅い |
|---|---|---|
| タイム | 6分15秒 | 186分14秒 |
| 順位 | 2846位 | 4467位 |
| パフォーマンス | 993 | 696 |
タイムが遅すぎると順位が下がってしまい、同じ4完でも差が出てきます。
タイムが遅くなる原因は、
- 実装力が足りない
- 間違いまくってペナルティをもらう
という2つの原因があります。どちらにせよ、典型的なパターンを使うことがD問題では多く見られるので、過去問演習をしましょう。
入緑までに取り組んだこと
- 鉄則本をする
鉄則本というのは、競プロのテクニックが詰まった書籍です。買いました。 - 過去問演習をする
例によってAtCoder Problems を用いて学習しました。
| 種類 | 入茶まで | 入緑まで |
|---|---|---|
| 灰 | 311 | 356 |
| 茶 | 6 | 16 |
| 緑 | 4 | 15 |
| 水 | 2 | 12 |
| 青 | 0 | 7 |
| その他 | 90 | 198 |
| 計 | 413 | 604 |
| TEE | 12203 | 30782 |
学んだアルゴリズム
- bit全探索
- 二分探索
- DFS
- BFS
- 動的計画法(区間DPを除く)
- 累積和
- 逆元
- heapqなどのデータ構造
- 素数系($O(\sqrt N)$ とかエラトステネスの篩とか)
入水に向けて
入水するためには、4完はマスト、5完も狙った方が良いぐらいのレベルだと感じているので、もっと考察力を鍛えたいです。
ダイクストラ法や、ダブリングなんかも習得したいです！
半年後には入水できているように頑張ろうと思います。
あとなぜかC問題のコードほぼ書いたのに最後の仕上げがめんどくさくなって先にB問題のAC取りに行ったりしてるので最後の仕上げをちゃんとやり切りたいです。
蟻本も持っていますが、今のところ内容が難しすぎて全く手を付けられていないので、早いところものにしたいです。
最後に
ここまでご覧いただきましてありがとうございました。
初めての投稿ということで拙い部分もたくさんあり、見てられるものではなかったかもしれませんが、指摘や意見などがございましたら是非コメントしていってください。
ありがとうございました。