JOI難易度７ 展覧会

問題原文

atcoder.jp

問題要旨

大きさ、価値がそれぞれ , であるような絵が 枚と、大きさが であるような額縁が 個ある。
各絵はそれよりも大きなサイズの額縁にしか入れることはできない。
また、絵を額縁に入れて飾る時、額縁の大きさについても絵の価値についても広義単調増加になっている必要がある。
最大で何枚の絵を入れられるか。

• 

解法

「こういうのは現時点で入れられる絵を管理するんですよ〜」っていいながら考えてたら普通にハマった。（方向性自体は多分だけど正しいと信じている）

まず、額縁は必ず大きい順に並ぶのでソートしておいて問題なし。
で、ここから良さげなパターンが２つ思い浮かぶ。

1. 額縁が大きい方から見て行って、その額縁に入る絵のうち、最も価値の高いものを入れる。
2. 額縁が小さい方から見て行って、その額縁に入る絵のうち、最も価値の低いものを入れる。

ただ2は、大きさが極小だけど価値が極大みたいな絵があった時に採用してしまうのでダメだとわかる。
（逆に１は「さっきは入らなかったけど、今は額縁に入って、それでいてこれまで入れたどんな絵よりも価値が高い」という状況が生まれない。一番大きな額縁に入れられる絵の集合は、二番目に大きな額縁に入れられる絵の集合を包含している。）

じゃぁ１か〜となって、絵の大きさについてソートしておいて、「今の額縁に入るものがまだあるか？」をセグ木とかで判定しようとしたけどTLEしてかなしいねになる。

で、発想をちょっと変えて価値に目線をおくと、「価値が大きいものから入れられるかチャレンジをして、入れられるなら入れてしまう」で損をしないこと、結局絵を入れる順番は同じなことががわかる。

これでようやくAC。

実装

def main():
    import sys
    my_input = sys.stdin.readline
    N, M = map(int, my_input().split())
    arts = [list(map(int, my_input().split())) for _ in range(N)]
    frames = [int(my_input()) for _ in range(M)]
    INF = float('inf')
 
    arts.sort(key=lambda x: [x[1], x[0]], reverse=True)
    frames.sort(reverse=True)
 
    ans = 0
    cursor = 0
    for frame in frames:
        while (cursor < N) and (arts[cursor][0] > frame):
            cursor += 1
 
        if cursor < N:
            ans += 1
            cursor += 1
 
    print(ans)
 
 
if __name__ == "__main__":
    main()

感想

はい典型〜じゃないんですよね。
証明力がないので説明があってるか不安になる。。。