小粒なスクリプトメモ

MarathonMatch等でときどきスクリプト書いたりしますが、書くたびにググっているのでここにまとめておくことにした。

TCO18 MM R1 RoadsAndJunctions

方針

序盤

置く候補を全探索し、置いたときにスコアが大きくなる順に置いて行った。 盤面がでかくて全探索できないときは探索する点を間引いた。

終盤

  1. 焼き鈍しを9400ms実行。遷移は以下の3つで、失敗確率0での解を求めた。

    • ランダムにjunctionを置く
    • 隣へ移動する
    • junctionの削除
  2. 失敗確率も考慮し、期待値が低くなるように1.で求めた点を多重化

反省点

  • yoursの期待値の最小化ではなく、(yours^-2)の期待値を最大化をする発想がなかった
  • 期待値の計算が適当
  • GCEでテストできるようにしていたが、環境構築に失敗していて、最終日までその失敗に気づかなかった(ずっと初期に書いたコードでテストされていた、途中でおかしいなとは思ったんですけどね…)
  • パラメータの調整の時間がもったいなかった(雑で良いので自動調整できるようにしたい)

良かったところ

  • 1週間頑張れた(えらい)
  • EMSTのO(nlogn)解法のような、面白そうだけど効果が薄そうな実装はせず、より効果の高そうな方針の検討に時間を割いた。(初期頂点から構成されるMSTの最長辺の長さで平面を分割するお手軽高速化は行ったけど、よく考えると非常に遅くなるケースあるしやらないほうが良かったな…)

ローカル1000ケースで評価して焼き鈍し解法のほうがよかったのでそっちを投げたけど、standingsでは下がっていた。もしかしてTLEしていたのかな。

別に着るわけじゃないだけどTシャツ獲得を目標にして残りを頑張ろう。

復習

  • 自動調整できるようにする
  • 期待値計算の見直し
  • (yours^-2)の期待値を最大化をしてみる
  • コードの書き直し

GCJ 2018メモ

GCJは今年からサーバーサイドでジャッジされる形式に変わったのでJavaで参加するときのメモ。

  • クラス名はSolutionクラス
  • テスターは以下のような形で実行
python3 testing_tool.py java -cp ../bin Solution

Rustのimplを複数ファイルに分割する

以下のようにすればできる。 github.com

アドベントカレンダーに合わせてローグライクゲームのAIを作るコンテスト開こうかと思いましたが頓挫しました

この記事は Competitive Programming Advent Calendar 2017 - Adventar の 21日目の記事として書かれました。 (診断人さん主催お疲れ様です&ありがとうございます)

(本文略)

まとめ

明日は kmjp_pc さんの記事です!楽しみですね!

OCamlのsetの実装の軽い紹介

Competitive Programming Advent Calendar 2016 - Adventar 1日目の記事です。

OCamlのsetがsplit/merge可能なAVL木になっているので、それの簡単な紹介です。 ちなみに、上の一文でこの記事の9割は終わったも同然です。

いくつかコアの関数を軽く紹介。計算量でh(t)って書いてあるのは、AVL木 t の高さのこと

balance

  • |h(n.l) - h(n.r)| = 3 のときに、木を回転させて |h(n.l) - h(n.r)| < 3 にする。
  • 計算量は O(1)
  • OCamlの実装だと、balという名前がついている
  • OCamlのset実装のAVLは、|Balance factor| <= 2 が不変条件になっているので注意。 gist.github.com

join(Node l, Node v, Node r)

  • l, v, r の並びでマージする関数
  • h(l), h(r) は任意で、h(v) = 1
  • 計算量は O(|h(l) - h(r)|)

gist.github.com

merge(Node l, Node r)

  • 2つのAVL木 l, r をマージする関数
  • 計算量は O(max(h(l), h(r)))
  • OCamlの実装だと、concatという名前がついている

gist.github.com

split(Node t, int k)

  • AVL木 t を [0,k), [k,size(n)) で分割する関数
  • 計算量は O(h(t))
    • (splitで再帰しながらjoinを呼んでおり一見 O(h(t)) に見えないが、joinしていく木の高さが徐々に高くなっていき、O(h1 + (h2 - h1) + (h3 - h2) + ...) = O(h(t)) となるのが面白い)

gist.github.com

性能

コピー&ペーストで、AVLとRBSTの性能を計測してみました。

問題
copypaste: コピー&ペースト - 2012年 日本情報オリンピック春合宿OJ | AtCoder
JOI 2011-2012 春季トレーニング合宿 問題

AVLによる解答 Submission #1000130 - 2012年 日本情報オリンピック春合宿OJ | AtCoder
RBSTによる解答 Submission #1000163 - 2012年 日本情報オリンピック春合宿OJ | AtCoder

AVLのほうがRBSTより速い(やけに実行速度が速いけど、昔よりジャッジが早くなってたりする?)

反省

  • 本当は図を入れたりして、どんな操作か丁寧に説明したかったのですが、間に合わず😞

明日の担当は tubo28 さんと snuke さんです。

参考(といいつつ自分はあんまり見てない)

Codeforces Round #372 (Div. 1) B. Complete The Graph

codeforces.com

Codeforces Round #372 Editorial - Codeforces

解法

辺のコストを1つあげると、最短経路のコストは0か1増加する。 広義単調増加なので、割り当てるコストの総和を2分探索で求めればよい。 辺のコストの割り当て方は適当でよい。

gist.github.com