Educational DP Contest / DP まとめコンテスト
- masashinakata
- 21359
- 7
- 2
- 0
サーバル「DPの表をじっと見つめると、斜めに潰して1次元にできることがわかるから、最初に説明したのと同じDPができるよ。 私にはこっちの方が難しく感じるけど、この「斜めに潰す」って考え方はDPでは結構よく出てくるから、覚えておくといいかも」 pic.twitter.com/OayFViN3PW
2019-01-05 11:13:56サーバル「競技プログラミングが強い子ってことだよね。多分一番強いのはフェネックだけど、フェネックはアライさんと一緒にいつも動き回ってるから会うのは大変かも。他だと博士と助手とか・・・ 続きは質問箱へ #peing #質問箱 peing.net/ja/qs/122935635
2019-01-05 11:18:49トキ「TDPC M『家』を解いたわ。「同じフロアの部屋iから部屋jに移動する方法は何通りか?」をbitDPで求める前半パートが本質で、後半は行列累乗すればいいわね」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-05 12:59:35カラカル「TDPC G『辞書順』を解いたわ。「辞書順は貪欲」という言葉を思い出すと、「各文字から始まる部分文字列は何個あるか?」が分かっていれば1文字目を決められて、その文字以降で同じ問題を考えると2文字目がわかって……という感じで求めることができるわね。つまり、」
2019-01-06 00:39:03カラカル「dp[i][j]=(Sのi文字目以降の部分列で、先頭がjであるものの個数) が求まればいいわ。これはiの降順で考えるとO(26|S|)のDPで求められるわね。そのまま計算するとO(2^n)くらい?の大きな値になっちゃうから、K以上の値はKに丸める必要があることに注意が必要よ」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-06 00:39:04カラカル「実装上は、「部分列として空文字列も認める」「終端文字'\0'を'a'より小さい文字として扱う」という2つの工夫をすると少し見通しがよくなるわ」 pic.twitter.com/Od4T2SHXjm
2019-01-06 00:39:04解くべき問題が2問と残っている課題が複数とDPまとめコンと本を読むとゲームをやるとTweetDeckをするをしなければいけない
2019-01-06 17:52:01