ARC121 参加記録 - Xenous の精進記録

コンテストから時間あけてしまいました。
1完 95分でした

A - 2nd Greatest Distance

40分ごろに提出できそうでしたが、だいぶ遅かったため B問題を解いたタイミングで出すようにしました。(失敗しましたが...)

$N$ 個の点があり、点 $i, j$ の距離が $\max{(|x_{i} - x_{j}|, |y_{i} - y_{j}|)}$ で定められています。距離の定義から、 $x$ 軸方向と $y$ 軸方向別々に見ても良さそうですね。それぞれでもっとも遠いところから2番目を考えます。

気になるパターンは、 $x$ 軸と $y$ 軸を別々に比べたときに、実は同じ頂点を見ていた、という場合です。 $x$ 軸で調べた値と $y$ 軸で調べた値を並べてしまうとこのようなことが起こります。場合分けを考え始めると煩雑になるため、間違いなく二番目の頂点が含まれている部分まで候補の点を出し、その中で全探索します。

$x$ 軸で考えます。もっとも遠いのは左端の頂点と右端の頂点をとってきた場合です。その次に短いのは、右端の代わりにその一つ手前の頂点を取ること、左端の代わりに次の頂点をとることになります。従って、候補はこの時点で三つ出てきます。

$y$ 軸も同様に考えたとき、頂点を集合で管理すれば、最小三つ、最大六つになります。この中で定義通りの距離を求めて二番目を求めればOKです。

B - RGB Matching

この問題の教訓は、Counter 使う前に sort しろ、です。もったいない。。

R, G, B の各色について、それぞれ同色が2つずつペアにできれば不満度は 0 です。つまり、各色の個体数が偶数なら 0 です。

次に、そうでない場合というのは、偶数、奇数、奇数のパターンしかありません。合計が偶数になるためです。従って、色によらずこの一つのパターンだけ考えればOKです。以下では、R(偶数)、G(奇数)、B(奇数)とします。

このとき、ペアにならない犬について不満度が小さくなるような組み合わせを見つけます。以下の2つの場合が考えられます。

GのあまりとBのあまりをくっつける
GのあまりとR、BのあまりとR をくっつける

あらかじめ、R、G、Bにおいて、どの値が何個あるかを数えておきます。例えば G の不満度の値を固定して、その値を B のとりうる不満度の列で二分探索し、もっとも差が小さくなるものを見つけます。

これを上記の2パターンでやって、小さい方が答えです。

実装では、個数のカウントに collection.Counter() を使います。辞書型のオブジェクトで、.keys() でキーを取得できます。これに対して二分探索をするのですが、事前にソートしておけば、.keys() の値もソートされた状態で取得できます。