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もやりたみは、今のところあるし、このモチベでやっていきたひ。