daikonnbatakeのブログ

【精進日記】ABC-002

精進した後に復習するためのメモみたいなもんです。
ほぼ自分用に書いてるので読みづらかったらごめんなさい。
特に断りが無い限り回答例は Python で記述します。

A問題

問題の要約

max(X, Y) を出力せよ。

回答例

print(max(map(int,input().split())))

ポイント

特にありません。

B問題

問題の要約

文字列 W から すべての a, i, u, e, o を消去して出力せよ。

回答例

print(''.join([i for i in list(input()) if i not in list('aiueo')]))

ポイント

特にありません。

C問題

問題の要約

二次元平面上の座標が 3 組与えられるので、各頂点を結んで出来る三角形の面積を求めよ。

回答例

x,y,a,b,c,d = list(map(int,input().split()))
print(abs((a-x)*(d-y) - (b-y)*(c-x))/2)

ポイント

特にありません。

D問題

問題の要約

N 個の頂点と M 個の辺が与えられる。
一部の頂点のすべてが互いに辺でつながっている状態を「派閥」と呼ぶ場合、派閥の中で一番大きなものの頂点の数を求めよ。

回答例

N, M=map(int, input().split())

ans = 0
v = [set([i])for i in range(N)]

for i in range(M):
    x, y=map(int, input().split())
    x-=1; y-=1
    v[x].add(y)
    v[y].add(x)

for i in range(1,1<<N):
    s = set()
    m = 0
    for j in range(N):
        if i & 1<<j:
            s.add(j)
    for j in s:
        if s & v[j] == s:
            m += 1
    ans = max(ans, m)
print(ans)

ポイント

「全ての頂点が互いに辺でつながっている状態」は、bit全探索で部分集合を求め、それと同じ部分集合を持つ集合を全探索すれば求めることができる。