適切にカードをぶつけて最適に相手をフルボッコにするゲームの解き方まとめ
-
tokoharu_sakura
- 1087
- 0
- 1
- 0
-
- いいね！0
nico_shindannin（診断人）
@nico_shindannin
しめじたんと同じ解法以外あるのかなぁ…。SRM217に類問ありました RT @tokoharu_sakura: 【緩募】 http://t.co/wYsoUBby 皆さんはこの問題どう解きますか
2011-11-16 00:42:25
Dは堕天のD
@Darsein
僕が最初に思いついたのはしめじたんさんと逆に、自分の手の最小カードから試す貪欲。あとは最大二部マッチングとか使えますかね？ RT @tokoharu_sakura:【緩募】 http://t.co/8B0A3fqO 皆さんはこの問題どう解きますか
2011-11-16 00:47:09
chokudai(高橋 直大)@AtCoder社長
@chokudai
第一感はソートしてO(klogk)の二分探索（ちゃんと解けるかどうかは未検証）。制約見て、「お？」ってなった後、O(k^2)の貪欲になりそう QT @tokoharu_sakura: 【緩募】 http://t.co/XJ9ctrZ4 皆さんはこの問題どう解きますか
2011-11-16 00:57:05
ＳＫＹ/sky58🍊
@skyaozora
@chokudai @tokoharu_sakura 貪欲でも尺取でやればklogkで済みそうな。自分の第一感はそれでした
2011-11-16 01:00:45
とこはる
@tokoharu_sakura
@nico_shindannin そうなんですよね。Accept数伸ばすだけだったらこの問題は「二部マッチング乙」とか、「はいはいGreedy」になってしまうんですけど、考えてみると色々解法が浮かぶ余地があるので良い問題だと思います。コンテスト向きではありませんが。
2011-11-16 01:15:04
chokudai(高橋 直大)@AtCoder社長
@chokudai
しかしこの問題で二部マッチングかぁ グラフを書いてみて考える、って感じの人だと確かにそうなるなぁ。面白いかもしれない
2011-11-16 01:04:02
とこはる
@tokoharu_sakura
@chokudai グラフ書いてみようとすると特殊な形になることがわかるので、実際にグラフ書くのも法則を理解するヒントになるかもしれません。
2011-11-16 01:07:44
Dは堕天のD
@Darsein
基本同じアルゴリズムなはずなのに、ずばずばと計算量落としにかかる赤い人たちをみて、改めてこのTLぱないと思った。 k<=26みた瞬間にまともに計算量見積もるのやめたし・・・
2011-11-16 01:05:54
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Darsein むしろこれくらいの問題だと、計算量よりも実装量が少ないプログラムを考えに行った方が良いから悪くないとおもうよー
2011-11-16 01:08:15
Dは堕天のD
@Darsein
@chokudai あれ、「たいていの問題はグラフで書ける」的な師匠の記事読んでたから思いついた感じなんですけどｗ あれは探索の話ではありますけど。
2011-11-16 01:13:32
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Darsein おー、確かにそだねー 自分の最近の思考は、とりあえず全探索→全探索で間に合わないなら纏める→無理なら削る方法がないか考える→なさげならグラフとかにしたり色々考える って順序だから、二部マッチングはなかなか出てこないなー
2011-11-16 01:18:22
chokudai(高橋 直大)@AtCoder社長
@chokudai
@Darsein おー、確かにそだねー 自分の最近の思考は、とりあえず全探索→全探索で間に合わないなら纏める→無理なら削る方法がないか考える→なさげならグラフとかにしたり色々考える って順序だから、二部マッチングはなかなか出てこないなー
2011-11-16 01:18:22
Dは堕天のD
@Darsein
@chokudai 僕も全探索が無理そうならとりあえずDPや二分探索を疑う感覚になりつつありますね。 確かにグラフでしかも二部を利用するのは最初に思いつくものではない気がします。今回は解法募集っぽい感じもしたので少しひねくれて考えてみました。
2011-11-16 01:24:15