Painting Wall (Mine) - 壁のペンキ塗り

どんな問題？

Painting Wall
http://www.checkio.org/mission/painting-wall/

指定された手順に従って、壁にペンキを塗っていく。例えば、手順が[1,5]であれば、壁の1枚目から5枚目までを塗る。同じ壁を重複して塗った場合も1枚として数える。
必要な枚数を塗り終わるまでに、何番目の手順まで進めればよいかを調べよ。

引数は、塗るべき壁の枚数と、手順のリストが与えられる。
戻り値は、指定した枚数を塗り終わるまでの手順の数を返す。すべての手順を終えても、必要な枚数に達しない場合は -1 を返す。

ヒントに、バイナリサーチ（二分探索）を試してみようと書いてある。

例題：

checkio(5, [[1,5], [11,15], [2,14], [21,25]]) == 1 # The first operation will paint 5 meter long.
checkio(6, [[1,5], [11,15], [2,14], [21,25]]) == 2 # The second operation will paint 5 meter long. The sum is 10.
checkio(11, [[1,5], [11,15], [2,14], [21,25]]) == 3 # After the third operation, the range 1-15 will be painted.
checkio(16, [[1,5], [11,15], [2,14], [21,25]]) == 4 # Note the overlapped range must be counted only once.
checkio(21, [[1,5], [11,15], [2,14], [21,25]]) == -1 # There are no ways to paint for 21 meters from this list.
 
checkio(1000000011,[[1,1000000000],[11,1000000010]]) == -1 # One of the huge test cases.

ちなみに、この問題の作者はCielさんで、（たぶん）CheckiOで最初の日本人が作った問題になる。

どうやって解く？

普通に考えると、壁1枚ごとに塗り終わったかどうかのフラグを作成しておいて、手順を1つ進めるごとに塗り終わった枚数を数えれば良さそうだ。

ただし、条件に 2*10¹⁸と書かれているのが気になる。普通の解き方ではメモリ不足になりそうな予感がする・・・。ヒントの二分探索も、どう使うのかがよくわからない。

とりあえずコードを書いてみた。手順ごとに、塗り終わった壁の番号をsetに追加していく。

def checkio(num, data):
    painted = set()
    for i, (start, end) in enumerate(data):
        painted |= {n for n in range(start, end + 1)}
        if len(painted) >= num:
            return i + 1
    return -1

ローカル環境で実行してみると、やっぱり例題の最後の問題で Memory Error となってしまった。

    assert checkio(1000000011, [[1, 1000000000], [11, 1000000010]]) == -1, "large"

やっぱり・・・。
さて、どうしようか。

先ほどメモリエラーになった例題を見ていると、

• 手順1で、1～1000000000（10億）を塗る
• 手順2で、11～1000000010 を塗る

という作業なのだから、

• 壁1～10は、手順1のみ
• 壁11～1000000000は、手順1と2で重複して塗っている
• 壁1000000001～1000000010は、手順2のみ

の3パターンだとわかる。壁1枚ごとにフラグを設定する必要はなく、このケースならフラグは3つあればいいわけだ。

壁1～10のようなひとかたまりをセグメントと呼ぶことにして、どうやってセグメントのリストを求めればいいだろうか？あれこれ考えて、

• 手順の後ろの数字を+1にする。手順が[1,5]なら(1,6)
• 手順リストに出てくるすべての数字を番号順にソート
• 前から2つずつペアにして、2番目の数字を-1する

とすることでセグメントのリストを得ることができた。

[[1, 5], [11, 15], [2, 14], [21, 25]]
　　　↓
(1, 6), (11, 16), (2, 15), (21, 26)
　　　↓
[1, 2, 6, 11, 15, 16, 21, 26]
　　　↓
[(1, 1), (2, 5), (6, 10), (11, 14), (15, 15), (16, 20), (21, 25)]

まとめ

def checkio(num, data):
    # Make segments
    # ex.
    #   data = [[1, 5], [11, 15], [2, 14], [21, 25]]
    #   segments = [(1, 1), (2, 5), (6, 10), (11, 14), (15, 15), (16, 20), (21, 25)]
    numbers = sorted([n for start, end in data for n in (start, end + 1)])
    segments = [(n1, n2 - 1) for n1, n2 in zip(numbers[:-1], numbers[1:])]
 
    painted = set()
    for i, (start, end) in enumerate(data):
        painted |= {(s, e) for s, e in segments if start <= s and e <= end}
        if sum([e - s + 1 for s, e in painted]) >= num:
            return i + 1

http://www.checkio.org/mission/painting-wall/publications/natsuki/python-3/first/

公開後に見直すと、手順に使われている数字(numbers)を求めるとき、同じ数字が出てくる場合があるので、setで重複を除去してからソートした方がよかったかな。

numbers = sorted([n for start, end in data for n in (start, end + 1)])  # list
　　　↓
numbers = sorted({n for start, end in data for n in (start, end + 1)})  # set

他の人の答え

bisectという、初めて見るモジュールが・・・。気になるところだが、続きは後日に。