https://codeforces.com/contest/1038/problem/E
左右に色が塗られたブロックがある。このブロックを同じ色どうしを接触させるようにつなげるとブロックに書かれている数字の和がスコアになる。与えられたブロックで得られる最大のスコアを求めよ。
[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2] ←これは63点。
色が4種類しかないので、4つの頂点を持つグラフを考える。すると、色$c_1, c_2$のブロックはそれらの頂点を結ぶ辺と考えることができ、好きな頂点からこれらの重みつき辺をたどって得られる最も大きいスコアが求める答えである。
自己ループ(両端に同じ色が塗ってあるブロック)はその色の頂点を1度でも通ればすべて使えるので、「頂点が持っているスコア」と考えることができる。
ブロックに左右の区別はないため、自己ループを除けば全部で$_4C_2=6$種類しかなく、重要な事実として、この中から同じ種類の辺を2つ以上捨てると最適にならない（たとえば色1,2を持つブロックを2つつなげれば自己ループのように扱うことができるため、validなブロックの塊を作れるかどうかはそれぞれの種類のブロックの数の偶奇のみに依存する）。しかし、4つの頂点がいくつかの連結成分に分かれている場合は使わない連結成分のブロックはすべて捨てなければならないためその限りではない。
それぞれの種類のブロックは高々1つまでしか捨てないことがわかっているので、どの種類のブロックを捨てるかということをbit全列挙で全通り試せばよい。捨てるブロックが決まれば、その種類のブロックのなかで最もスコアが低いものを捨てることになる。残ったブロックを全部使ってvalidなブロックの塊を作れる条件は、残ったブロックで構築したグラフにオイラー路が存在する(次数が奇である点が2つ以下である）ことである。ただし、この問題では4つの点が異なる連結成分に分かれることを考慮しなければならないので、Union-Findを使って残ったブロックから連結成分を併合し、0~3それぞれをrootとする頂点を含む辺だけでグラフを構築することを行った。あとは、できたもののなかからスコア最大のものを出力すればよい。
まずコンテスト中に色が高々4つしかないことに気づけなかった時点でいろいろ厳しいのだが、気づいていたら解けていたかというと怪しい。