![解法
● さっきの列を a[1], a[2], … とする
● dp[i][w] := ( a[i] まで見ていて、ここまでの
コストが w であるときの最大価値 )
– ただし、行きに往復分のコストを払い、帰りはコスト 0 と
思う](https://image.slidesharecdn.com/sanpo-130313021313-phpapp01/85/Sanpo-7-320.jpg)
![解法
● DP の遷移は ( a[i-1] → a[i] が下りの辺のとき )
dp[i][w] := max(dp[prev[i]][w],
max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } )
● ここで、
– prev[i] := ( j ＜ i かつ a[i] == a[j] となる最大の j )
– t_i := ( 辺 a[i-1] → a[i] のコスト )
– m_i := ( 辺 a[i-1] → a[i] の価値が得られる回数の上限 )
– v_i := ( 辺 a[i-1] → a[i] の価値 )](https://image.slidesharecdn.com/sanpo-130313021313-phpapp01/85/Sanpo-8-320.jpg)
![解法
dp[i][w] := max(dp[prev[i]][w],
max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } )
● 部分木 a[prev[i]], …, a[i-1] を無視することを表す
遷移](https://image.slidesharecdn.com/sanpo-130313021313-phpapp01/85/Sanpo-9-320.jpg)
![解法
dp[i][w] := max(dp[prev[i]][w],
max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } )
● 辺 a[i-1] → a[i] を c/2 回往復することを表す遷移](https://image.slidesharecdn.com/sanpo-130313021313-phpapp01/85/Sanpo-10-320.jpg)
![解法
● 以上を素直に実装すると、O(NTM) かかり、TLE し
てしまう
– M := max{ m_1, m_2, …, m_{N-1} }
● DP の更新式
dp[i][w] := max(dp[prev[i]][w],
max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } )
をよく見てみると...](https://image.slidesharecdn.com/sanpo-130313021313-phpapp01/85/Sanpo-11-320.jpg)
Sanpo
- 1. さんぽ 原案 : komiya, fura2 解答 : komiya, fura2 解説 : fura2
- 2. 問題概要 ● N 頂点の木がある ● 辺 i を通ると、m_i 回目までの通行ではスコア v_i が得られる。m_i+1 回目以降は何も得られない ● また、辺 i には通行に必要なコスト t_i がある ● 頂点 1 からはじまり頂点 1 で終わるような、合計コ スト T 以下のウォークで、得られるスコアの合計を 最大化せよ
- 3. 例 T=15 1 1/10 3/1 2 5 8/777 3/1 4 3 (コスト/☆の価値)
- 4. 例 ● 答えは 10 + 10 + 10 + 1 + 1 = 32 T=15 1 1/10 3/1 2 5 8/777 3/1 4 3 (コスト/☆の価値)
- 5. 解法 ● DP です – 以下、詳しく説明します ● 当分の間、説明を簡単にするため、m_i は正の偶数で あるとします
- 6. 解法 ● 考えやすくするため、木を列にしておく – 根から DFS して、頂点を通った順に並べる。(Euler tour technique) 1 2 5 4 3 1 2 3 2 1 4 1 5 1
- 7. 解法 ● さっきの列を a[1], a[2], … とする ● dp[i][w] := ( a[i] まで見ていて、ここまでの コストが w であるときの最大価値 ) – ただし、行きに往復分のコストを払い、帰りはコスト 0 と 思う
- 8. 解法 ● DP の遷移は ( a[i-1] → a[i] が下りの辺のとき ) dp[i][w] := max(dp[prev[i]][w], max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } ) ● ここで、 – prev[i] := ( j ＜ i かつ a[i] == a[j] となる最大の j ) – t_i := ( 辺 a[i-1] → a[i] のコスト ) – m_i := ( 辺 a[i-1] → a[i] の価値が得られる回数の上限 ) – v_i := ( 辺 a[i-1] → a[i] の価値 )
- 9. 解法 dp[i][w] := max(dp[prev[i]][w], max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } ) ● 部分木 a[prev[i]], …, a[i-1] を無視することを表す 遷移
- 10. 解法 dp[i][w] := max(dp[prev[i]][w], max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } ) ● 辺 a[i-1] → a[i] を c/2 回往復することを表す遷移
- 11. 解法 ● 以上を素直に実装すると、O(NTM) かかり、TLE し てしまう – M := max{ m_1, m_2, …, m_{N-1} } ● DP の更新式 dp[i][w] := max(dp[prev[i]][w], max{ dp[i-1][w-c*t_i]+c*v_i | c=2,4,…,m_i } ) をよく見てみると...
- 12. 解法 ● ナップザック問題の DP と同じだ！ – しかも c=2,4,…,m_i なので、これは個数制限つ きナップザック ● 個数制限つきナップザックの高速化はよく知られて います – m_i を 2, 4, 8, … と O(log m_i) 個に分割する – あるいは、スライド最小値を使う どちらも蟻本に載っています
- 13. 解法 ● というわけで、 ● さっきの DP は O(NT log M) または O(NT) で計 算できます ● これで間に合う
- 14. コーナーケース ● m_i が奇数のときは、全部の☆を拾うケースがあ るので、DP の遷移がひとつ増える。( サンプルに あります ) ● m_i = 0 のときは、☆を拾わずに i を進める遷移が 増える
- 15. 提出状況 ● AC Rate – 20.00 % (1/5) ● First Acceptance – Onsite: magyorin (269 min) – All: magyorin (269 min)