Educational DP Contest / DP まとめコンテスト

Educational DP Contest / DP まとめコンテスト - AtCoder: https://atcoder.jp/contests/dp Typical DP Contest - Togetter(2013年8月に開催されたコンテストのまとめです): 続きを読む
5
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
なるわい / Lithium @Lilies_lit

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
競技プログラミングをするフレンズ @kyopro_friends

サーバル「日程は調整中みたい!ごめんね!」

2019-01-04 17:53:34
はむこ@ジャバ @hamko_intel

@ompugao りまいんだ:あしたは26問DPコンテストがあります atcoder.jp/contests/dp

2019-01-04 18:00:20
○○() @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でもちゃんと成立することに気付くまで30分くらいかかった(頭が悪すぎる(代数的構造を学べ))

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
残りを読む(1762)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?