問題ページ Plush Toys | Aizu Online Judge 解法 bitDPをする。dp[S] = (集合Sの要素に含まれる種類を左から並べたときの最小の並べ替え回数) とする。dp[S|1<<i] = dp[S] + (並び替えに必要な回数) と遷移できる。並べ替えに必要な回数は並べる区間に含まれていない種類iの個数なので、種類別に累積和を取っておけばO(1)で求めることができる。したがってO(M2^M)で解ける。 //#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; t…</i]>

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf 考えたこと 最大の最小化と言われたので二分探索をする。幅Xで実現することができるかの判定について考える。x方向、y方向についてそれぞれ貪欲に決めていくと幅Xで必要な…

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと 色iが色jの上に乗っていることをjからiへの有向辺が張られている状態と考えるとトポロジカルソートをすればよい。O(HWN)で辺を張ればよく、トポロジカルソート…

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと N頂点の木で値の総和が最大になるような連結成分を求めればいい。dp[i] = (頂点iの部分木で最大の値の総和) とするとdp[i] = sum(dp[j], 頂点jが頂点iの子でdp…

問題ページ JOI 公園 | Aizu Online Judge 考えたこと とりあえず広場1から各広場への最短距離はdijkstraで求まる。Xを決めれば各辺について両端の頂点への最短距離がX以下かどうかでその辺が撤去される辺か判断できるのでO(M)でできる。max(X) = 10^10 でま…

問題ページ バームクーヘン | Aizu Online Judge 考えたこと 最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認す…