ARC 029 A - 高橋君とお肉 と ABC 002 D - 派閥

けんちょんさんがまとめてくれてるqiitaのAtCoder精選問題集の問題(初級)。

高橋くんとお肉は、そんなに難しくなかった。樹形図的に2のN乗の全探索で、肉を2つの鉄板に振り分けていく問題。こういうパターンもあるのかという気持ちになった。

t = []
n = 0
def rec(i, a, b):
    if i == n:
        return max(sum(a), sum(b))
    ans = 10000

    a.append(t[i])
    ans = min(ans, rec(i+1, a, b))
    a.pop()

    b.append(t[i])
    ans = min(ans, rec(i+1, a, b))
    b.pop()

    return ans


def main():
    global n
    n = int(input())
    for i in range(n):
        t.append(int(input()))
    print(rec(0, [], []))


if __name__ == '__main__':
    main()

これで、ACした。

できてないのが、派閥。 問題としては、幾何学っぽい感じがする。N 個の頂点が、互いにランダムに結びついていて、その中で、全ての頂点同士が結び付いているグループの最大頂点数を求める問題(だと思う)。

テストケース正解数が、62/70だから、88%ぐらいは、できてる(こんなこと言ったら、全部合ってこそ正解だバカヤローと言われてしまいそうだが)。

table = []


def rec(a):
    ans = 1
    if not a:
        return ans
    first = a[0]
    del a[0]
    common = set(table[first]) & set(a)
    nxt = sorted(list(common), key=lambda x: len(table[x]), reverse=True)
    ans += rec(nxt)
    return ans


def main():
    global table
    n, m = [int(i) for i in input().split()]
    table = [[] for i in range(n)]
    for i in range(m):
        x, y = [int(j) for j in input().split()]
        table[x-1].append(y-1)
    ans = 0
    for i in range(n):
        ans = max(ans, rec([j for j in range(i, n)]+[k for k in range(i)]))
    print(ans-1)


if __name__ == '__main__':
    main()

失敗するテストケースは、わかってるんだけど、探索の仕方がまだわかってなくて、部分的にこうじゃないかな、ぐらいの考えで書いてるからなんとも言えない感じ。 近日中に解きたい(できれば明日)。

蟻本の練習問題は、英語だし、C++だし、あまり合わなかったんだけど、これなら、行けそうかもと思ってる。楽しくやるのが一番だけどね。こっちで慣れたらPOJもやりたみは、今のところあるし、このモチベでやっていきたひ。