Google Code Jam 2017 Qualification Round

iwashi31 @iwashi31

GCJ65ptsのフレンズです

はむこ @hamko_intel

うーん、明らかに欠落してる発想があるんだよね。「操作回数を固定する」「グラフの辺に着目する」「グラフを構築しながらうにょうにょする」みたいな

きひろちゃん（9歳幼女） @aki33524

D解説読んでもよく分からん

きひろちゃん（9歳幼女） @aki33524

問題を分割してOKみたいなのよく分からんなぁ

赤毛のロビン @akagenorobin

B-largeが落ちたとな。。。うーん、なんでだ…

みさわ @Mi_Sawa

@aki33524 縦横は「+でも.でもないものは高々1つずつ」で斜めは「xでも.でもないものは高々1つずつ」という制約で, それぞれ置けると1pt. 各マスに「+でも.でもない」があるかと「xでもry」があるかがわかると, そのマスに何が入るかは決まる.

iwashi31 @iwashi31

@akagenorobin 99999999999999999とかのときにpow周りで誤差が出てるっぽいです

きひろちゃん（9歳幼女） @aki33524

@Mi_Sawa なんか正しいことは分かるけどこれ思いつけないなぁという気持ちになっている

みさわ @Mi_Sawa

@aki33524 目的関数とかアップグレードとか見て, 「縦と斜めに分解してね」という作問者の気持ちを汲み取るゲーム

きひろちゃん（9歳幼女） @aki33524

D、問題を+/xに分割してそれぞれ2部マッチングしてやればよく、初期値はマッチングのノードを消したと考えればOKというところまでは理解してるんだけどどうもな〜〜〜〜

きひろちゃん（9歳幼女） @aki33524

+/xを合わせてoになるのが作為的過ぎてスッキリしないのかなぁ

きひろちゃん（9歳幼女） @aki33524

@Mi_Sawa フロー系に一瞬思いを馳せたけど縦と斜めあるから無理ンゴｗっつって終了してしまった

kmjp @kmjp_pc

昨日は朝少しGCJやったあとずっと出ていて、ARCもTCOも不参加だった。GCJはCまで通ったのはよかったね。Dは適当に貪欲やったら失敗して、最大フローに持ち込むんだろうなーというところで時間切れ。貪欲でも解けたのね…。

Masaki Hara @qnighy

GCJ2017qual-dの角配置問題はこの順に貪欲にとれるか試せばよい pic.twitter.com/wUR543QRN6

拡大

きひろちゃん（9歳幼女） @aki33524

GCJのDむずいにゃあ

nico_shindannin（診断人） @nico_shindannin

そういや、GCJの問題D、超誤解してた図面のツイートが残っているので、消しとくのじゃ。

きひろちゃん（9歳幼女） @aki33524

斜めの二部マッチングきらい

まーす @__math

@aki33524 45度回転させると斜め要素がなくなる

きひろちゃん（9歳幼女） @aki33524

@__math それはそうなんですけどindexがごちゃごちゃしてこういうの苦手

まーす @__math

@aki33524 45度回転させるときは(a,b) -> (a+b,a-b) ってすればいいので大丈夫

きひろちゃん（9歳幼女） @aki33524

D-largeも通した

きひろちゃん（9歳幼女） @aki33524

クッソ時間かかったなぁ……

きひろちゃん（9歳幼女） @aki33524

D-largeどう考えてももっと簡潔に書けそう ideone.com/9YKRO9

nico_shindannin（診断人） @nico_shindannin

そういえばGCJ A問題の貪欲で良い理由を放送で質問されたけど、うまく説明できなかった気がするのじゃ。プログラミングコンテストチャレンジブック P139に書いてあるのじゃよ。

nico_shindannin（診断人） @nico_shindannin

もう、だいぶ蟻本の内容を忘れつつあり、悲しみ。たまに、ざっとで良いから目を通そう…