Dark

6ヶ月停滞したけどAtCoderで水色になりました!

はじめに

くさころ(@9sako6)です。

2020年3月1日のAtCoder Beginner Contest 157水色になりました!学生のうちにAtCoder水色に届いてよかったです。これまで競プロの質問に答えてくださった皆様、祝ってくださった皆様、ありがとうございます。

私は2019年5月末に緑になってから約9ヶ月間水色になれませんでした。
タイトルにある通り、1100を超えてからは約6ヶ月間停滞しました。
本記事は、緑で停滞した後に水色になった人間の事例を紹介するものです。緑で停滞している方に何らかの示唆を提供できるかもしれません。

本題に入る前に一つ、デカルトさんの言葉を借りて前置きです。

けれども、この書は一つの話として、あるいは、一つの寓話といってもよいが、そういうものとしてだけお見せするのであり、そこには真似てよい手本とともに、従わないほうがよい例も数多くみられるだろう。そのようにお見せしてわたしが期待するのは、この書がだれにも無害で、しかも人によっては有益であり、またすべての人が私のこの率直さをよしとしてくれることである。 (デカルト(著), 谷川多佳子(訳). 方法序説. 岩波書店, 1997. p.11より)

水色までの軌跡

某年、名古屋大学を卒業しました。その後同大学の大学院に入ってから競技プログラミングを始めました。

名大に在籍しているものの、数学的素養は無です。そもそも数学に対する興味が低めです。おつり計算を間違えたり、三角関数の微分を忘れたりしたことがあります。一方、プログラミングは好きです。RubyとC++の両刀で戦っています。

あと、名大にはプロコンサークルがあります(名大プロコンサークルについて)。私はたまに顔を出して精進していました。後輩くん達はぐんぐんレートを伸ばしていました。みんな頑張っていてえらいです。

レート

以下がレートの遷移です。プログラムは書けたので、茶色になるのに苦労はしませんでした。
その後は旧ABC-Cをメインに精進しつつ、緑色になりました。しかし、ここから約9ヶ月、1100をこえてから約6ヶ月間水色になれませんでした。原因は後にも書くのですが、新ABC-Eの打率が低すぎたことだと思っています。

rating_mizuironatta

精進グラフは水色中盤です。普通くらいの量かもしれません[要出典]。(AtCoder Scoresより)

syojin_graph_mizuiro

わには消えました。

パフォーマンス

最近は水パフォ前半で安定してきました。しかし、青パフォ以上を一度もとったことがありません。

contests_history

atcoder_chart_mizuiro

AtCoder Chartsより)

解いた問題数

AtCoderで解いた問題数は748問です。ABCのCまで埋めました。

problems_circle_charts

AtCoder Problemsより)

他のサイトも入れると800問ちょっと解いているようです。

toita_mondaisuu

Rating Historyより)

ABCにおける打率

新ABC(ABC126以降)において、各問題をどのくらいの割合で通せたかを示します。
Cまではほぼ解けています。解けていると思っていたDは6割しか解けていませんでした。ショックです。Eに至っては約1割しか解けていません。いつもFは問題を読みに行く暇さえありません。

問題 割合
A 23/23 (100%)
B 23/23 (100%)
C 22/23 (96%)
D 14/23 (60%)
E 3 / 23 (13%)
F 0 / 23 (0%)

本番中に解けた水Difficulty以上の問題は、なんとたったの2問でした。基本的に早解きをして水パフォを稼いでいるようです。本当にこのくさころくんは水色でいいんでしょうか。

緑で停滞する原因

「参加者の2割弱くらいが通せる問題」を通せる割合が低いのが原因だと思います。「参加者の2割弱くらいが通せる問題」は、だいたいEくらいを想定しています。Eまで解ければだいたい水中盤以上のパフォは出ます[要出典]。しかし、Eが解けず、Dまで解けるだけでは水パフォが限界です[要出典]。

私は基本的にDまで解いてレートを停滞させつつ、たまにEを解くまぐれ戦法で水色に上がったというわけです。これは本質的でも効率的でもありませんね。

どうすればEを通せるようになるか

わかりません。教えて欲しいです。
過去のE問題で問われた知識はおおよそ以下のものです。

  • BFS, DFS
  • 工夫して全探索
  • 二項係数(というか、数え上げが多め)
  • 素因数分解
  • 最大公約数
  • XOR
  • 二分探索
  • 累積和(二次元累積和)
  • 桁DP
  • ナップサックDP
  • その他DP
  • LIS
  • セグメント木
  • Union-Find木
  • ワーシャルフロイド法
  • ベルマンフォード法
  • Z-Algorithm

結構多く感じるのですが、蟻本中級までにほとんど載っていました。
ということは順当に考えて、E問題を解けるようになるためには、「蟻本中級までを頭に入れて、問題演習を積んで慣れる」に尽きるでしょう。とりあえず私は今後以下の精進をするつもりです。

おわりに

次は青を目指します!!!

Share:
記事一覧
Dark