第13回日本情報オリンピック　予選６

2013年12月15日
情報オリンピック日本委員会

解説

部分点解法

i 番目の小籠包を p_i 番目に食べるとすると， {p₁, p₂, ..., p_N} は {1, 2, ..., N} の置換である． p₁, p₂, ..., p_N の取りうる値の組み合わせは N! 通りあり，それらを全探索して最良のものを見つける． 1 ≦ i < j ≦ N をみたす (i, j) の組を考える．

• p_i < p_j のとき，もし j - i <= D_i ならば， i 番目の小籠包を食べる際に， 汁が j 番目の小籠包にかかり，おいしさが A_i 増える．
• p_i > p_j のとき，もし j - i <= D_j ならば， j 番目の小籠包を食べる際に， 汁が i 番目の小籠包にかかり，おいしさが A_j 増える．

よってこれらの値を i, j のすべての組について合計することで，最終的なおいしさの合計値が求まる． p の値の取りうる N! 通りの組み合わせについて探索し，各組み合わせについておいしさの合計の計算に O(N²)の時間がかかるので， この解法の計算量は O(N! * N²) である．

満点解法

D₁, ... , D_N の最大値を DMAX とすると，上の解法で， |i - j| ≦ DMAX となる (i, j) の組のみについて調べればよいことになる．すなわち， p_i と p_j の大小関係が問題になるのは， |i - j| ≦ DMAX のときのみである．

よって，小籠包を 1 番目から i 番目までの小籠包についてそれらの中での食べる順番を決めたとき， それ以降の小籠包の食べる順番を決めるのに関わってくるのは， i - DMAX + 1 番目から i 番目までの小籠包(の食べる順番)のみである．したがって，次のような dp テーブルを定義して動的計画法を行えばよい．

dp[i][(q₁, q₂, ..., q_DMAX)] := i - DMAX + 1 番目から i 番目までの DMAX 個の小籠包については，食べる順番が i - q₁, ..., i - q_DMAX となるように， 1 番目から i 番目の小籠包を食べたときのおいしさの和の最大値

ここで 1 ≦ i ≦ N で，q₁, q₂, ..., q_DMAX は {0, 1,..., DMAX - 1} の任意の置換である．

この解法の計算量は，ある 2 変数多項式 poly について O(DMAX! * poly(N, DMAX)) となる．