2019-02-11

AtCoder Regular Contest 067：E - Grouping

問題

https://atcoder.jp/contests/arc067/tasks/arc067_c

考え方

漸化式的な考え方でDPをする。難しい。

$dp[i][j] := i$ 人未満のグループのみで $j$ 人を分ける場合の数

と定義する。 $dp[i][j]$ を用いると $N$ 人のうち $j$ 人はすでにグループが決まっているため残りの $N-j$ 人のグループ分けについて考えれば良い。

そのとき

$\displaystyle dp[i+1][j+i] += dp[i][j] * {}_{N-j} \mathrm{C}_i$
$\displaystyle dp[i+1][j+2*i] += dp[i][j] * {}_{N-j} \mathrm{C}_i * {}_{N-j-i} \mathrm{C}_i * \frac{1}{2!}$
$\cdots$

であるから一般的に書くと

$\displaystyle dp[i+1][j+k*i] += dp[i][j] * {}_{N-j} \mathrm{C}_i * {}_{N-j-i} \mathrm{C}_i \cdots * {}_{N-j-(k-1)i} \mathrm{C}_i * \frac{1}{k!}$

である。

細かい注意点としては各グループ数 $k$ は $C \le k \le D$ であることである。 $k \lt C$ なる $k$ については場合の数に含めないが、コンビネーションの累積積の計算は必要。

Submission #4234421 - AtCoder Regular Contest 067

どこに着目して考察するべきだったか

$N$ 人のグループ分けの場合の数を求めたいので、DPとして今分けようとしている人数を状態に持つことは自然な気がする。加えてちょうと $i$ 人でのグループ分けは組み合わせで求めることができるのですでに $i-1$ 人でのグループ分けが完了している、という状態を持つのも自然な気もする。

何がバグっていたか

得た知見(典型ポイント)

漸化式的なDP...(ポイントが難しい)

類題

2019-02-11

AtCoder Regular Contest 098：E - Range Minimum Queries

問題

https://atcoder.jp/contests/arc098/tasks/arc098_c

考えたこと

$K = 1$ だとするともとの数列 $\{A_N\}$ をソートして連続する $Q$ 個の要素の最小値をとればよいことはわかった。これはしゃくとり法とかで $O(N)$ でできる。

選べない数を除々に決めていきたいが、これは小さい数から決めていくのがよさそう。まだ何も除いていない場合は元の数列の一番小さい数を除けば良いので一意に決まるため。

除くということを考える。これは元の数列を分割することに他ならない。分割した数列のうち、数列の要素数を $m$ とすると $m-k+1$ 個まで選ぶことができる。分割した数列から選ぶ数はよってそれぞれの分割した数列から $m-k+1$ 個を選んできて、そのうち小さい数のうち $Q$ 個を選べば良い。

すべての数について分割し計算した後、最小値が解となる。

Submission #4231046 - AtCoder Regular Contest 098

どこに着目して考察するべきだったか

分割した後に、分割した数列それぞれについて、 $m-k+1$ 個選べる...ということが考慮不足だった。

何がバグっていたか

以下のようにすると、元の lists に含まれる list がソートされてしまう。

for (List<Integer> list : lists) {
    Collections.sort(list)
}

今回の場合は

for (List<Integer> list : lists) {
    tmp = new ArrayList<>(list);
    Collections.sort(tmp);
}

とするのがよい

得た知見(典型ポイント)

最大値と最小値の最大化は、最大値の最小化
小さい数から貪欲(自由度の小さいほうから)

類題

2019-02-11

AtCoder Regular Contest 097：E - Sorted and Sorted

問題

https://atcoder.jp/contests/arc097/tasks/arc097_c

考え方

状態を決め打ちできるかどうかが一番重要な考察な気がする。つまり

dp[i][j] := 左から [1,i] までの黒 'B' の数と [1,j] までの白 'W' の数が正しく並べるようにするときの最小のswap回数

と定義すると、その次に置くべき数は一意に決まるのでDPで解を求めることができる。dp[i][j] としたときに 'B' を次に置くのであればその数は i+1 であるし、'W' であれば j+1 である。

よってDPの形は以下のようになる。

dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (黒の i+1 を整列した数列の一番右までswapさせるときの最小の回数))
dp[i][j+1] = min(dp[i][j+1], dp[i][j] + (白の j+1 を整列した数列の一番右までswapさせるときの最小の回数))

次にそれぞれのコストを求めていく。「黒の i+1 を整列した数列の一番右までswapさせるときの最小の回数」について考える。これは位置 k において i+1 よりも大きい数の黒 'B' の数と、位置 k において j よりも大きい数の白 'W' の数の和である。よってそれぞれの色ごとに O(N²) で超えている数の個数を求めて累積和を取ることで位置 k における i(j) よりも大きい数の個数が求められる。

また黒の数 i 白の数 j の位置 k も前計算して求めておくことでDPの遷移のコストが　O(1) で求められるようになった。

Submission #4228636 - AtCoder Regular Contest 097

どこに着目して考察するべきだったか

左から確定状態を決め打ち仮定することで、順に条件を満たす数列のコストが求められることに気づく必要がある。

