Educational Codeforces Round 74 (virtual) 解法

コンテストページ

https://codeforces.com/contest/1238

解法

✔A - Prime Subtraction

差が 1 のときだけ NO です。

✔B - Kill `Em All

A を降順に並べて同じものも消します。直接攻撃をするのは、大きいものから順で良いですから、攻撃する人数を全探索です。

✔C - Standard Free2play

足場があることを ✔、ないことを ✖ と呼びましょう。

使う予定の石はギリギリまで使わないとすると、状態は高さだけです。一般に、✔ ばかりのところは 2 ずつ、✖ ばかりのところは 1 ずつノーコストで進めます。 ✖が終わったら自然な流れで ✔ に入れますから、問題は ✔ -> ✖ です。高さ 1 まで続いているものはノーコストです。番兵を入れておいて、来たら 1 個前が 1 かどうかを見て、そうならばスルーをしましょう。

途中から始まったものは、まずは 1 つ前に着地をするところから始まります。目の前が ✖ な状態で終わりたいですから、ここを入れて偶数個の「間」が欲しいです。したがって、もとの状態で偶数この ○ が続いていればよいです。そうでなければ +1 です。

初めから続いているものは、1 つ前から始まりませんから、偶奇が入れ替わります。奇数個の ○ が続いていればよいです。偶数個ならば +1 です。これは、初めの足場をノーカンにすることで計算があいます。ノーカンにした結果初めの島がなくなったとしても、もともと奇数個でノーコストなのでよいです。

DP でも座標圧縮と行列累乗で解けて、そちらのほうが正当化は楽なのですが、実装が少し大変です。

✔D - AB-string

Bad をカウントして、n(n-1)/2 から引きましょう。 Bad な原因は必ず端っこです。形は ABBBBB のようなものしかありません。そこで、RLE をして重複度を計算し、隣接しているものから x+y-1 です。

✔E - Keyboard Purchase

どこかで類題を見ました。

キー配列を左から順に決めて、既に決まった場所の中での移動コストと、そこに出入りするコストの合計を DP です。遷移は、dp[ bs | 1<<i ] |= dp[bs] + a[ bs | 1<<i ] と書けます。a は出入りコストです。

出入りコストは、パスワード中の相異なる隣接する 2 つの文字 'a'+i, a'a+j に対して、 i と j のいずれか一方のみを含むような bs について a[bs]+=1 をしたいです。しかしこれでは間に合いませんから、累積和を使いましょう。

a[1<<i]+=1
a[1<<j]+=1
a[1<<i|1<<j]-=2

をして、高速ゼータ変換をした人の勝ちです。

✔F - The Maximum Subtree

条件は、キャタピラグラフであることと同値です。

en.wikipedia.org

極大なキャタピラサブグラフは、2 頂点 u, v を選んで、それをパスで結んで足をたくさん生やしたものですから、ｘ = LCA(u, v) を全探索です。 dp[ 頂点 ] = そこから部分木のどれかの頂点まで結んだパスに足を生やして作れるキャタピラの最大サイズをすると、各点でこれの top 2 を見ると良いです。場合分けを省くために、0 を 2 つ入れておくと良いです。