AtCorder、先週から参戦するつもりだったのですが、土曜日は予定があったので、できませんでした。
AtCorderって、土曜日にやる場合と日曜日にやる場合があるんですね。知りませんでした・・・💧 AtCorderやっていこうと思ったときが日曜日にやっていたので、てっきり毎週日曜日にやるものだと思っていました。
というわけで、また今週も自習することにします。
ABC248
問題はこちら
https://atcoder.jp/contests/abc248
私はPythonでやっているため、解説は公式よりこちらを毎度、参照しています。(本当にこの人すごい、何者なんだろ。。。)
https://qiita.com/u2dayo/items/f695270c45edbe0a2734
やってみて
A,Bは問題なし。C以降は解けず。E以降は見ていない。
Cは、何やって良いのかまったく分からず。ほとんど何も書けませんでした。
Dは、これ絶対タイムアウトになるだろうなと思いながら、そのまま実装。案の定、TLEの嵐でした・・・
色別の正解率
目標としている水色とその手前の緑色の正解率は、
緑色 - C: 74.7％ D: 74.6％
水色 - C: 94.5％ D: 93.2％
らしいです。
やはり、解けないといけない問題のようですね。
解説を見て
C
Cは、DP(動的計画法)というものを使うみたいですね。動的計画法は、ああ、何か聞いたことがあるというレベルで、何もわかっていないです。
最短経路問題とかで使うんだろうなというイメージがありましたが、こういった数列系の問題でも使うことがあるんですね。
今読んでいる本『新・明解 Pythonで学ぶアルゴリズムとデータ構造』でDPを勉強しようと思ったのですが、載っていませんでした。この本は、図や説明の多さや難度が私にとってはマッチしていてわかりやすいのですが、競技プログラミングに特化しているわけではないようなので、こういったことがあるみたいですね。
というわけで、サイトで勉強することにします。この辺が良さそうな気がしています。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
https://qiita.com/keisuke-ota/items/504d66092671a67c1040
D
Dも、解説コードを見ても何やっているのがよく分からずです。
二分探索というものを使うようですね。こちらは、『新・明解 Pythonで学ぶアルゴリズムとデータ構造』のありました。本書の一番最後に掲載されています。この本は、難易度順に載っているようなのですが、D問題で最後に登場するようなアルゴリズムが必要なのかと思いました。
本書はとりあえず早く読破して、競プロレベルの本に移行する必要がありそうですね。
まとめ・感想
競プロの茨の道感がすごいですね。参戦前ですでに挫折しそうです。
競プロって、少なくともDレベルぐらいまでは、数学の受験勉強に似てるなと思いました。基本的な考えや公式を詰め込んで、あとはそれを応用した問題をひたすらやって、慣れていくしかないって感じがします。
