2つの解法
まず、この問題の模範解答は「遅延評価セグメント木」を使った解法になります。詳しくは、公式解説を参照してください。
一方、もうちょっと素朴に考えると、2種類の解法を思いつきます。
1つは、W 個のマスのそれぞれの高さをリストに記録して、更新していく方法です。
# リスト bricks に区間が（取り出し逆とは逆順に）入っている heights = [0] * (W+1) l, r = bricks.pop() for i in range(l, r+1): heights[i] = 1 print(1) for n in range(2, N+1): l, r = bricks.pop() h = 1 for i in range(l, r+1): h = max(h, heights[i]+1) for i in range(l, r+1): heights[i] = h print(h)
レンガが長いと検索・更新処理に時間がかかるため、公式解説では、座標圧縮、もしくは、セグメント木で効率化する方法が紹介されています。
ただし、（平均的に）レンガが短ければ、このままでも問題ありません。
一方、（平均的に）レンガが長い場合は、ちょっと考え方を変えることができます。区間の幅に対してレンガが長い場合、レンガはどんどん上に積み重なっていくため、新しいレンガを載せる場合、すでに高い位置にあるレンガに重なる可能性が高くなります。
そこで、高さごとにレンガをグループ分けしておいて、高いものから順に重なりをチェックしていけば、最初に重なりが見つかった所で検索を終えることができます。
# リスト bricks に区間が（取り出し逆とは逆順に）入っている B = [[] for _ in range(N+1)] # B[h] : 高さ h のレンガを含むリスト l, r = bricks.pop() B[1].append((l, r)) print(1) max_h = 1 for n in range(2, N+1): l, r = bricks.pop() h = 1 for h1 in range(max_h, 0, -1): if h != 1: break for l1, r1 in B[h1]: if max(l, l1) > min(r, r1): # 重なっていない continue h = h1 + 1 max_h = max(max_h, h) break B[h].append((l, r)) print(h)
アルゴリズムを場合分けする
で、じゃあ実際どっちを使えばいいの？ ということですが、それぞれの解法を提出してみると、どちらも TLE しますが、（予想通り？）TLE するケースがそれぞれに異なります。レンガの平均的な長さによって、効率的なアルゴリズムが変わるという予想は正しかったようです。
そこで、すべてのレンガの長さの平均値を計算して、これが区間の幅 W の〇分の１以下であれば、最初の（区間が短い場合に有利な）アルゴリズム、そうでなければ、後から説明した（区間が長い場合に有利な）アルゴリズムを適用するようにします。〇の所に何を入れるかは、試行錯誤が必要ですが・・・
結果としては、〇 = 100 で通りました。