何がバグっていたか

得た知見(典型ポイント)

左から状態を決めていく
O(n²)のときに dp[i][j] としてDPする

類題

2019-02-10

AtCoder Regular Contest 061：E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題

https://atcoder.jp/contests/arc061/tasks/arc061_c

考え方

まずは問題文の条件通り、路線ごとの駅にノードを対応させてグラフを構築する。駅と会社でそれぞれの頂点の役割が変わってくるので座圧の要領で拡張点に index を付与しておく。

同じ駅で会社が異なる場合はそれぞれ乗り換えすることができるが、単純に各駅に辺を張ると最大で O(会社²) の辺がはられることになり間に合わない。そこで各駅の代表駅のような駅を追加し、代表駅から各会社の同一の駅に辺を張ることで辺の数を O(会社) にする。これがこの問題の本質だと思う。

そのように考えると代表駅からそれぞれの駅に入る場合はコスト 1 の辺、駅から代表駅に出る場合はコスト 0 の辺を張ることになる。また M 本の辺は同じ会社の駅であるからそれぞれの駅についてコスト 0 の辺を張ることになる。このグラフにおいて駅 1 の代表駅からダイクストラ法をして、駅 N の代表駅への最短のコストが解になる。

イメージ図は以下。

f:id:d_tutuz:20190210221812j:plain

実装上の面倒な点としてはそれぞれの頂点に index を張ることである。今回は駅 i で会社 c の場合に以下のようにして index を取るようにした。

       long f(int i, int c) {
            return (long)c << 32 | i;
        }

        void addId(long key) {
            if (map.containsKey(key)) return;
            map.put(key, ++id);
        }

        int getId(long key) {
            return map.get(key);
        }

Submission #4225861 - AtCoder Regular Contest 061

どこに着目して考察するべきだったか

だいたい拡張グラフのダイクストラ法だが、ボトルネックを解消するように別の頂点を構築する、という発想が必要。

何がバグっていたか

得た知見(典型ポイント)

グラフ上の頂点を拡張してダイクストラ法
グラフの頂点を座圧

類題

2019-02-10

「みんなのプロコン 2019」：D - Ears

問題

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d

考え方

まずはすぬけくんが散歩する操作をシミュレーションする。そうすると散歩による操作を数列で表すことができることがわかる。その数列はある性質を持っていて以下のように表される。

0 even odd even 0

イメージ図は以下の通り。言われれば確かにそうなるのは分かるが...

f:id:d_tutuz:20190210195918j:plain

よって、この数列と元の数列 $\{A_L\}$ の差を考える。数列の区切り位置を全探索すること計算量的にできない。DPを考えることにする。

$dp[i][j] := i+1$ 番目までの要素で状態が $j$ であるときの差の最小値

と定義する。 $j$ の状態数が $5$ であることからこのDPを定義することができる。 DPの初期値は

$dp[0][j] = 0\ (0 \le j \le 4)$

でDP遷移は

$dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost(i, k))$

である。 $cost(i, k)$ は $A_i$ を状態 $k$ に割り当てたときの差の最小値である。１例えば、状態が $0$ から $3$ に遷移するのは無駄だが、最適な解にはなり得ないので無視して大丈夫である。

どこに着目して考察するべきだったか

まずは、すぬけくんが散歩する経路をシミュレーションすることが重要そう。次に、散歩するという操作を数列で表すと、一般に 0 even odd even 0 のような形で表されることが分かる。ここまで来ると、この数列と元の数列の差を考えればよい。この数列の区切り位置を全探索することはできないが、DPを考えると解ける。

「こういうゴチャゴチャした状態遷移を扱う問題はそのまんま DP になるイメージがある。*1」らしい。たしかに Tree Burning もごちゃごちゃしていたが、DPを考えると部分点解が自然に浮かぶような気がする。

何がバグっていたか

得た知見(典型ポイント)

シミュレーションで操作を式(数列)に対応させる
ごちゃごちゃした状態遷移をDPでまとめる

類題

B - Tree Burning

*1:みんなのプロコン 2019 D - Ears (600 点) - けんちょんの競プロ精進記録

2019-02-09

AtCoder Regular Contest 081：E - Don't Be a Subsequence

問題

https://atcoder.jp/contests/arc081/tasks/arc081_c

考え方

基本的な考え方は放送解説がわかりやすい。

dp[i] := 位置 i 以降で条件を満たす最小の文字列の長さ

とする。そのとき dp[i] = min(dp[next[i][j]] + 1) となる。next[i][j] は位置 i 以降で文字 c が現れる一番最初の位置の index である。

文字列の長さが求まったら、具体的に dp[0] の長さの文字列を構成することになる。これは、dp[i] の長さを求める過程で最小の長さになったときの文字 c の情報を保持しておくことで何によって最小の長さが求められたか復元することができる。よって rest[i] を位置 i における dp[i] を更新したときの文字としておくと rest[0] から順番に文字の情報を next[0][rest[0]] からたどっていくことで具体的な文字列を求めることができる。

イメージ図は以下の通り。

f:id:d_tutuz:20190209172225p:plain