AGC028 参加記録＆解説（A～C）

AtCoder Grand Contest 028 - AtCoder

今回も前回と同じく、速解き1完でレート微減。うーん…

f:id:betrue12:20181014005902p:plain

しっかり復習しましょう。A～Cを振り返ります。

A - Two Abbreviations

解法

※以降の説明では、文字列のインデックスを0始まりで記載します。

まず $X$ の長さ $L$ は $N, M$ の両方で割り切れるという条件があるため、 $L$ は $N, M$ の公倍数です。公倍数は最小公倍数の倍数であるため、 $L$ は $lcm(N, M)$ の正整数倍です。

とりあえず、 $L = lcm(N, M)$ として考えます。 $X$ の中で、文字列 $S, T$ がどこに含まれているかを図示します。

f:id:betrue12:20181014011332p:plain

図のように、 $S$ が1文字進むごとに $X$ は $\frac{L}{N}$ 文字、 $T$ が1文字進むごとに $X$ は $\frac{L}{M}$ 文字進みます。

$X$ の各文字のうち、 $S, T$ のどちらか一方に対応している位置はその文字を採用すればよいですし、どちらとも対応していない位置の文字は好きに決めればよいです。問題は両方に対応している位置で、これらは同じ文字である必要があります。

このように $S, T$ の両方の文字が存在する位置は、 $\frac{L}{N}$ と $\frac{L}{M}$ の公倍数（と0）になります。先ほども書いたように公倍数は最小公倍数の倍数であるため、 $lcm(\frac{L}{N}, \frac{L}{M})$ の0以上の整数倍の位置すべてについて、そこに対応する $S, T$ の文字が一致しているかどうかを調べればよいです。

これで、 $L = lcm(N, M)$ のときの判定ができました。では他の公倍数の場合はどうか？と考えてみますが、他の公倍数は $lcm(N, M)$ の正整数倍です。 $L = k \times lcm(N, M)$ とすると、 $X, S, T$ の対応図は上の図をそっくりそのまま $k$ 倍に「引き伸ばした」ような感じになります。つまりどの公倍数で考えても、比較しなければいけない $S$ と $T$ の文字は同じであり、 $S, T$ に矛盾なく $X$ を構成できるかどうかも同じになります。

そのため上記のように $L = lcm(N, M)$ で調べて、OKであればその値が最小値ですし、NGであればどの公倍数でも $X$ は構成不可能なので-1を出力します。

ACコード

C++のほうが、上の説明に沿って書いています。

B - Removing Blocks

解法

各ブロックについて、「 $N!$ 個の全てのパターンについて合計したときに、ブロック $i$ の重さは合計何回分カウントされるか？」を求めたいです。これを係数として $A_{i}$ に掛けて総和を取ると答えになります。

これをさらに分解し、「ブロック $j$ を取り除くときに、ブロック $i$ の重さは合計何回分カウントされるか？」を考えます。各パターンごとに各ブロックはそれぞれ1回ずつしか取り除かれないため、これは「 $N!$ 個の全てのパターンのうち、ブロック $j$ を取り除くときにブロック $i$ の重さがカウントされるパターンはいくつあるか？」と書き換えられます。

ブロック $j$ を取り除くときにブロック $i$ の重さがカウントされる条件は、取り除く時点で $j$ から $i$ までのブロックが全て存在すること。言い換えると、 $j$ から $i$ までの $|j-i|+1$ 個のブロックのうち、ブロック $j$ が最初に取り除かれることです。このようなパターンの数は $\frac{N!}{|j-i| + 1}$ になります。これは、ブロックを取り除く順番をランダムな事象として考えたときに、 $|j-i|+1$ 個のブロックのうちブロック $j$ が最初に取り除かれる確率が $\frac{1}{|j-i|+1}$ である、と考えたほうが理解しやすいかもしれません。

ここまでの内容を整理すると、

「ブロック $j$ を取り除くときに、ブロック $i$ の重さは合計何回分カウントされるか」は、 $\frac{N!}{|j-i| + 1}$ 。
「 $N!$ 個の全てのパターンを合計したときに、ブロック $i$ の重さは合計何回分カウントされるか？」は、↑を全ての $j$ について合計した $\sum_{j=1}^{N}\frac{N!}{|j-i| + 1}$ 。
答えは、それを係数として $A_{i}$ に掛けて合計したもの。

です。

では、 $\sum_{j=1}^{N}\frac{N!}{|j-i| + 1}$ を求めましょう。 $N!$ は全ての項に共通なので、 $\sum_{j=1}^{N}\frac{1}{|j-i| + 1}$ を求めて一番最後に $N!$ を掛けることにします。これは $i$ の両側それぞれで見ると、 $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots$ という形になっています。この累積和を事前計算しておけば、各 $i$ についてこの値が高速に求められます。

