SRM514 Div1 Hard
-
- いいね！0
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai ありがとうございます! さっそくお願いします! 主に dp[] の定義以降のメインっぽい部分と memo[] の中身の意味について教えてください。 http://t.co/kjVw91H
2011-08-11 23:23:54
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Da__Long あーいっ メモは単純に、bitの立ってる数が奇数かどうかをやってるだけｗ メインループは、うーん、凄く書き直したい・・・ｗ 簡単に言うと、各行の偶奇未確定な部分に対して、偶奇を全通り試して、更新してあげてるだけだよー
2011-08-11 23:33:16
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai ありがとうございます。そこまでは私の考えた方法と同じなのですが、ナイーブに書くと 2^100 もしくは 2^81 になってしまいます。どこを工夫してどれくらいのオーダーにできたのかが知りたいのです。
2011-08-11 23:41:24
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Da__Long えーっと、2^100は多分全探査ですよねー それだったら、それを纏めてあげればおｋです ii列目が終わった後に、各列が奇数になってるか偶数になってるかをbitで表現してあげて、その個数をメモってあげればおわり！
2011-08-12 00:11:55
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai iiという変数はi列目のビット表現のように見えますが、i=0列目から順に埋めていると読んで正しいでしょうか。また、もしそうなら、0列目の埋め方として考えられるいくつかの方法に対して1列目の埋め方は決定的でも独立でもないと思いますが、どのように数えていますか?
2011-08-12 00:31:33
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Da__Long あとの計算は、「i行目までの和で、各列が奇数になってるか偶数になってるかのbit表現」のみに依存するので、そこで纏めちゃってます。 うーん、どう説明するのがいいんだろう 正直ちゃんとしたコードに書き直した方が判りやすい気がします＞＜
2011-08-12 00:34:34
大堀龍一 (Ryuichi OHORI)
@__DaLong
わかったことは自分の言葉でメモ。dp(i,y) := (i列目までの埋め方であってj行目までの部分和の最下位ビットを並べたものがyになるものの総数) = Σ [y = p xor q] dp(i-1,p) 埋め方 (i,q)
2011-08-12 00:44:41
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai ということで、私は今ツイートしたような感じで普通に漸化式だけ書いていただければそれが正しいことはすぐ理解します。思考過程までたどるのはすこし大変ですが。
2011-08-12 00:46:52
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Da__Long はーいｗ 自分はDPを漸化式にする習慣がないので、数学的表現にしようとすると手間取っちゃうタイプだからちょっと困ってましたｗ
2011-08-12 00:48:53
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Da__Long ちなみに、おまけでもう１個 これだと計算量がO(n*2^2m)とかですが、これを１個ずつにしてあげると、状態数が、「列ごとの偶奇」に加えて、「今の行の偶奇」の２通りが増えて、計算量がO(n*m*2^m)くらいまで落ちます
2011-08-12 00:52:26
大堀龍一 (Ryuichi OHORI)
@__DaLong
とはいえ、方針がわかっているのに Local Test は10回以上、System Test を4回くらい走らせてやっと Pass した。バグ量産しすぎ。(1) 先に . が出てきてから偶奇がわかるものをカウントしていなかった。(2) 1<<n から1を引き忘れた。
2011-08-12 13:59:17
大堀龍一 (Ryuichi OHORI)
@__DaLong
(3) 行方向の和が奇数になることをチェックし忘れた。(4) 漸化式のインデクスをずらして書いてしまった。(5) 1か所で Mod を取り忘れオーバーフロー。(6) 累乗を50までしか用意していなかった。(7) 切り捨て除算 \ と 除算 / とを間違えた。
2011-08-12 14:01:53
大堀龍一 (Ryuichi OHORI)
@__DaLong
(8) 変数名を書き間違えた。(9) 立っているビットが奇数になるものを列挙する際にビットシフトを忘れた。
2011-08-12 14:02:48