-
masashinakata
- 2328
- 0
- 0
- 0
-
- いいね！0
agw
@masashinakata
@hogeover30 Advent Calendarで作図しまくります! ARC006 Cも超良問だったので盛り込みたいです
2013-11-05 16:03:26
agw
@masashinakata
@hogeover30 ごめんなさい。大きく出てしまいました。恐らくいつもの作図と変わらないです ((((；ﾟДﾟ))))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ
2013-11-05 16:08:57
大堀龍一 (Ryuichi OHORI)
@__DaLong
@teporz 各くじに対し、それを最初に引いたときの現在のコレクションからコンプリートまでの (最適戦略下) コスト期待値を変数とし、コレクションが現在より多い場合の期待値がわかっているとした一次方程式を立てます。条件つき期待値のあたりは注意していないとはまりそうです。
2013-11-05 22:29:44
大堀龍一 (Ryuichi OHORI)
@__DaLong
C問題は解けたのに解説を読んでもわからない…… RT @chokudai: AtCoder Regular Contest 016、解説アップロードしました! http://t.co/JTNgwXmjhq
2013-11-05 22:38:22
大堀龍一 (Ryuichi OHORI)
@__DaLong
@teporz 公式の解説を読んでもわからなかったので気が向いたら書くかもしれません (忘れそう)
2013-11-05 22:50:57
大堀龍一 (Ryuichi OHORI)
@__DaLong
ARC016C の解法である bitDP の概念は知っていたが名前は最近まで知らなかった。固定された可算集合の有限部分集合を自然数にエンコードすることと DP とを組み合わせただけなら、仰々しい名前なんてつけない方がいいと思うけど。
2013-11-05 22:56:52
大堀龍一 (Ryuichi OHORI)
@__DaLong
@teporz うーん、なぜ両回答ともに「特定の1つを当てるまでにかかる回数の期待値」を既知としているのでしょう。そのままコードにすると、余分な場合分けを作り出してしまいます。素直に一般の場合で一次方程式を書きたいですね。
2013-11-05 23:03:02
chokudai(高橋 直大)🍆@AtCoder社長
@chokudai
@__DaLong 今回は使わないけど、for(int j=i; j>0; j= ((j-1)&i))みたいな感じで参照するパターンとかあるから、なんか名前ついてた方が色々テクニックとして覚えやすい印象。まぁそれ言うなら桁DPとかも桁ごとにやってるだけで本質的に同じやんとか色々
2013-11-05 23:03:49
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai 「どうやって解くの?」「bitDP です」「ふえぇ、そんなの知らないよう……」より「どうやって解くの?」「あなたも知ってる DP ですよ」「集合を添字にしなきゃいけないよ?」「自然数で集合を表せます」の方が学習者にとって有益だと思うのです。
2013-11-05 23:12:48
chokudai(高橋 直大)🍆@AtCoder社長
@chokudai
@nijinoryu for(j = 1; j < N+1; j++){ってあるんですが、jがN==100まで行くのに対し、string x[9][100];で、0-99までしかないので、長さ100の入力が与えられた時に配列外参照してそうですねー・・・。
2013-11-05 23:12:50