AOJ 2703 - サイコロスタンプ
解法
あらかじめ、番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。
- サイコロの集合について、これらを最適な順番で転がした際に得ることができる得点の最大値
とすると、答えはです。
の求め方について考えます。
の中で、番目のサイコロを最後に転がした、ということを考えてみます。
このとき、と、番目のサイコロが通る座標で重複する部分があれば、から差し引かなければなりません。
ところが、重複する座標に今どの数字が書かれているか、というのはこれらの情報からは読み取ることができません。
ということで次に逆順、つまり、を最初に転がしたとき、について考えてみます。
このとき、と、番目のサイコロが通る座標が重複する部分について考えてみると、その座標に何がかかれていようが、番目のサイコロがその座標に書き込む数字は別のサイコロによって上書きされてしまいます。
ということで、の中で、最初にを転がした際に得られる得点の最大値は、
となります。
は、上記の計算をについて計算したうちの最大値となります。
です。自分は座標管理にmapを用いたので、が付きます。