TCO15 Algorithm R1C

yuki2006 @yuki2006_kd

@koyumeishi_ 使われないコードはうんこーどっていうのがはっきりわかりますね（

yuki2006 @yuki2006_kd

Med、Setだけでいい理由教えてください...

agw @masashinakata

pic.twitter.com/O3IIxC375T

拡大

agw @masashinakata

チャレンジ観戦中にも関わらず反応してくれた（・∀・）

roiti @roiti46

@yuki2006_kd この問題は葉の数を数えればよいのですが、葉の数は枝分かれの数に対応しており、枝分かれの数はもとの配列の長さとセットの長さの差で計算できるからです

roiti @roiti46

medは問題文読解が一番難しいところ

roiti @roiti46

Medはサンプルの２を実際に絵に描いてみると解法に気付ける気がする

紙ぺーぱー @camypaper

Med意味不明なんだけど(´･_･`)

紙ぺーぱー @camypaper

あぁ，候補の数を挙げればいいのか…パスの選び方の数え上げかと思ってた(´･_･`)(´･_･`)

紙ぺーぱー @camypaper

@roiti46 今読んでましたが，完全にパスのペアの数え上げだと思ってましたね…

roiti @roiti46

@camypaper あそこまでの条件設定してたらパスの数え上げでもさせられるのかと思いますよね

紙ぺーぱー @camypaper

@roiti46 明らかに誤読を狙っているとしか思えない…

roiti @roiti46

@camypaper 実際解法は簡単だからそうとしか思えない（ある意味サービス問題ではあるけど）

紙ぺーぱー @camypaper

Med，葉の頂点のみのパスが候補として選ばれる(クソかよ)

紙ぺーぱー @camypaper

いや，クソとまで言うことはない思ったけど，問題文の設定はなんだったんだという思いが

yuki2006 @yuki2006_kd

@roiti46 ありがとうございます。前半は分かりましたが、後半はまだピンときてません。。

紙ぺーぱー @camypaper

@yuki2006_kd 葉を探したい=子がいない頂点を探したい これは全体から親であるような頂点の数を引いた値と一致する 親の配列をsetに突っ込むと全て独立であるような親の集合がわかる これを使うとN-set(parents).Countが葉の数 ということですー

yuki2006 @yuki2006_kd

@camypaper なるほどです！！ありがとうございます。（単純でした

roiti @roiti46

おお、すばらしい解説だ

紙ぺーぱー @camypaper

クソみたいなゲームDPを書いてしまったがgrundyでいけたのか…

kmjp @kmjp_pc

む、確かにTCO Round1CのHardは900pt普通に超えるなこれ…。むしろ自分は250ptを1ミスしていたし、それ除いてもEasyとHardが同程度な気すらしてきた。

kmjp @kmjp_pc

GCJ Round1Cやろう。BのC問題もまだ残してるけど…。

kmjp @kmjp_pc

GCJ Round1C解いた。Round1Bより素直な問題で、ノーミス全完で1時間ちょいだった。予選3つとも出ていたら、Round1AとRound1Cは余裕の全完突破、一方Round1BはかなりWA連発でかなり苦戦、というだいぶいびつな結果になってたっぽいな。

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoderOpen 2015 Round1C Easy DevuAndPlantingTrees - kmjp's blog kmjp.hatenablog.jp/entry/2015/05/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoderOpen 2015 Round1C Medium UnrelatedPaths - kmjp's blog kmjp.hatenablog.jp/entry/2015/05/…