いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Beginner ContestのD問題はいいぞ

この記事は「Competitive Programming (1) Advent Calendar 2018 - Adventar」の21日目の記事です.

ちなみに去年は連続ACを8ヶ月続けた事について書きました.
ratea.hatenablog.com
想定読者はAtCoder緑上位~水色くらいです.
それより上の人は多分つまらないですごめんなさい.

[目次]

大学院進学とともに競技プログラミングをはじめました,1年と8ヶ月くらいになります.
永遠に水色ですどうもありがとうございました.
f:id:ratetion:20181206012529p:plain
shichinomiya - AtCoder
個人的に速解きだけで水色まで上がったけどあまり学習しなかったのでそこで停滞してしまったという印象があります.
ABCもまあまあ埋めました(全部じゃないんかい)
f:id:ratetion:20181206021404p:plain


経緯

CODE FESTIVAL2018に向けて精進していた時によく解いていたのがAtCoder Beginner ContestのD問題でした,特に昔の物をよく解きました.
解いていて感じた事として,よく名前を聞くが,問題を解いた事がなかったり,実装経験がないアルゴリズムやデータ構造が出題されている事が多いように思いました.

これはどうでもいいんですが以前Yazaten氏に
「らてあ君って意外とレートの割にアルゴリズムとか知らないよね」
みたいなことを言われました(要出典)
何から学んでいいかわからないという僕のような人は特にABCのD問題を埋めていくことをお勧めします.
実際のところ,自分がちょうど解けるかどうかの問題を解くのが成長につながると思うので.

おすすめ問題

全部です.

すいません嘘です,優先的に解くべきだと僕が感じるものを偏見で列挙するので上の内容に共感した人は是非解いてください.
ネタバレになるので白文字で感想を書いておきます.
あくまで感想なのであてにはしないでください.
解説開きたくないけどヒント欲しい時に役に立つ可能性もあります.

D - マーブル
難しい,DPにこういう使い方もあるんだなぁという感じ,こういうややこしい問題もしっかり考えればDPで解決できちゃうのはいい知見っぽそう

D - おいしいたこ焼きの焼き方
DPでも累積和でも,まあよく見ると思う

D - トランプ挿入ソート
こういうのを知らないから驚かれたりするんだろうか,最長増加部分列

D - 禁止された数字
桁DP,君もpekempey先生の記事で桁DP入門しよう!https://pekempey.hatenablog.com/entry/2015/12/09/000603

D - 金塊ゲーム
これめっちゃ難しいと思う,強い気持ちでしっかり詰めたDPを書いて圧倒的成長

D - 浮気予防
蟻本を開いてフローに入門しよう

D - 阿弥陀
これ賢い,ダブリングってすげえと思う

D - 閉路
ダブリングを出した次の回でLCAを出すとか教育的すぎると思いませんか?

D - 高橋くんの苦悩
DPに慣れてきたな〜って思うと解けたい

D - 食塩水
これは誰もが通る道だと信じたいとても辛い教育的だと思う

D - トレジャーハント
最近似た問題が出たんだけど僕は解けなかったけどみんなド典型って言ってて辛かったよ

D - 塗り絵
木DP,ちょっと捻らないとダメな気持ちになるんだけど解説曰く簡単らしい

D - プレゼント
これもめっちゃ解く価値があると思った,あと蛍光灯とか似てる

D - 道路の老朽化対策について
UFを貼ると通る,僕は最小全域木でUFを学んだんですがこれで入門するのもいいんでしょう

D - 徒競走
トポロジカルソートのbitDPのなんかややこしい感じなので整理して頑張りたいやつ

D - 井井井 / ###
なんか似たような問題よく出るような印象ある

D - Built?
最小全域木を生やす

終わりに

ハァハァ...今日のところはこの辺にしといてやるよ...
いやまあここであげてないD問題も全部価値あると思うんでそのうち僕も全部埋めます.
個人的にですが,昔の方が教育的な問題が多いようには感じます.
CODE FESTIVALにこそ行けなかったものの,CODE THANKS FESTIVALでは上であげた問題に似た問題が2問は出て両方解けたので,かなり精進してよかったと思ってます,パーカーこそ得れませんでしたが.

明日はnotさんの「JAGの作問環境」です.
かなりの量を作問されてるので†楽しみ†ですね.