cafelier@SRM

SRM Member Pilot 2

SRM | 02:30 |

SRM Member Pilot 2 の成績・ソース（要ログイン） : AC/WA/WA : 撃墜ラッシュ

450開く

• 『二次元平面上に都市がたくさんあるので、直線道路で２都市の間をつなぐか空港建てて空港ある都市間を全部つなぐかで、とにかく全部連結にしてね、最小コストで』
  • 道路は roadCost*距離、空港は1個につき airportCost かかる

• 空港とかあるけど、基本的に最小全域木だよねえ
• えーと、空港をx個置くとすると、全体を道路でx個の連結成分になるまでつないでからそれぞれの島に空港を置けばいい
• x個の連結成分になる最短の繋ぎ方、はクラスカルのアルゴリズムを途中で止めれば出る

• というわけで、クラスカルを回しながら残り連結成分数*airportCostを足したコストを求めて最小値を返す
• よし。サンプル通った。テストケース自分で考えてないけど、レートつかないSRMだしもう出しちゃえ

300開く

• げ、部屋で誰もまだ解いてない。難しいのかな…
• 『0と1がマス目状に並んでるマトリックスAの2x2を一カ所選んで90度左か右に回転させたらBになりました。ところでAとBのうち何カ所か ? になってるので、ちゃんとこの条件を満たす様に?を辞書順最小に埋めてね』

• 30x30が最大サイズなので、とりあえずAの可能な回し方全通り29x29x2を試してみて、Bとunification。?同士なら0にする、どっちか?ならもう片方の値にする、どっちも0、どっちも1もOK。0と1で違ってたら次を試す。

• 簡単な気がするけど…
• 書いた。サンプル通った。出しちゃえ出しちゃえ。

1000開く

• 『K種類のアルファベットを使ってN元のprefix符号を作りたい。アルファベットそれぞれには重みが設定されてて、N個の符号を全部書き出したときの重み総和が小さくなるような符号にしてください』

• えーとえーと。
• 最小費用流かなにかにならないかな。
  • ルートが空文字列、子供が 0, ... , k-1、その子供が 00 01 ... 10 11 ... (k-1)(k-1) みたいな、符号語でtrieみたいにした無限木を頂点として
  • 各辺が容量∞、コストは指定された重み
  • それぞれの頂点から特別なsink0へ、コスト0容量1の辺が出てて
  • sink0からsink1へコスト0容量Nの辺がでてる
• ルートをsourceとすると、当然最大流量はN
  • で、このときルートからどこかの頂点を通ってsink0へ、というパスがN個できる形のフローになってて、
  • このときの費用はちょうど重み総和になってる。

• 問題は無限木が相手なことで…
  • N=500 だからせいぜい深さO(500)まで考えれば良さそうなので有限と言えば有限だけど
  • もっと狩らないとどこまで頂点考えるのかよくわからなくなるなあ。
• いや、フローのアルゴリズムって最短路を回しまくるわけだから仮想ノードが無限個あっても問題ないような気もしてきた

• いやいや、待て待て！
• このアルゴリズムだとprefix符号にならない！
  • 親からsink0に向かうと同時に子からsink0に向かったりできちゃう。
  • はいダメー

• うーん。
• わからん。
• ちょっとサンプルじっくり眺めてみよう。
• ...
• この{1,3,5}でも{11,13,3}でもどっちでも重み最小、というのはどうしてこうなるのかな。
• えーと
• N=2だったら {1,3} が最小で、
• 次は 5 を足しても、1を分けて{11,13}にしても増えるコストが5だからどっちでも最適なのか

• なのか

• ・・・
• この考え方で一般に最適解求まりませんかね。
• グリーディーに１個ずつ符号語を増やしていく
  • 使ってない符号を使うか、
  • 使ってる符号を分割して二つに増やすか
• どっちかベターな方を使う

• うーん自信ないけど
• レートつかないし（←またそれか）
• 900だからきっと簡単だろうし
• やるか！

• 書いた
• うわ、サンプル通っちゃった
• だしちゃえ！

すごい時間余った

• スコアでも眺めるか
• あれ？さっきトップにいたACRushがめっちゃ下に落ちてる
• 450を再提出してる！なんか罠でもあるのか！

450再び

• 見直し。
• 入出力の条件を読み直す
  • 都市の数は…たいしたことない
  • コストの範囲も…問題無さそう
  • 都市の座標の範囲が…1000000以内…
  • sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) で距離を求めると…
  • x1 やら y1 やらが int だとオーバーフローしますぞ！！！

• 慌ててさっさとdoubleにキャストするコードを挿入
  • テストテスト。
  • (0,0) (1000000,1000000) road=0.01, air=10000000
  • よし、修正前と後で結果が違う。これはバグってた。
  • あぶねー！再提出

• って、結果が違う、って確認しただけで正しいかどうか考えてなかった
• このくらいなら手計算できるな。
  • えーと、道路で行くのが速いから、なんか√2っぽい値が答えなはず
  • チラッ
    • 1014142.1356...
  • という答えを修正後のプログラムが返しています
  • 後ろの方は√2っぽいけど、最初の10はなんだ…？？？？

• あああ空港のコスト1000000か！
• 必ず空港1個は建てるコード書いちゃってる！
  • 連結成分の数で足してるし！

• これはダメだ。連結成分1個なら0個にするコード追加
• よし 14142.... になった。これだ。再再サブミット

• サンプルにそういう例無いのか…ないなあ
• これは撃墜合戦になりそうだなあ。
• 例を作っておこう。
• さっきのヤツでいいか。オーバーフローも空港1個も撃墜できるし

• 300もサンプルに無さそうな例を調べておくか
• AもBも?のパターンが無いかな。じゃあそれ。{"??","??"}

撃墜タイム

• (0,0) (1000000,1000000) road=0.01, air=10000000 で4撃墜
  • オーバーフロー２人と空港1個２人
• 勝利！

• 300の方は誰もひっかかってなかった。無念

感想

• そして900はやっぱりSystem Testで落ちてた
• さらに450も落ちてた！！！
• えええまださらにハマりポイントがあったのか。うわあダメすぎる…
  • 都市数1個の場合か！
  • 連結成分の個数が1に減ったときに特別処理、というコードで対処してたので、最初から1だと対処できてない。
  • こういうのはナシにしろよ俺とあれほど…うわああああ
  • ACRushもまったく同じ特殊処理を入れてまったく同じくSystem Testに落ちてたので、微妙になごんだ