Educational DP Contest / DP まとめコンテスト
-
masashinakata
- 20709
- 7
- 2
- 0
-
- いいね！0
kakiraちゃん
@kakira9618
DPまとめコン atcoder.jp/contests/dp TDPC との違い: 当コンテストはより典型的で簡単な問題が出題されます。 難易度の目安は、序盤は 200 点ほど、終盤は 800 点ほどです。
2018-12-18 13:14:52
すぎむ
@sugim48
1/5 (土) 20:00 - 25:00 に開催予定の DP まとめコンテスト (atcoder.jp/contests/dp) ですが、1/5 (土) 25:30 - に Codeforces のコンテストが生えたので、1/6 (日) 20:00 - 25:00 への移動を検討しています。ぜひアンケートにご協力ください。
2019-01-04 13:45:18
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「明日は20時からDPまとめコンテストがあるよ！DPの練習向けに、初心者～中級者向けの問題が出題されるみたい。私たちも参加する予定だよ！」
2019-01-04 16:39:39
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「明日のDPまとめコンテストの練習に、TDPCの問題を解いてみて、2時間半くらいでABCDEJTの7完だったよ。難しいね……」
2019-01-04 16:41:33
NaruY a.k.a. Azuki🐬💫
@azuki774s
DP まとめコンテスト / Educational DP Contest - AtCoder atcoder.jp/contests/dp 過去問でしばこ
2019-01-04 16:44:52
競技プログラミングをするフレンズ
@kyopro_friends
TDPC A『コンテスト』 アライさん「これは基本中の基本のナップサックDPなのだ！やるだけなのだ！」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:46:07
競技プログラミングをするフレンズ
@kyopro_friends
TDPC B『ゲーム』 ルル「これはDPじゃなくて、メモ化再帰で解いたよ。"ゲーム"の基本的な問題だけど、ちょっと実装に手間取っちゃった」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:46:44
競技プログラミングをするフレンズ
@kyopro_friends
TDPC C『トーナメント』 サーバル「dp[i][j]=(iラウンド終了時点でjが勝ち上がっている確率) っていうDPを考えると解けるよ！状態遷移は「dp[i+1][j]=Σdp[i][j]*dp[i][x]」で、シグマは「(i+1)ラウンド目でjと戦う可能性がある全てのプレイヤーx」を走るよ！」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:49:03
競技プログラミングをするフレンズ
@kyopro_friends
TDPC D『サイコロ』 トキ「2,3,5がそれぞれ何回登場するかを覚えておけばいいわね。100回連続4がでると2は200回になる可能性があるけど、Dには高々60回しか登場しないから、それ以上は全部60にまとめちゃっていいわね。3と5も同様よ」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:51:30
競技プログラミングをするフレンズ
@kyopro_friends
TDPC E『数』 シロサイ「桁DPの典型ですわ。「考えている数がNより小さいか？」というフラグを持つ必要があるのは、初めてだと思いつかないかもしれませんが、よくあるテクニックですの」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:54:10
競技プログラミングをするフレンズ
@kyopro_friends
TDPC J『ボール』 ギンギツネ「bitDP+確率DPって感じかしら？自己ループを含む簡単な例ね。これもB問題と同じで「ゲームの進行によってものが減っていく」ような問題だから、メモ化再帰の方がイメージしやすかったわね」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 16:57:23
競技プログラミングをするフレンズ
@kyopro_friends
TDPC T『フィボナッチ』 フェネック「やー、きたまさ法で解いたけど、TL2secのところをC言語で1029msかかってるから、想定解は高速きたまさ法なのかもねー。ちなみに、そっちは実装したことないねー」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-04 17:00:00
競技プログラミングをするフレンズ
@kyopro_friends
誤：Σdp[i][j]*dp[i][x] 正：Σdp[i][j]*dp[i][x]*(jとxが戦ってjが勝つ確率)
2019-01-04 17:09:32
roimu
@youthfuldays072
@kyopro_friends コドフォと被るから日曜日にするかもって主催の人のツイートみましたけど、土曜日に確定したんですか？
2019-01-04 17:46:38
○○()
@ksomemo
“日時: 2019-01-05(土) 20:00-25:00 JST 時間: 5 時間 問題数: 26 配点: 各 100 点 レート変化: なし” atcoder.jp/contests/tdpc との違い: 当コンテストはより典… htn.to/mzCrZTKk
2019-01-04 20:56:43
chokudai(高橋 直大)🍆
@chokudai
D問題、A/B + C/D が、AD+BC / BD で表せるテクが、modでもちゃんと成立することに気付くまで３０分くらいかかった（頭が悪すぎる（代数的構造を学べ））
2019-01-05 02:49:18
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「TDPC F『準急』を解いたよ！「j駅連続で止まってる」のは「最後に通過したのがj駅前」と同じだから dp[i]=(駅iを通過する場合の数) みたいな感じでうまくいかないかなーって見当をつけてみる（※）と、
2019-01-05 11:12:03
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「 dp[i]=Σ(最後に通過したのが駅jである場合の数)=Σdp[j] (i-k≦j<i) でうまく計算できるよ。 dp[i]の累積和を持っておけば遷移はO(1)でできて、求める答えはDP遷移と同じように考えてΣdp[j] (N-k<j<N)だからO(N)で求められるね」 tdpc.contest.atcoder.jp/submissions/39…
2019-01-05 11:12:03
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「類題は、これよりちょっと難しいけどCODE FESTIVAL 2018 qual A D『通勤』とかかな？」
2019-01-05 11:12:04
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「「見当をつける」とか「思いつく」っていうことをしなくてすむ方法も一応紹介しておくね。 まず計算量を考えなければ dp[i][j]=(駅iの時点でj連続で止まっているような場合の数) というDPがすぐ思いつくね！ もちろんこれは状態数がO(NK)だからこのままじゃ無理なんだけど、」
2019-01-05 11:13:55