ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2703 - サイコロスタンプ

問題
提出コード

解法

あらかじめ、i番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。

  • dp[S] = サイコロの集合Sについて、これらを最適な順番で転がした際に得ることができる得点の最大値

とすると、答えはmax(dp[S])です。
dp[S]の求め方について考えます。
Sの中で、i番目のサイコロを最後に転がした、ということを考えてみます。
このとき、S \setminus\{i\}と、i番目のサイコロが通る座標で重複する部分があれば、dp[S \setminus \{i\}]から差し引かなければなりません。
ところが、重複する座標に今どの数字が書かれているか、というのはこれらの情報からは読み取ることができません。
ということで次に逆順、つまり、iを最初に転がしたとき、について考えてみます。
このとき、S \setminus\{i\}と、i番目のサイコロが通る座標が重複する部分について考えてみると、その座標に何がかかれていようが、i番目のサイコロがその座標に書き込む数字は別のサイコロによって上書きされてしまいます。
ということで、Sの中で、最初にiを転がした際に得られる得点の最大値は、
dp[S \setminus\{i\}] + \sum (i番目のサイコロがS\setminus\{i\}と重複せずに書き込む座標の値)
となります。
dp[S]は、上記の計算をi \in Sについて計算したうちの最大値となります。
O(N max(|rot|)2^{N})です。自分は座標管理にmapを用いたので、\logが付きます。