KUPC 2015 A 東京都 と ABC 103 D - Islands War

競技プログラミング

https://qiita.com/drken/items/e77685614f3c6bf86f44

続きです。

区間スケジューリングの問題がメインです。

区間スケジューリングは、個々の区間に、少なくとも 1 つ垂直に棒が刺さっている状態にするには、最小で何本必要ですかという問題らしい。けんちょんさんのブログが、めちゃめちゃわかりやすい。

東京都は、区間スケジューリングっていう感じはしなかった。ただ貪欲にって感じ。以下解答

https://atcoder.jp/contests/kupc2015/tasks/kupc2015_a

def ans(s):
    a, b = 'kyoto', 'tokyo'
    i = 0
    ans = 0
    while i < len(s):
        if s[i:i+len(a)] == a:
            i += len(a)
            ans += 1
        elif s[i:i+len(b)] == b:
            i += len(b)
            ans += 1
        else:
            i += 1
    return ans


def main():
    n = int(input())
    for i in range(n):
        s = input()
        print(ans(s))


if __name__ == '__main__':
    main()

Islands War

https://atcoder.jp/contests/abc103/tasks/abc103_d

問題概要

水平にいくつか点がある。その点はどれも、両端の点と線で繋がっている。任意の数の 2 点の組み合わせが与えられるので、線を消して、その 2 点が線を通じて繋がらないようにしてほしいらしい。そのとき、最小で何本線を消せば良いか。

解答

def main():
    n, m = [int(i) for i in input().split()]
    abc = []
    for i in range(m):
        a, b  = [int(j) for j in input().split()]
        abc.append([a,b])
    abc.sort(key=lambda x:x[1])
    i = 1
    ans = 1
    now = abc[0]
    while i < m:
        if now[1] <= abc[i][0]:
            ans += 1
            now = abc[i]
        i += 1
    print(ans)

if __name__ == '__main__':
    main()