AtCoder Grand Contest 028 A～C

AtCoder Grand Contest 028

AtCoder Grand Contest 028 解説放送 - YouTube

A - Two Abbreviations

• 長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$
• 以下の条件を満たす最短の文字列 $X$ の長さ $L$ を求めよ
  • $L$ は $N$ でも $M$ でも割り切れる
  • $X$ を1文字目から $\frac{L}{N}$ 文字ごとに読むと $S$ になる
  • $X$ を1文字目から $\frac{L}{M}$ 文字ごとに読むと $T$ になる
• 存在しなければ'-1'を出力

S = ae
T = acp
↓
X = accept
    a  e
    a c p

存在するなら $L$ は $N$ と $M$ の最小公倍数となる。

「$X$ の $i$ 文字目は○○でなければならない」という制約が $S$ 側と $T$ 側から存在する。同じ $i$ に対し、双方からの制約が矛盾すれば不可。

S = abcdef
T = aceg
↓
L = LCM(6, 4) = 12
制約
S:  a.b.c.d.e.f.
T:  a..c..e..g..
    ~     ~     ←制約が共通する箇所
          x     ←矛盾する箇所

これを素直に確認すればよい。

B - Removing Blocks

• 長さ $N$ の数列 $A_1,A_2,...,A_N$
• ここから1つずつ数字を無くなるまで取り除いていく
• 取り除くコストは、以下の通りである
  • $A_i$ を取り除く時、その連結成分の $A_k$ の総和のコストがかかる
  • $x$ と $y$ が連結であるとは、$x～y$ の間の数字がまだ1つも取り除かれていないことを示す
• さて、ここで取り除く順番は $N!$ 通りある
• 全ての取り除き方のコストの総和を求めよ

数列 1 2 3 4 5 6
     1   3 4 5 6  2を除去→123456 のコスト 21
     1   3   5 6  4を除去→  3456 のコスト 18
     1   3     6  5を除去→    56 のコスト 11
     1         6  3を除去→  3    のコスト  3
     1            6を除去→     6 のコスト  6
                  1を除去→1      のコスト  1 計 60

これを、$N!$ 通りの全ての順序で実践した総和を求める

答えは、$c_1A_1 + c_2A_2 + ... + c_NA_N$ のような形になる。$c_i$ は、$A_i$ のコストが $N!$ 通りで総計何回足されることになるか。

$c_i$ は $A_i$ の値には関係なく $N$ と位置のみによって決まるので、まずこれを求めて、最後に $c_iA_i$ を計算して足し合わせることにする。

どうやって求めるか。一発でたちどころに求まるようなものでもないので、何らかの基準で問題を分割したい。

何回目に取り出されるか？ など動的計画法でうんうん考えていたが、$O(N^2)$ の計算量からなかなか減らせない。

ここでは、$i,j$ について「$i$ を取り除く時、$j$ のコストが反映される場合の数 $d_{ij}$」を考えるとよかったようだ。

$j$ を固定して $i=1～N$ について $d_{ij}$ を求めると、$c_j = \sum_i{d_{ij}}$ で求められる。これは漏れなく、ダブり無く数えられている。

1  2  3  4
c3 = 1 を除いた時に 3が反映される場合の数 d(1,3)
   + 2 を除いた時に 3が反映される場合の数 d(2,3)
   + 3 を除いた時に 3が反映される場合の数 d(3,3)
   + 4 を除いた時に 3が反映される場合の数 d(4,3)

コストが反映されるためには、$i$ を取り除くまで、$i+1～j$ のどの数字も取り除かれていてはいけない。$k=|i-j|$ とすると、

• 全体の場合の数＝$N!$
• $i～j$ の区間の取り除き方＝$(k+1)!$ 通り
• $i～j$ の区間で、$i$を最初に取り除く場合の数＝$k!$ 通り
• よって、$d_{ij}=\frac{N!k!}{(k+1)!}=\frac{N!}{k+1}$

このように、$d_{ij}$ は $N$ と $k=|i-j|$ のみによって決まる。$d_{1,3} = d_{2,4} = d_{3,5}$ である。

$e_k=d_{ij}$ で表すことにする。

            1  2  3  4
d(1,3) e(2) *     *
d(2,3) e(1)    *  *
d(3,3) e(0)       *
d(4,3) e(1)       *  *

$e_k$ の並び方に着目すると、ある $j$ について $c_j$ を求めるのに必要となる $k$ は連続している。

言い換えると、$j$ の左にある数字の個数を $l$、右側を $r$ とすると、$c_j=e_l+e_{l-1}+...+e_1+e_0+e_1+...+e_r$ となる。

よって、$k=0～N-1$ について$e_k$ を求め、累積和を事前計算しておくと、各 $j$ について $O(1)$ で $c_j$ を求められる。

後は $A_j$ とそれぞれ掛け合わせ、MOD をとればよい。

C - Min Cost Cycle

• $N$ 頂点の有向完全グラフ
• 各頂点には、$A_i, B_i$ の2つの数字が与えられている
• 頂点 $u \rightarrow v$ の辺のコストは、$\min(A_u,B_v)$
• ハミルトン閉路（全頂点を訪れて戻ってくるルート）の、最短コストを求めよ
• $2 \le N \le 10^5$

まず、Dijkstraなどの最短経路探索に落とし込む方法は、総計 $N(N-1)$ 本の辺が張られることになるため、計算量・空間量的に不可能。

全頂点間に辺が張られているので、各頂点で「$A_i,B_i$ が採用されるか」を決めれば、（ある例外に注意すれば）好きなように閉路を構築できることを利用する。

頂点で採用されるコストは4パターンに分けられて、

1. $A_i$ も $B_i$ も共に使用される
2. $A_i$ のみ使用される
3. $B_i$ のみ使用される
4. 両方使用されない

頂点$u$ のパターンと、その次の頂点$v$ のパターンは、$Bu,Av$ のどちらか一方のみが採用されていないといけないことを踏まえると、遷移は以下のようになる。

よって、閉路を作ることが可能なパターンの組は、以下のいずれかとなる

• 全頂点がパターン2
• 全頂点がパターン3
• パターン1と4が同数で、かつ最低1つは存在する（採用するコストを $N$ 個選べば自動的に同数になるため、注意すべき条件は「最低1つ」）

$A_i,B_i$ をまとめて $2N$ 個をソートし、小さい方から $N$ 個を取ったものが、基本的には答えとなる。

ただし、小さい方から $N$ 個を取った結果、閉路が作れないパターンの組み合わせが出てくる。それは「パターン2と3が混在しているが、パターン1や4が存在しない」状態で、その場合のみ微調整の必要がある。

微調整とはいっても、1つだけ組み替えて、パターン1(と4)を1つ作ればよい。

$N$ 個取った結果パターン1の頂点が存在しない⇒選ばれた $N$ 個の頂点は全て別々、選ばれなかった方も全て別々なので、選ばれた方と選ばれなかった方から1つずつ取り、入れ替えればよい。

基本的にはコストのソート結果の$N$番目と$N+1$番目を組み替えればよい。

しかし、$N$番目と$N+1$番目が同じ頂点由来であった場合は、単にその頂点のパターン2がパターン3に（あるいは逆に）なっただけでパターン1が作られない。

その場合は、「$N-1$番目と$N+1$番目」「$N$番目と$N+2$番目」の、コストがより小さくなる方を組み替えればよい。