ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
というのが基本ルールなんですが、DP強化週間第二弾ということで今週もこちらの問題を解いていきます。
(一応)今週のおすすめレート: 646
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
先週よりABCのパフォーマンス良かったはずなんだけど微妙に下がってるぅ…
やった問題
2022/07/24
Educational DP Contest: G - Longest Path
- 自力AC？ 🙅
- 所要時間: 1時間20分
多分O(N2)くらいなんじゃないかなっていう三重ループ(??)でやってみて3回くらいTLEしたので解説を読み始めたのが50分経過くらいのあたり。 メモ化再帰という方法を使うらしい。再帰で計算結果を都度配列に突っ込んで計算量を下げつつ探索していくスタイル。フィボナッチ数列を比較的常識的な実行時間の再帰で解きたいときの実装方法が多分イメージに近い気がする。 今回はDFSで解いたけど、トポロジカルソートはBFSでも解けるらしい、というかTLEしたコードはBFSだったし。どっちも計算量的にはO(N+M)らしいので、BFSでもちゃんと書けたら通るのかしら。
ちなみに前に解いた茶色アッパーの類題だと始点が1つ目のノードに固定されているのでもうちょっと気楽に解けるやつ。
2022/07/25
Educational DP Contest: H - Grid 1
- 自力AC？ 🙆
- 所要時間: 10分
DPシリーズでやっとまともに自力解答できた気がする。
単純な碁盤の目状の道の最短経路数を求めさせる問題は高校数学でよくあるやつで、で出せるんだけど今回は経路上の不定位置に壁がある(かもしれない)ということでDPしていく。
とにかく右か下に移動していってゴールにたどり着けば最短経路のどれかに当てはまるので、dp[i][j] = dp[i-1][j] + dp[i][j-1]で左上から右下に粛々とループを回していけばdp[h][g]が答えになる。
余談だけどかの有名なフカシギおねえさんの問題は似てるけど最短経路ではないのね。
2022/07/26
Educational DP Contest: I - Coins
- 自力AC？ 🙆
- 所要時間: 1時間10分
やっぱり縦軸と横軸の取り方で微妙に悩んでしまった、が、今までと比べたら圧倒的に順調に決められたのでその辺は成長だと思いたい。ただしそのあと「表の個数が裏の個数を上回る確率」を回答するところで過半数ぴったりの値を出し続けて何がおかしいんだろうと悩み、結局1時間強でAC。問題よく読むんだ私。ちゃんと情報の整理が出来れば次からはもっとスムーズに解けるはず、きっと。 今回はj=0の列も地味にちゃんと計算しないとダメだったりする。
解説コードを見るとどっちも概ねn2の二次元配列をDP用に組んでいたけど、実はn2までいらなくて、n*(n/2)まで求められれば1 - dp[n][0..n/2].sumで出せるはず。この感想書きながら気付いたので、ACコードではもう少しややこしいことしてるけど。
2022/07/27
Educational DP Contest: J - Sushi
- 自力AC？ 🙅
- 所要時間: 1時間10分
解説を読み始めたのが27分経過時点。
とても読みやすいRubyのACコードを参考にさせてもらったものの、ほぼ写経でACした時点では正直まだよく分かってない。
dp[i][j][k]に3個の皿がi枚・2個の皿がj枚・1個の皿がk枚あるときの期待値が入っているのは分かる。最初に読んだ解説の漸化式(？)を読んで(x個乗ってる皿を引く確率) * (x個乗ってる皿が1枚減った場合の期待値)を足し合わせていくのも分かるんだけど、1って何よ1って、となっている。最低1回は試行しないとダメってことなのかしら、ということで強引に納得しようとはしている。
多分イメージとしてはこっちの解説みたいな感じで、おそらく私の書いたACコードもこっちの読み方ベースなんだと思う。
(現在の状態から1回寿司を食べるまでの試行回数の期待値) + (1個の皿から食べたケース以降の部分期待値) * (寿司が残っている皿を引いたとして、1個の皿を引く確率) + (2個の皿から食べたケース以降の部分期待値) * (寿司が残っている皿を引いたとして、2個の皿を引く確率) + (3個の皿から食べたケース以降の部分期待値) * (寿司が残っている皿を引いたとして、3個の皿を引く確率)
「確率の事象が発生するまでの試行回数の期待値が
である」というのは地味に覚えていた方がいい、というか条件付き期待値って高校数学レベルではあるらしいんだけど、それなら絶対やってるはずなのにサイコロの出目の期待値計算くらいしか記憶にない……
2022/07/28
Educational DP Contest: K - Stones
- 自力AC？ 🙅
- 所要時間: 25分
なんか類題っぽいの*2見たことあるなーって思いながら5分くらいで断念して解説を読む。考えないといけない山は1つなので、さすがにこの類題よりはだいぶシンプルだし、あっちは解説読んだら全然違う解き方してた。16行のコードになったので分かっていれば秒で解けるんだろうなー 一次元のDPっぽい感じで解いていく。「残り1個の状態で先手の手番が回ってきたときに勝つ手が存在するか？」「残り2個の状態で(以下略)」…みたいなのを延々とKまで繰り返すような感じ。「最適に行動する」という条件があるので、1つでも確実に負けに追い込める手が存在すればOKらしい。
ところで競プロの解説でよくあるフレーズとして「DPするだけ」みたいなのがあるらしいんだけど、確かに出来上がってみるとそういうコードになるんだけど、どうDPするのか考えるのが一番難しくない？ってよく思ってる。
2022/07/29
Educational DP Contest: L - Deque
- 自力AC？ 🙅
- 所要時間: 31分
ここまでが基本問題らしいので、今回でDPシリーズ最終日、さすがにちょっと疲れた。 22分ほど経過したところで解説を読み、その後9分くらいでAC。メモ化再帰かー。
素直なループのDPで片付けられるパターンと、メモ化再帰が必要なパターンと、いまいち区別がついてない気がする。ただ、今回はどう走査するかが不定なので、そういう時は再帰向けではあるんだろうなぁとは思っている。単純に端の値だけを見ればいいというものではないのは分かってたものの、損得判断をどうしたらいいのかで悩む。まぁ、先の判断を保留(？)すればいいっていうのが再帰のいいところなんだけども。
2022/07/30
ABCが日曜日なのでやろうと思ったんですが、眠すぎて無理でした！