第17回日本情報オリンピック　予選４

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

解説

まずはすべての切り方を試すことを考える．切り方の候補は全部で 2^(N-1) - 1 個ある．1 つの切り方に対して，例えば単純なループ処理を用いることで O(N^2) 時間でピースの長さの最大値と最小値の差を計算することができる．よって全体で O(2^N * N^2) 時間で処理することができるから小課題 1 が解ける．

ピースの長さとして許される最小値と最大値をあらかじめ決めておく．すると，動的計画法を用いることで「実際にそのようにピースを切り分けることができるかどうか」を高速に判定することができる．

たとえば dp[i] を「水ようかんの左端から，i 番目の切れ目までの部分を考えたとき，実際にうまく切り分けることができるか」という真偽値として定義すると，dp[i] は dp[1] から dp[i-1] までの値を用いることで O(N) で計算できる．水ようかんの右端を N 番目の切れ目とみなして dp[N] までを順番に計算すると，dp[1] から dp[N] までを全体で O(N^2) 時間で計算でき，また dp[N] が全体の答えとなることから，結果として O(N^2) 時間で全体をうまく切り分けられるかどうか判定ができる．

ピースの長さとして許される最小値の候補は 1 から水ようかん全体の長さで，最大値の候補は最小値 + max{L_i} までである．これは，自明な切り分け方として「すべての切れ目で切断する」というものがあるため，最終的な答えが必ず max{L_i} 以下になるためである．

最小値および最大値の候補のペアは O( (max{L_i})^2 * N ) 個あり，それらすべてを試すことで全体として O( (max{L_i})^2 * N^3 ) 時間で計算できるから小課題 2 が解ける．

ピースの長さとして許される最小値のみをあらかじめ決めておく．すると，動的計画法を用いることで「うまくピースを切り分けたときの『ピースの長さの最大値』の最小値」を高速に計算することができる．

たとえば dp'[i] を「水ようかんの左端から，i 番目の切れ目までの部分を考えたとき，うまく切り分けたときのピースの最大の長さ」という整数値として定義すると，dp'[i] は dp'[1] から dp'[i-1] までの値を用いることで O(N) で計算できる．dp'[N] が全体の答えとなるから，全体として O(N^2) 時間で値が求められる．

ピースの長さとして許される最小値の候補は 1 から水ようかん全体の長さであるから O(max{L_i} * N) 個ある．よって各最小値の候補を試すと全体で O(max{L_i} * N^3) 時間で計算できるから小課題 3 が解ける．

実際にはピースの長さとして許される最小値の候補はもっと少ない．具体的には「水ようかんのうちある切れ目からある切れ目までの長さ」しか候補になれない．これは O(N^2) 個しかないから，全体で O(N^4) 時間で解ける．