【No.020】「ICPC 2016 国内予選 E問題 3Dプリント」
問題文はこちら
1つの候補を1つのノードとみなして、実際に設置したとき共通部分をもつもの同士にエッジを張ります。エッジのコストは、
S*S*12 - (その2つを重ねて設置してできる多面体の表面積)
にします。※この2つを設置することで全体の表面積がいくつ減らせるかを表す値です。
あとはこのグラフの中で長さKのパスか閉路の中でコストの和が最大のものを探索することで解くことができます。
問題文に書いてある3条件をよく読むと、簡単な深さ優先による全探索でも計算量が全く増えないことがわかります。
下の図は、2つの直方体を設置して、それを1つの多面体として見たとき、その多面体の表面積を求めるときの例として僕が作った図です。
上からみると、面積は4、正面からみると3、横からみると2なので、
表面積は ( 4 + 3 + 2 ) × 2 = 18 となります。
この方針なら、それぞれの直方体のペアに対して、O(1)で計算できます。
僕が実際に本番で書いたコードです。
