ぱらつり記

No description

CodeRunner予選Aに参加して盛大に爆死した

幾何ーーーーーーーーー!

つらい

さまりー

200x200の領域から交差しない頂点対を選んでいってできるだけ伸ばしてね
でも頂点IDがどの座標に対応するかは見えないよ

スコア2594で204位

投げたクエリ延べ9166回(+α)

非常に辛い

流石に2回目の開催とあって単純な問題ではなくなっていますね。
というか去年が簡単すぎたのか(それでもまともに取り組めなかったけど)

問題を前にして思考停止

CodeRunnerは時間をかけて得点を伸ばしていくコンテストですが、考えることができない自分にはつらいものがありました。

思考できないから問題を噛み砕くことができない

「長く引いたら交わるし短く引いたらスコアが伸びない」

もうずっとここで止まってるんですよね。

去年の予選Aはランダムで文字列送りつければある程度なんとかなりましたが、今回は踏み出すことができずに2時間くらい頂点対の距離を取るマシンと化していました。

1時間でなんとかできるならいいんですが、考察が全くできないから肝心の情報が生かせない

ニコ生でちょくだいさんの実装アルゴリズム見た時はふぉーーーって
言われればそうなんです。それは当然なんです。

その言われれば当たり前のことが考えられない。もちろん考えられたら苦労しないですが自分にはあらゆるものが不足していてダメ。

  • 3点を用いた座標特定
  • 良い辺をふるい落として収めていく

うーん。やっぱり数時間前の自分には思いつくなんて無理でしたね。
サブマリン上位勢すごすぎ。

コロコロ変わるツール

  • C#で頂点対の距離を何の考えもなく適当に2時間位取る
  • RubyというかPry(on RaspberryPi)でソートして出力
  • とりあえずC#でスコア昇順にとっていく(スコア0でロールバック)
  • C#で乱択(スコア0で巻き戻し)。終了15分くらい前にやり直したらちょっとスコア伸びた

結局能なし乱数頼みに落ち着きました(この時既に残り1時間弱)

VisualStudio使ってC#でクエリ飛ばしつつPryでいじるという。
正直なところC#の1つのプロジェクトでうまく回せないからやむを得ずやったんですが(最近Railsしてるのも相まって)、それでも「こっちを試してみたい」というやつでプロジェクトまるごとコピーしたり。
なんとかうまくやる方法ないですかねえ。(VS複数起動はごちゃってアレ)

それかスコア降順で取っていくのを最初にしたほうが良かったかもしれない。
良くも悪くも1query/sec制限があるのであとから思っても遅いですね。

まとめ

考察ができない

問題を前にしていかに戦略を巡らせられるか、自分の場合は緊張で何考えればいいのかわからなくなるのでどうしようもないのかもしれませんが。

予選B……できる気がしねえ……

メモ

ニコ生その1

  • 1点Aを決めて頂点対の距離をとる
  • 点Aから最遠のものを点Bとする
    • 線分ABは対角線状にある
  • AC + BCが最大となるような点Cをとる
    • 点Cは線分ABとは異なる隅にある
  • 点Pをランダムに取り、BP + CPとBCの積(△PBCの面積)を△PBCの高さhと見る
    • 等積変形を考えれば底辺を共有する等しい高さの三角形の面積は等しい
  • 求めた高さhが近い点同士を接続する

ニコ生その2

  • これまでの結果から最良の辺を選択する。
  • それ以外の上位の辺から有効なものを選択する。
  • 最初の辺と平行に近い辺が集まってる

snuke氏のツイート