SRM 653

有為 @uwitenpen

複数状態のときに損失辺のどれかは0になるけど複数辺で最小カットになりうるのどう解釈すればいいんだろうなあ

有為 @uwitenpen

@skyaozora 下のグラフ、真ん中の状態に無限のコストをかけることで、真ん中の状態が絶対に選ばれないようにしているように見えますけど、これ上と結果違うんです？

有為 @uwitenpen

@nico_shindannin でも制約辺がいっぱい張ってある状態では真ん中は孤立しないと思うけどどうかなぁ(1個の変数についてのみsourceからの辺のカットとsinkからの辺のカットが共存するみたいな)

nico_shindannin @nico_shindannin

@uwitenpen ちょっと自信がなくなってきた・・・。考えさせてください・・・

nico_shindannin @nico_shindannin

とんでもない誤解をしてたかも・・・

nico_shindannin @nico_shindannin

孤立するような切り方してもいい気がしてきた…。s→a→t と頂点がならんでるとき、Ps=1, Pt=0, Dsa=1, Dat=1（s→a, a→tの両方を切る） で、0≦Pa≦1の値をとっても何も問題ない気がする。

ＳＫＹ/sky58🍊 @skyaozora

@uwitenpen この2つのグラフだと、上なら最小カットは111で、下だと最小カットは22になります。で、上は状態が2つ、下は状態が3つを表してるっぽいのですが何でかなーと pic.twitter.com/WiTiG1v9Xa

拡大

有為 @uwitenpen

@skyaozora 感覚的な説明ですけど、辺を上からa1,a2,a3,b1,b2,b3,c1,c2,c3とおいて、同じ文字のなかではどれか一つの状態をとるとすると、上のグラフだと自然に(a1 and c3)を否定するのができているようにみえますね(下は経路ができない)

有為 @uwitenpen

@skyaozora で、2つの矢印をひくことでこれが成り立って欲しいのかということで、!(a1 and b3) and !(b1 and c3) => !(a1 and c3)の命題を考えると、3状態を仮定した場合はb1,b3がどちらもfalseになりうるので成り立たない

有為 @uwitenpen

@skyaozora bの無限損失のはずだった2個めの状態がとれてしまうせいで損失を軽く見積もれてしまうんだと思う？

有為 @uwitenpen

どういう状態になってるんだろうなこれ

ＳＫＹ/sky58🍊 @skyaozora

@uwitenpen そうですね。ただ今回の例だと必ず両方向に辺が張られているので分かりやすいですが、片方向にしか辺が張られない場合（a1&b3はいいけどa3&b1はダメとか）でも、2状態なら上のグラフ、3状態なら下のグラフってやってちゃんと動くのかなというのがまだ疑問です

有為 @uwitenpen

むずい

nico_shindannin @nico_shindannin

とりあえず、わしの例のスライドに間違ってるところは、帰宅したら修正します。ごめんなさい・・・

nico_shindannin @nico_shindannin

下の貼り方難しすぎる…。

nico_shindannin @nico_shindannin

@uwitenpen 単純に自分の誤解でした（孤立してもよいです）。ごめんなさい…。

有為 @uwitenpen

@nico_shindannin ん、了解です。なかなか難しいですね

nico_shindannin @nico_shindannin

よく考えてから発言しよう…（大反省）

agw @masashinakata

SRM 653 Div II Hard SingleEasyやっと解けた…

agw @masashinakata

なんかDP楽しくなってきたんだけど、解けないものが多すぎる

とーらす🌸📦🌕✨🍀 @torus711

書いた : SRM 653（前々回）, div2 全部 d.hatena.ne.jp/torus711/20150…

とーらす🌸📦🌕✨🍀 @torus711

書いた : SRM 653, div1-1,2 d.hatena.ne.jp/torus711/20150…

roiti @roiti46

はてなブログに投稿しました #はてなブログ TopCoder SRM 653 Div2 Med: RockPaperScissorsMagicEasy - roiti46's blog roiti46.hatenablog.com/entry/2015/05/…