ABC178-F Contrastの別解

まえがき

regiです。今回はABC178-F Contrastの別解、つまりは私がコンテスト中にどういう解法を用いたかを紹介します。この解法の正当性は時間が取れたら書き足します。

その解法

本問のサンプル1と、説明するのに都合の良い自前のサンプル2つの、計3つのサンプルを例に紹介します。

まずはサンプル1です。

これですね。最初に、A[i]=B[i]を満たす箇所において、A[i]とB[i]に色を塗ります。ここで、数字によって塗る色を変えておきます。そうすると以下のようになります。

この場合はどこもA[i]=B[i]を満たすので、全て何かしらの色で塗られました。

次に、色が塗られているかつ、その色が異なるB[i],B[j]のペアを適当に選び、スワップしていきます。

このとき、必ずA[i]≠B[i], A[j]≠B[j]となるため、A[i],A[j],B[i],B[j]の色を消します。

このスワップを、A[i]やB[i]を塗るために用いられている色の種類数が1種類以下になるまで行います。今は3種類あるので、まだスワップを続けます。なお、種類数が2種類以上である限り、必ずスワップを行うことができるので、どのようなA,Bにおいても、この操作で色の種類数を必ず1種類以下にすることができます。

スワップを行い続けると以下のようになります。

無事に色の1種類以下になったので、ここで操作を終了します。なお、今回のサンプルのように、この操作終了時に色の種類数が0種類になった場合は、この時点で題意を満たすBを得ることができたということなので、これで終了です。

次に以下のようなサンプルを考えます。

これも、塗ります。そうすると以下のようになります。

次に、A[i]やB[i]を塗るために用いられている色の種類数が1種類以下になるまでスワップする操作を行います。そうすると以下のようになります。

色の種類数が1種類以下になりましたが、今回のサンプルでは1種類残りました。

次に、色が塗られているb[i]と、a[j]≠b[i]かつb[j]≠b[i]を満たすjにおけるb[j]を適当に選び、スワップしていきます。

このとき、必ずA[i]≠B[i], A[j]≠B[j]となるため、A[i],スワップ前のB[i]の色を消します。

このスワップは、行うことができなくなるまで繰り返し行います。そうすると以下のようになります。

今回の場合、色の種類数が0種類になったことでスワップを行うことができなくなったため、得られたBは題意を満たします。

最後に以下のようなサンプルを考えます。

 色塗り。

最初のスワップ操作

色の種類数が1種類以下になりました。

次のスワップ操作。

今回の場合、まだ色の塗られているA[i],B[i]が存在しているにも関わらず、スワップを行うことができなくなったため、題意を満たすBは得られません。

チャートにするとこのような流れです。

実際にコンテスト中に(可読性は期待しないでください)この解法を用いてACを取った私のコードです。↓↓

https://atcoder.jp/contests/abc178/submissions/16712437

あとがき

ある程度書けたらとりあえず公開するのと、きちんと書くまで公開しないの、どちらの方が良いのでしょうか。とてもどうでもよいことだが、好きな問題を語るだけの自己満足記事、書きたさある。