読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

AOJ2254 Fastest Route

Fastest Route | Aizu Online Judge

まずN<=8ならばnext_permutationi()でO(N!)全列挙すれば通りそう。クリアした順序は最短時間に関わらないので、どのステージをクリアしたかの情報のみを保持しておけば計算する量を減らせそう。クリアした・してないの2つの状態がNステージについてあるので全体で2^Nの状態について計算すればよさそう。

dp[S] = (集合Sをクリアするのにかかる最短時間)とする。
dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので漸化式で表すと
dp[S] = min{dp[S/{j}] + min{t[j][k] | k∈S/{j}} | j∈S}
となる。集合について扱うDPなのでbitDPで書くとO(n^2・2^n)で解けて間に合う。


競プロ関係のサイト

コンテスト・オンラインジャッジ

AOJ 0043-Puzzle

パズル | Aizu Online Judge

DFSで面子と雀頭の取り方を全て試す。

DPL_4 B Coin Combination Problem II

Coin Combination Problem II | Aizu Online Judge

N<=40 とここだけ明らかに制約が小さいので、これを利用して半分全列挙します。事前にソートしておくことで二分探索を用いて高速に計算できます。

DPL_1 E Edit Distance (Levenshtein Distance)

dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。
各文字列に対する操作についてDPの遷移を考えると

  • 挿入 dp[i][j] = dp[i][j-1] + 1
  • 削除 dp[i][j] = dp[i-1][j] + 1
  • 置換 dp[i][j] = dp[i-1][j-1] + 1

となります。さらにs1[i]とs2[j]が等しいときは置換を行う必要がありません。そのため、置換の代わりに

dp[i][j] = dp[i-1][j-1]

と遷移できます。

SRM 710 div2

Writerの方の解説
codeforces.com

Easy

問題概要

 n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる。

解法

 一番最初を選ぶ場合はマイナスのものだけを選択することで最大となり、選ばない場合はプラスのものだけを選択することで最大となる。この両パターンで大きい方を返す。


Med

問題概要

 n要素の配列Aが与えられる。i番目の要素を選択するとA[i]を0にした後、i+1番目からA[i]個の要素に+1する。このときn-1番目の要素の次の要素は0番目の要素である。要素1つのみが正の数になるように要素を選択していく。このとき、どのように要素を選択していけば条件を達成することができるのか出力する。

解法

 0でないもっとも先頭の要素を選択することを繰り返し、要素の遷移をシミュレートしていく。


Hard

問題概要

 n頂点m辺の連結な無向グラフが与えられる。各頂点には0からn-1のラベルがつけられる。自己ループや二重辺がないことが保証されている。各辺および各頂点にコストが定められており、頂点iから頂点jのパスのうち最大の辺のコストと最大の頂点のコストの積がパスのコストとして定められる。d(i, j)を頂点iと頂点jを結ぶ経路の最小のコストとする。0 <= i < j <= n-1 の全てのi,jの組についてのd(i, j)の和を出力する。

解法

 Writerの方の解説のapproach1の方法についてです。頂点、辺をコストの小さい順に見ていき矛盾する点がなく暫定の最短コストよりも小さければ最短コストを更新します。正直ちゃんと理解できているか怪しいので嘘が含まれているかも…

AGC011 A, B, C, D

agc011.contest.atcoder.jp

A問題

 早い時間に到着する乗客をバスに乗せずに待たせて置くほうがいいパターンは存在しません。したがって到着時間をあらかじめソートしておくと、条件を満たすぎりぎりの乗客まで乗せて出発するを繰り返すことで答えを求められます。


B問題

 色の順序等は答えに影響しないことからあらかじめ、大きさ順にソートしておいても問題ありません。a[i]番目の生物がa[i+1]番目の生物を吸収できる条件は、a[i]以下の大きさの和の2倍がa[i+1]以上であることです。したがって、累積和をとって、k番目以降が全て条件を満たしているならばn-k+1色が存在可能です。


C問題

 二つの連結グラフA, Bが存在するときこれらのグラフから作られるグラフの連結成分の個数を考えます。

  • A, Bどちらかが孤立点のとき

 頂点数の積

  • A, Bどちらかが二部グラフでない

 二部グラフでない場合奇数長のサイクルが存在するため各頂点間に偶数と奇数のパスが両方存在する。したがって全ての頂点が連結になるため連結成分の数は1

  • A, Bともに二部グラフ

 奇数長のパスの組と偶数長のパスの組でそれぞれ連結成分がつくられるため連結成分の個数は2

与えられたグラフの孤立点の個数をa個、二部グラフの個数をb個、二部グラフでないグラフの個数をc個とすると、
{ 
2b^2 + 2bc + c^2 + a^2 + 2a(n-a)
}
個の連結成分となります。二部グラフの判定はdfsでO(|V|+|E|)で可能なので2秒以内に答えが求まる。


D問題

 rngさんの解説放送を見てください。
www.youtube.com