2017-02-06から1日間の記事一覧

SRM 548 DIV2 Hard: KingdomAndPassword

解法 oldPasswordが新しいパスワードにもなる場合がコーナーケース。 そうでない場合を考える。 先頭からi桁が等しいとする。つまり、新しいパスワードがoldPasswordと異なる最上位の桁をi(0-indexed)とする。この桁の値によって新しいパスワードがoldPasswo…

SRM DIV2 Hard: OrderOfTheHats

解法 トポロジカルソートの要領で以下のビットDPを解く。 dp[mask] = トポロジカルソート済みの頂点の集合がmaskであるときの削除した辺の個数の最小値 N<=20 → ビットDP DAG →トポロジカルソート

AtCoder AGC010 C - Cleaning

エディトリアルの判定 L>=min(max(c[i]), Σ(c[i])/2)がよくわからなかった。 以下、条件判定の考察のみ変数名はエディトリアルのものを踏襲 葉ではない頂点をv、m = max(c[i])とする。 T >= 0 (1)は自明。 A[v]が最大になるのは子供=>v=>親 を含む経路がすべ…