第18回日本情報オリンピック　予選５

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

解説

まず，それぞれの木にイルミネーションを飾り付けるかどうかをすべて試すことを考える． このような方法は 2^N 通りあり，飾り付け方が条件を満たすかどうかの判定は単純には O(NM) かかるため，このアルゴリズムの計算量は O(2^N * NM) となる． この方法では，10 点を獲得することができる．

より高速な解法として，動的計画法に基づくアルゴリズムがある． たとえば，木 1, 2, ..., N の順に，イルミネーションを飾り付けるかどうかを決めていくことを考える． このとき，「木 L_j, ..., R_j のうち 2 つ以上にイルミネーションを飾り付けてはならない」という条件は，「木 R_j について飾り付けるかどうか決めたとき，イルミネーションを飾り付ける木であって，2 番目に最新のものは，木 L_j より前である」と言い換えられる．

これは，動的計画法の状態として，イルミネーションを飾り付ける木であって，最新のものおよび，2 番目に最新のものの組み合わせをとり，各 j に対して，R_j についての更新後に「2 番目に最新のものは L_j より前」という条件を覚えておくと計算することができる． この方法の計算量は O(N^3 + M) となり，40 点を獲得できる．

木 i を飾り付けたとき，その次に飾り付けることができる木は，ある X_i に対して「番号が X_i 以上の木」として表すことができる． 明らかに，任意の i に対して，X_i は i+1 以上である． 各 j に対し，木 L_j, ..., R_j に対しては X の値は R_j + 1 以上である． 逆に，すべての j に対してこの更新を行った後には，実際にこの値以上の番号を持つ木を飾り付けることはできることがわかる． よって，この値を O(NM) かけて前計算した後，「最後に飾り付けた木の番号」を状態に持つ動的計画法を行うと，O(NM) でこの問題を解くことができ，70 点を獲得できる．

Segment Tree などのデータ構造を用いると，前計算や動的計画法の更新を高速化することができ，O((N+M) log N) などで問題を解くことはできる． ここでは，より簡潔に O(N+M) の計算量で解く解法を紹介する． 前のアルゴリズムにおいて，前計算で各 j に対し L_j についてのみ X の値を R_j + 1 との最大値をとって更新しておき，最後に i = 1, 2, ..., N の順に， X_i を X_{i-1} との最大値をとって更新することで，正しく X_i を求めることができる． また，動的計画法の更新では，「木 i にはイルミネーションを飾り付けずに，以降の木を飾り付けるかどうかを決める」という遷移を許すことで， 木 i にイルミネーションを飾り付けるとき，木 i から 木 X_i, X_i + 1, ... への遷移をすべて試すかわりに，木 X_i への遷移のみを試せばよくなることがわかる． これにより，O(N+M) でこの問題を解くことができ，満点を獲得できる．