AtCoder Grand Contest 028 - 情報妖精の競プロ日記

AtCoder Grand Contest 028 (AGC028)に参加しました！
AtCoder Grand Contest 028 旧版
 AtCoder Grand Contest 028 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Grand Contest 028
rated
10/13(土) 21:00 ～ 23:30 (150分)
300-600-700-900-1400-2500(1000) (6問)
ペナルティ: 5分

方針

もうレート落ちなきゃ良いわ(次の日が秋季博麗神社例大祭の為)、300-700解いて終わらせる

A - Two Abbreviations

まず、条件1より最小の $L$ の候補は ${\rm lcm}(N, M)$ です。
この時、任意の $i(0 \leq i < \gcd(N, M))$ に対して $N$ の $i \times \frac{N}{\gcd(N, M)} + 1$ 番目と $M$ の $i \times \frac{M}{\gcd(N, M)} + 1$ 番目は同じ位置になる為、この文字が同じである必要があります。
ところで、全ての $L$ の候補は ${\rm lcm}(N, M)$ の定数倍ですが、何倍にしても同じ位置になる文字は同一です。
よって、 ${\rm lcm}(N, M)$ のみを愚直に調べれば良いので、計算量は ${\rm O}(N+M)$ です。
ちなみに、 ${\rm lcm}(N, M)$ は最大で $NM \leq 10^{10}$ になるため、オーバーフローには注意しましょう。

B - Removing Blocks

全てのコストの合計……のような、全通りの合計を行った場合は左→右と右→左の両方が含まれるので、順番を考慮しなくていいことに注目します。
まず、そのままだと分かり辛いので仮に左端の1個についてコストを計算するものとしましょう。
この時、まず自分自身とは必ず連結しているので、自分自身は $N!$ 回のコストが足されます。
次に、隣のブロックと計算する場合、自分が先に選ばれた場合のみコストが足されるので $\frac{N!}{2}$ となります。
同様に $j$ 個離れたブロックについては、全 $j+1$ 個のブロックの中で自分が最初に選ばれた時のみコスト計算するので $\frac{N!}{j+1}$ 回となります。
ということは、左から $i$ 番目のブロックのコストは $\frac{N!}{i-1}+\frac{N!}{i-2}+\cdots+\frac{N!}{1}+\frac{N!}{2}+\cdots+\frac{N!}{N-i+1}=\sum_{j=1}^{i-1}\frac{N!}{j} + \sum_{j=1}{N-i+1}\frac{N!}{j} - N!$ 回計算されるので、この値に $A_i$ を掛ければ良いです。
この計算は、累積和を用いて $\sum_{j=1}{k}\frac{N!}{j}$ を予め求めておけば ${\rm O}(1)$ で出せるので、後は全ての $i$ に対して計算すれば ${\rm O}(N)$ で求めることができます。

C - Min Cost Cycle

まず、制約より丁度 $N$ 個の重みの総和が答えになることが分かります。
理想は重みが小さいもの $N$ 個のみで構成することですが、それは可能でしょうか？
まず、各頂点について重みの計算は次の4通りが考えられます。

$A_i$ と $B_i$ のどちらも使われない
$A_i$ が使われ、 $B_i$ が使われない
$B_i$ が使われ、 $A_i$ が使われない
$A_i$ と $B_i$ のどちらも使われる

さて、今重みの小さいもの $N$ 個を仮に取った場合を考えましょう。
この時、接続可能な遷移はどれでしょうか？
列挙すると、 $1 \rightarrow 2$ 、 $1 \rightarrow 4$ 、 $2 \rightarrow 2$ 、 $2 \rightarrow 4$ 、 $3 \rightarrow 1$ 、 $3 \rightarrow 3$ 、 $4 \rightarrow 1$ 、 $4 \rightarrow 3$ の8通りあります。
ここで、鳩の巣原理より必ず1のパターンと4のパターンは同数個あることに着目すると、 $1 \rightarrow 4 \rightarrow 1 \cdots$ と繰り返すことで1及び4の個数は任意に減らすことができます。
また、 $1 \rightarrow 2 \rightarrow 2 \rightarrow \cdots \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 3 \rightarrow \cdots \rightarrow 3$ 、あるいはその逆を行うことで1か4のパターンが存在すれば2と3の個数も任意に減らすことができるので、もし両方が使われる場合はその瞬間に最小の重み $N$ 個を選べば良いことになります。
後は2と3のみが存在するパターンを考えます。
まず、遷移を見れば分かるように2のみ、3のみの場合は問題なく解けます。
逆に、そうでない場合はどうやら最小の重み $N$ 個では解けないようです。
そこで、この場合は仕方ないので第 $N+1$ 番目の重みのものを追加し、第 $N$ 番目のものを除外することで解けます。
……と、第 $N$ 番目と第 $N+1$ 番目が同じi番目の辺だと意味がないので、この場合は第 $N$ 番目を外して $N+2$ 番目の重みの頂点に変更するか第 $N-1$ 番目を外して $N+1$ 番目の頂点に変更するか、好きな方(というかより小さい方)を選びましょう。
計算量はソートしてから貪欲なので ${\rm O}(N \log N)$ です。