ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
……と思ったんだけど、あまりにもDPへの苦手意識が強いので、当面は基本的なDPの問題をたくさん集めたコンテストの問題を上から順に、とりあえず基本編の終わりくらいまでは解いてみようと思います。基本編までで12問あるので、多分2週間くらいこれかな？
(一応)今週のおすすめレート: 650
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
やった問題
2022/07/17
ABCだったのでお休みにしようと思ったんだけど、ABCの結果があまりにあんまりだったので。
Educational DP Contest: A - Frog 1
- 自力AC？ 🙆
- 所要時間: 50分
分かってみれば解法はほぼフィボナッチ数列スタイル。再帰で解いてTLEになったり二次元配列で管理しようとして持て余したり、さっそく迷走気味。 当日のABC260Cと合わせて、「イメージ図がちゃんと描けない問題が解けると思ってはいけない」という言葉を胸に刻みたい。
2022/07/18
Educational DP Contest: B - Frog 2
- 自力AC？ 🙅
- 所要時間: 多分40分くらい
昨日の問題のバリエーション。初回でWA食らって直しどころが全く分からず他の人のACコードを読んだら配列に詰めておく初期値が小さすぎたというオチ。素直にFloat::INFINITYとかにしておけばよかった。切ない。
そこ以外は全く直すポイントがなく、これ本番でやらかしてたらその日じゅう立ち直れない気がする。
2022/07/19
Educational DP Contest: C - Vacation
- 自力AC？ 🙅
- 所要時間: 22分
再帰かな？などと10分くらい悩んだあと、解説を読んで分かってみるとなんともシンプルではある。
直近の日にAを選んだときの最適解は必ず 直近のA + 前の日にBを選んだときの最適解か直近のA + 前の日にCを選んだときの最適解 のどっちかなので、同じ理屈で三択全部に対して計算し続けるイメージ。後は最終日ぶんの計算結果のうち、一番大きな値を返せばよい。
選択肢を一つに絞るのは最後まで保留してもいい、ということを学ぶのにいい問題でした。
2022/07/20
Educational DP Contest: D - Knapsack 1
- 自力AC？ 🙅
- 所要時間: 45分
ナップサック問題キターーーーー！
ということで典型的なというか、基本のナップサック問題らしい。
また安易に再帰使ってTLEを起こし、わけわからんと思って解説を読み漁ってなんとかAC。 このタイミングではまだピンと来ていなかったので、プログラムの挙動を追って表を埋めていってやっと何となく理解した感じ。これは何回か類題を解かないと身体にしみこまないやつだなー
2022/07/21
Educational DP Contest: E - Knapsack 2
- 自力AC？ 🙅
- 所要時間: 1時間34分(最初測り忘れたので解説を読んでからの時間)
数値的な制約以外は完全に昨日の問題と一緒だよね？と思いつつ、とりあえず昨日の解答をソラで書けるかの確認がてら、昨日のコードまんまではACしないことを確認。多分ここまで20分くらいというか、少なくとも計測を忘れていた時間が無視できるくらいにはこの後手こずった。思いついた手を2、3試してみてダメかーってなってわりとさっさと解説読んだはずなんだけども……
さて、結局どうなったかと言うと昨日と探索の軸をひっくり返すというか、「所定の重量までで一番高い価値」を探していた処理を「所定の価値ぴったりの組み合わせで一番重量が軽いもの」の探索に差し替える感じ。変に混乱してしまって苦労した。最終的にはとりあえず値の範囲を全部解説と同じにしてようやくサンプルの出力が合ったので提出したらAC、という感じ。見た感じ、おそらく0-basedと1-basedのインデックスがごっちゃになってたと思われる……
解説記事曰くここまでが入門編とのこと。明日から大丈夫かな…？
2022/07/22
Educational DP Contest: F - LCS
- 自力AC？ 🙅
- 所要時間: 2時間34分
全然大丈夫じゃなかった。前に類題で撃沈した、というか解説を読んでもよく分からなかった記憶のあるLCS(Longest-common subsequence、最長共通部分列)の問題。 正直初めてこの手の問題に出会ったとき「共通部分列？共通部分文字列じゃなくて？」って思ってたんだけど、diffとかでも使う古典的な問題だって聞くと、このアルゴリズムの実用性という観点でもわりと納得感が出てくる現金さ。いつもお世話になってます、diffなしでは仕事できません！！！
最初の探索の仕方としては概ねナップサック問題の類題と言っていい感じ。 出来上がった探索結果で最長文字数を答えるだけなら簡単なんだけど、そこから文字列を起こすのに難儀してしまった。ゴチャゴチャ書いた最初の提出に比べて解説ACしたコードのシンプルさたるや……
2時間うんうん悩んで結構キツかったし問題解く前に読んだ水色指南の記事で「茶色や緑色の人にはちょっと難しめかも」って書いてあって瞬間最大風速*2でようやく緑な灰色の私は怯んだものの、やっといてよかった気持ち。 ちなみに類題の難易度をAtCoder Problemsで見たらアッパーとは言え茶色(779)でマジか、ってなりました。とは言え茶-緑ボーダー上の人が正解率50%って考えるとそんなもんなのかも。
