keyword 2部グラフ 最小点被覆 C++ 問題概要 W*H(W,H 解法 板を置くのは連続した部分の左端か上端になる。全ての泥があるマスに対して、連続した左端のノード(in A)と上端のノード(in B)を繋いで2部グラフを作る(A群とB群は別)。あとは最小点被覆なので、例…

解法 編集距離を求めるだけ。テストケースが実は複数ある。stdio.hをincludeしなくてもEOFは-1らしい。

keyword Greedy Java 問題概要 N*N(N 解法 Greedyにやってみたら上手くいった。上手くいった理由は分からない。

keyword BruteForce C++ 問題概要 N(バイスがある。それぞれのデバイスはM( 解法 Bについて全探索する。データ構造を工夫してBを決めたらB/Pの最大値をO(N * log M)で計算できる様にする。全体の計算量はO(N^2*M*log M)。

keyword メモ化再帰 C 問題概要 dequeに配列(長さN 解法 Greedyでは駄目らしい。のでメモ化再帰して解く。memo[from][to]は[from, to)が残ったときに得られる最大値。計算量O(N^2)。

解法 蟻本を参考にして解いた。ソース略。

keyword 最小全域木 BruteForce Java 問題概要 ノード数V( 解法 下限に対して全探索する。下限さえ決めてやれば普通に最小全域木を求めると目的関数の値が計算できる。計算量O(|E|^2)。 感想 最初は下限に関して二分探索してたけどよく考えたら単調性はなか…

解法 二分探索するだけ。