JAG Winter Contest 2010 簡易解説

ICPC

Twitter上ではすでにつぶやいたのですが、復習される方のために1/24に行われたJAG Winter Contest 2010の簡易解説を上げておきます。

  • A:最小になる≒極値≒微分したら0になる です。a,b,cについて偏微分した式=0とすると、3連立方程式になります。コレを解けばa,b,cが出ます。
  • B:グラフを作ると二部グラフになります。Aをカバーする(Aの頂点を全て使う)マッチングを持てばBの勝ち、持たなければBの勝ちになります。証明は後日の解説にて。
  • C:n個でうまく行く確率をf(n,m)とする。箱1から順に開けてi個目の箱で1を見つける確率は1/n。残りのn-i個がうまく行く確率はf(n-i,m)なので、f(n,m)=\sum_{1<=i<=min(n,m)}(1/n)*f(n-i,m)
  • D:ある平面が外側にあるかどうかは、その平面の法線ベクトルと他の点へのベクトルの内積が全ての点について同符号になることを確認すれば良い。摂動を入れると全ての面が三角形になるので処理が簡単になる。
  • E:書け！
  • F:円と円の共通接線を列挙、ジャンプできる接線を列挙、コースとショートカットをグラフ化、ダイクストラ、です。順方向と逆方向で辺を多重化する必要があります。担当者2名のコードは1000行超えました。
  • G:幾何情報からグラフを生成し、ループを検出する問題です。スキャンライン法を使用してO(N log N)で計算する必要があります。
  • H:0と1からなる数列を正しくソートできれば正しいソートアルゴリズムであるという01-principleの定理を使います。そのままやると2^Nパターンありますが、一段ソートされた出力を見るとN^2通りにまとまります。
  • I:ダイヤをグラフにします。A->Bはコスト-1容量Ci、B->Aはコスト0容量Ci、上から下向きのエッジはコスト0容量∞とします。Aの最初の頂点からBの最後の頂点への最小費用流×-1が答えです。負の閉路が出るため負閉路消去法が必要です。
  • J:素直なDPだとO(N^3)、m[l][r-1]<=m[l][r]<=m[l+1][r]を利用するとO(N^2)となります。