AOJ2224: Save your cats

アルゴリズム/最小全域木 データ構造/グラフ 競技プログラミング/AOJ 競技プログラミング アルゴリズム/双対グラフ

Save your cats | Aizu Online Judge

解き方

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

ハマったところ

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

github.com

ARC083 E: Bichrome Tree

アルゴリズム/DP 競技プログラミング/AtCoder 競技プログラミング データ構造/木

E - Bichrome Tree

解き方

  • ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく
    • 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い
  • 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる
  • 頂点iがleafでない場合
    • 子どもの重みの割当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

アルゴリズム/DP データ構造/グラフ アルゴリズム/最短経路 競技プログラミング/AtCoder 競技プログラミング

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

競技プログラミング/AtCoder 競技プログラミング

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の設定したら、強制再起動かかるようになった（諦めた）