AOJ2224: Save your cats

Save your cats | Aizu Online Judge

解き方

  • pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木(コストは、fenceの長さ)を求めれば良い
  • 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒
  • 元の平面グラフの全域木に使われた辺を、双対グラフ上で削除すると、そのグラフは双対グラフの全域木となる
    • もとのグラフで最大全域木を求めて、辺全体のコストから引けば、双対グラフの最小全域木のコストが求められる

ハマったところ

  • 双対グラフの最小全域木を考える必要があることはわかったが、双対グラフの性質を存在ごと完全に忘れていた
    • 双対グラフの性質はまとめて覚えておく必要がありそう

github.com

ARC083 E: Bichrome Tree

E - Bichrome Tree

解き方

  • ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく
    • 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い
  • 頂点ileafの場合、色はどちらでもよく、重みはx_iになる
  • 頂点ileafでない場合
    • 子どもの重みの割当b, wをそれぞれまず計算する
    • iへ色と重みを割り当てると、b_i = x_iまたはw_i = x_iを満たすが、ここでx_iでない方はできるだけ小さい方がその後の重み割当がしやすくなる
      • 頂点iの子どものリストをc_1, c_2, ..., c_nとして、dp[j][k] = c_1, ... c_iまでを使って、重みの和がjになるような色の割り当て方があるかどうか(true, false)と定義してDP
      • dp[n][k] = trueとなる最大のkを用いてiへの色の割当を考える
  • 計算量の見積もり(怪しい)
    • DPについて: k <= X_iとして問題なく、さらに各辺について、1回しかこのDPで参照されないので、解法全体を通してO(NX)で収まるはず
    • dp[n][k] = trueなる最大のkを求める:O(X)
      • これは各頂点について行われるので、解法全体でO(NX)
    • 解法全体ではO(NX)のはず

github.com

ARC083 D: Restoring Road Network

D - Restoring Road Network

解き方

  • これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する
  • 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、
    • もし、d[i][j] == cならば、もう辺を追加する必要はない (A)
    • d[i][j] < cならば、cが最短距離であることに矛盾するので、そのようなグラフはない
    • d[i][j] > cの時、i, j間にコストcの辺を追加する。コストの合計にcを足し、最短距離をd[s][t] = min(d[s][t], d[s][i] + c + d[j][t], d[s][j] + c + d[i][t])で更新する
  • すべての町のペアに対して行うので、外側のループがN^2回、内側のコストの更新がO(N^2)なので、全体でO(N^4)の解法となり、N <= 300なので間に合う

その他

  • Warshall Floydをしながら、各辺が更新された回数を記録する(2回以上更新された時、その部分は上記解法でいう(A)に当たる)という解法もあり、こっちのほうが綺麗に解けそう

github.com

ARC083 C: Sugar Water

C - Sugar Water

解き方

  • A, B, C, Dそれぞれの操作を何回するか、全探索
    • A, Bについては、100A <= F <= 30 * 100より、たかだか30回
    • C, Dについては、最大でF/2g溶ける(E=100の時)ので、たかだか1500回
  • 合計で[tex:O(109)]なので、ダメでは?という気もするが、間に合った
    • 水のありうる量を列挙、砂糖のありうる量を列挙し、各水の量について、最大の砂糖の量を二分探索、とすると、O(1500^2+30^2*log(1500^2))となって十分間に合う感じになりそう

ハマったところ

  • 濃度の比較を整数で行おうとした時、\frac{a_1}{a_1+b_1} > \frac{a_2}{a_2+b_2}の式変形で、a_1(a_1+b_1)(a_2+b_2) > a_2(a_1+b_1)(a_2+b_2)としていてWA

github.com

活動記録(2017/9/11-2017/9/17)

競技プログラミング

ARC083

結果 97th, 1551->1679 (Perf: 2363)

Cを3回WAしてダメかと思ったが、うまいことEまで解けた。

AOJ0189, AOJ2249, AOJ2200

蟻本練習問題。warshall floydだったりdijkstraだったり、最短経路問題の基本系

その他

  • 金沢行ってきた
  • Wake on LANの設定したら、強制再起動かかるようになった(諦めた)

AOJ2200: Mr. Rito Post Office

Mr. Rito Post Office | Aizu Online Judge

解き方

  •  z_{i-1}からz_iへの行き方は次の2通り
    • 陸路で行く
    • 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路
  • 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく
  • dp[i][j] = 船がjにある状態でz_iまで集配するための最短距離として動的計画法
    • dp[0][z_0] = 0、その他INFが初期状態
    • [tex:O(RN2)]は間に合うか怪しいと思ったが、間に合った

ハマったところ

  • Warshall Floydまでは思いついたが、直前の船の位置だけメモ化すればよいことに気づかず、しばらくO(R^N)の解法しか思いつかなかった

github.com

AOJ2249: Road Construction

Road Construction | Aizu Online Judge

解き方

  • captalを始点としてdijkstraして、その後経路復元
    • 経路復元のための情報において、条件を満たす辺のなかでコスト最小のものを保存するようにする
  • 多分、priority_queueを使ったdijkstraじゃないとTLEすると思う

ハマったところ

github.com