ただしこれは整数での割り算なので、素数modでの逆元計算を行い、その逆元を足し算していきます。逆元の計算についてはこちらの記事によくまとまっています。信頼と実績のけんちょんさん。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜

これで材料が揃いました。解法をまとめます。

素数modでの逆元計算を用いて、 $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots$ の累積和を計算しておく。
各 $i$ について、累積和を使って $\sum_{j=1}^{N}\frac{1}{|j-i| + 1}$ を計算する。
上記結果を係数として $A_{i}$ に掛け、加算する。
最後に後回しにしておいた $N!$ を掛ける。

ACコード

C - Min Cost Cycle

解法

ある頂点の $A_{i}$ と別の頂点の $B_{j}$ がペアになり、 $N$ 本の辺を構成します。このとき、重みの小さいものをなるべくばらけさせたいです。特に、 $A_{i}, B_{j}$ を合計 $2N$ 個をごちゃ混ぜにソートして、小さいほうから $N$ 個を $N$ 本の辺にばらけさせることができれば、これが最適です。

ただし問題では「全ての頂点を1度ずつ通るサイクルを構成すること」が要求されています。 $A_{i}, B_{j}$ から重みとして使いたい値を $N$ 個選んだとき、それを $N$ 本の辺にばらけさせて、要求されているサイクルが構成できるでしょうか。

f:id:betrue12:20181014113938p:plain

サイクルを構成できる条件は、上図のようなものになります。一番左のOKパターンは実際に作ってみればいいので分かりやすく、一番右のNGパターンも図のように閉路を作ろうとすると必ず繋ぎ相手がいなくなるので分かりやすいです。真ん中のパターンが必ずOKというのはちょっと難しいのですが、「Aを使うもの」と「Bを使うもの」をそれぞれ固めて、その間を「AもBも使うもの」と「AもBも使わないもの」で上手く繋ぐようにするとサイクルを構成できます。（図では要素数が少ないですが、一応そのように構成しています。）

これでやることが決まりました。OKパターンを満たすように、その中で $A_{i}, B_{j}$ の合計がなるべく小さくなるように $N$ 個を選びます。

ということで、まず小さい方から $N$ 個選んでしまいましょう。この $N$ 個がOKかNGかを確認します。

OKパターンだった場合
- 何の問題もありません。そのまま出力します。
NGパターンだった場合
- この場合、取る値を変更しないといけません。2番目に合計が小さくなるのは、 $1, 2, ..., N-1, N+1$ 番目を選んだ場合です。これがOKパターンならこれが答えです。ただこれも、NGパターンになることがあります。

最後の詰めです。 $1, 2, ..., N-1, N$ 番目も $1, 2, ..., N-1, N+1$ 番目もNGパターンになるというのはどういう状態でしょうか。

f:id:betrue12:20181014113206p:plain

$1, 2. ..., N-1$ 番目を選んだ状態から、 $N$ 番目を選んでも $N+1$ 番目を選んでもNGになる場合、これらの2つの値は同じ頂点に属しています。これがとても重要です。

次の候補を考えます。 $1, 2, ..., N-1, N+1$ 番目がNGとなると、次に重み合計が小さくなるのは

$1, 2, ..., N-1, N+2$ 番目
$1, 2, ..., N-2, N, N+1$ 番目

のどちらかになります。このときこれら2つはどちらも、「 $N$ 番目と $N+1$ 番目は同じ頂点に属している」ということを使ってOKパターンになることが示せます。

$1, 2, ..., N-1, N+2$ 番目を選ぶと、同じ頂点に属する $N, N+1$ 番目がどちらも選ばれていない。そのため他の頂点どれか1つ以上で、 $A_{i}, B_{i}$ 両方が選ばれているはずである。
$1, 2, ..., N-2, N, N+1$ 番目を選ぶと、同じ頂点に属する $N, N+1$ 番目がどちらも選ばれている。

つまり、2つをそれぞれ計算して小さい方を出力すればよいです。

解法をまとめます。

各重みをソートし、小さい方から $N$ 個選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
↑がNGパターンの場合、 $1, 2, ..., N-1, N+1$ 番目を選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
↑もNGパターンの場合、以下の2つはともにOKパターンなので、2つのうち合計値が小さいほうを出力して終了。
- $1, 2, ..., N-1, N+2$ 番目
- $1, 2, ..., N-2, N, N+1$ 番目