ABC002

今日のラボプロコンでABC002をやりました。

abc002.contest.atcoder.jp

最近の奴に比べると難易度が本当に教育的だって思いましたね。この前のABC023の制約とかもうね(;_;) 定期的に記事書かないと習慣がつかないと思ったので上げることに。D問題が結構ためになりました。

A-正直者

入力二つの大きい方を出力する問題。一行で書きたいなら皆こうなるであろう(pythonなら)。

print max(map(int,raw_input().split(" ")))

B-罠

入力された文字列の母音を取り除いて出力する問題。ちょっとfilter使いたかったので使ってみた。

ban_word = set(["a","i","u","e","o"])
print "".join(filter(lambda w: w not in ban_word,list(raw_input())))

C-直訴

与えられた3点がなす三角形の面積を出す問題。ヒント見ちゃったので乗っかっちゃいましたw (0,0), (a,b), (c,d) で構成される三角形の面積は|ad−bc|/2だっての高校でやった覚えあるなあ。

xa, ya, xb, yb, xc, yc = map(int,raw_input().split(" "))
print abs((xa-xc)*(yb-yc)-(xb-xc)*(ya-yc)) / 2.

D-派閥

N人の議員についてのM個の人間関係から、全員が知り合いであるような最大のグループの人数を求める問題。文章にすると分かりにくいですが、いわゆる最大クリーク*1問題です。

最大クリーク問題 - Wikipedia

「あっこれグラフ理論でやった奴だ」ってちょっと思いましたね笑 とは言ってもそもそも最大クリーク問題の最適な解き方とかよく知らなかったんで地道に解くことにしました。

初めにこのD問題が一番ためになったと言ったのですが、なぜかというとプロコンでしばしば見られる問題の言い換えを意識することが出来たからです。「グラフの最大クリークの節点数Kを求める」と言われても僕は困ってしまうのですが、「グラフにK個の節点からなるクリークが存在するようなKの最大値を求める」と考えると話が分かりやすくなります。

「グラフにK個の節点からなるクリークが存在するか？」という問題はK-クリーク問題と呼ばれます。 これを解くのは(計算量の話は今回は置いとくとして)簡単です。グラフのN個の節点の内K個の節点を選んでしえば, それらがクリークを成しているかは任意の二節点が辺で結ばれているかを調べてしまえば確かめられます。これをN個の節点から取れるK個の節点の組み合わせ, 通り全て調べればK-クリーク問題は解けるわけです。

よって今回の問題は, KをNから1まで動かして行って各KでK-クリーク問題を解き, TRUEだったKの最大値はいくらだったかを返せば良いことになります。こういう解き方を初めて自力でできたので簡単な問題とはいえ結構嬉しかったです(^^)

from itertools import combinations as comb

def k_clique_solve(relation, max_members, k):
    for members in comb(max_members,k):
        for r in comb(members,2):
            if r in relation:
                continue
            break
        else:
            return True
    else:
        return False

N, M = map(int,raw_input().split(" "))
max_members = range(N)
relation = set()

for i in range(M):
    x,y = map(int,raw_input().split(" "))
    relation.add((x-1,y-1))
 
result = 1
for k in range(N,0,-1):
    if k_clique_solve(relation,max_members, k):
        result = k
        break
print result

今回は1≤N≤12なので全然大丈夫ですが、 ARCや最近のABCだと制約が厳しいため二分探索を求めてきます。せっかくなのでやってみました。

from itertools import combinations as comb

def k_clique_solve(relation, max_members, k):
    for members in comb(max_members,k):
        for r in comb(members,2):
            if r in relation:
                continue
            break
        else:
            return True
    else:
        return False

N, M = map(int,raw_input().split(" "))
max_members = range(N)
relation = set()

for i in range(M):
    x,y = map(int,raw_input().split(" "))
    relation.add((x-1,y-1))
 
left = 1
right = N + 1
while right - left > 1:
    mid = (left + right) / 2
    if k_clique_solve(relation, max_members, mid):
        left = mid
    else:
        right = mid
print left

まあNがちっちゃいので2ms速くなっただけでしたね笑 今回のは良い練習になったと思うので、次は本番でこういう解き方をしたいなあと思います。

*1:任意の二節点が辺で結ばれているグラフをクリークという