競プロ参戦記 #29 「最小全域木」 | KEYENCE 2019 [ABCE]

KEYENCE 社主催のコンテストです。手を付けた問題の考察を書きます。

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

問題リスト: https://atcoder.jp/contests/keyence2019/tasks

A - Beginning

問題概要: 4つの数が与えられる。並び替えて 1, 9, 7, 4 にできるか判定せよ

考察: 4つの数を配列に入れてソートし、 1, 4, 7, 9 になるか調べればOK。

筆者の実装 [AC]: https://atcoder.jp/contests/keyence2019/submissions/4001280

B - KEYENCE String

問題概要: 文字列 S が与えられる。連続した範囲を1つ除去して "keyence" と一致させられるか判定せよ。

考察: 例えば kHOGEeyence や keHOGEyence のような文字列ならOK。

以下のいずれかが成り立てば条件を満たします。

- keyence で終わる、または
- k で始まり eyence で終わる、または
- ke で始まり yence で終わる、または
- ...
- keyenc で始まり e で終わる、または
- keyence で始まる

逆に、この条件を満たすならもとの条件も満たします。

筆者の実装 [AC]: https://atcoder.jp/contests/keyence2019/submissions/4000995

C - Exam and Wizard

問題概要: 長さ N の整数列 A, B が与えられる。C を長さ N の整数列とする。A の総和と C の総和は等しいとする。すべての i について C(i) ≥ B(i) を満たすとする。このような C が存在するか判定せよ。存在するなら、 A(i) ≠ C(i) となる i の個数の最小値を求めよ。

考察: C(i) ≥ B(i) の条件から、 C の総和は B の総和以上です。そのため A の総和が B の総和より小さければ、 C は存在しません。逆に、A の総和が B 以上なら、C(i) = B(i) + n とおくことで数列 C を構成できます。

C が存在するかどうかは判定できたので、 i の個数の最小値について考えます。

A(i) - B(i) の値が大きい i から A(j) < B(j) となる j に値を「移動」させることで C(i) ≥ B(i) の条件を満たすようにします。これは A(i) - B(i) の値が大きい要素を書き換えて (C(i) ≠ A(i) にして) 移動させたほうが、より少ない数の要素を触ることになるので最善です。

筆者の実装 [AC]: https://atcoder.jp/contests/keyence2019/submissions/4000549

E - Connecting Cities

問題概要: N 個の点からなるグラフがある。点 i と j の間に辺を張るとしたら、その辺にはコスト |i - j| * D + A(i) + A(j) がつく。グラフに N-1 本の辺を加えて連結にした。コストの最小値を求めよ。

考察: いわゆる最小全域木のコストを計算する問題です。最小全域木といえばプリム法やクラスカル法ですが、どちらも最悪計算量が E (= N^2) 以上なのでダメです。

ある点をそれより左の点と繋ぐときにコストが最小になる相手、というのを計算します。これは単純なループでできます。

右の点と繋ぐ場合についても同様に計算すると、使うべき辺は各点につき左右2本に絞られます。

この時点でグラフの辺の本数が最大 O(N) になったので、最小全域木を求める一般的なアルゴリズムを使えば終わり……というのが公式の解説の方針ですが、私は思いつかなかったので、もう少し続けます。

点を繋ぐ相手を計算するとき、ループ (点からその点自身へ辺) を考えてもいいことにします。つまり、「左にある、繋ぐときのコストが最小の点」を、ループと比較して順繰りに求めていきます。

この処理で最小値が更新されるケース、つまり点 i を i より左の点と繋ぐよりループで繋ぐほうがコストが低いケースというのは、 i より右の点を i より左の点と繋ぐ理由がない (i と繋いだほうが良い) 状態です。(ここが解法の最重要ポイントだと思ってました)

右も同様に計算します。

そうすると、A[i] が最小の点や、最小ではないけど周りより十分に小さい点では、左右どちらへの辺よりもループのほうがコストが低いです。こういう点を極小点と呼ぶことにします。

残りの点は左か右の極小点のうちコストが低い方と繋ぎます。これによって極小点を根とするいくつかの木に分割されます。後は極小点同士を順番に繋いでいけば最小全域木のできあがりです。

筆者の実装 [AC]: https://atcoder.jp/contests/keyence2019/submissions/4008324

おわりに

ABC-E 完です。D 問題は一瞬で諦めてしまったので後で解説ACしたいです。レートが +127 も増加し、青コーダーとして幸先のよいスタートになりました。