読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

東京大学プログラミングコンテスト(UTPC)2014 F問題 チェックディジット

http://utpc2014.contest.atcoder.jp/tasks/utpc2014_f
本番中時間がなくて露骨に部分点を狙いにいった問題。
一度見た問題は解かないと気が済まないので満点出すまでやりました。

- 問題概要

10桁の整数がT個与えられます。
整数a_iが入力したとき整数p_iを出力する。
i \neq jのとき
a_i=a_jが成り立つならばp_i = p_jが成り立つよう出力。
(a_iの内隣接する二つの数字を入れ替えたもの)=a_jが成り立つならばp_i \neq p_jが成り立つよう出力をしなければならない
なお得点の関係上、満点を出すには出力する整数の種類を3種類以下に抑える必要がある。

- 解法

この問題は各整数の関係を辺とすることでグラフ問題に帰着できる。
具体的には、012と021は隣接する1と2を入れ替えることで互いの整数に変換することができるため、整数を頂点として無向辺を張ることができる。
また、各整数は整数型でなく文字列として管理すると楽になる。
グラフ問題として考えたとき、隣接する頂点と同じ値は出力してはならない。
したがって、出力する整数を色とするとグラフの彩色問題として考えることができる。


グラフ彩色を行う場合はWelsh-Powel法という貪欲法を用いた彩色アルゴリズムが存在する。
次数の大きい順からできるだけ小さな値(色)を割り当てていくという手法です。
しかし、このアルゴリズムはO(グラフの最大次数+1)であるので3色以下に収まらないケースが存在する。
※UTPCの公式解説ではO(最適彩色数+1)となっているが恐らく間違い

↑恐らくなので合ってるかもしれないです。私には分かりません。
一応反例を以下に示します。

入力
18
0214356789
0213465789
0123546789
0123546879
0125346879
0123564879
0213456789
0123456789
1023456789
1023457689
1203456789
1230456789
2103456789
0123546798
0123546978
0123549678
0123546987
1023546798
これらを隣接グラフに起こすと以下のようになる。
f:id:NitCoder000:20150402171339p:plain
Welsh-Powelアルゴリズムを用いて彩色するとき、
緑、オレンジ、青、ピンクの順で4色に彩色されるパターンが存在する。
f:id:NitCoder000:20150402171059p:plain

そこで、グラフの閉路について考える。
閉路の長さは必ず偶数となるため、必ず2色に彩色できる。
これは証明してないけど直観的に多分正しいはず。

したがって幅優先木(深さ優先木)を作成し、深さ%2の値で彩色していけば満点が得られる。

グラフの作成の際文字列をmapで管理してやればO(10*T\log T)で隣接リストが作成できる。
また、グラフ上の辺の数の最大は10*Tなので彩色も上の計算量以下で実現できる。
実際はmapでの探索の際内部で文字列の比較を行っているのでO(10*10*T\log T)=10^8ぐらいで結構ギリギリ

- ソースコード

http://utpc2014.contest.atcoder.jp/submissions/377763
最初はcoloringの位置がwelsh-powelをする関数だった。
しかしACもらうものの182点しかもらえなかったため反例を考えたら彩色数4のパターンが見つかってしまったためやり直しました。