【AtCoder版！蟻本】ABC002 D - 派閥【bit全探索】
AtCoder版！蟻本のbit全探索で類題としてあげられているABC002 DをPythonで解いていきます。
リンク
AtCoder Beginner Contest 002 D - 派閥
問題文
神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。
AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。
人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。
制約
・N (1≦N≦12)
・M (0≦M≦N(N−1)/2)
・xi と yi はともに整数で、1 ≦ xi < yi ≦ Nを満たす。
・i≠j のとき、( xi , yi ) ≠ ( xj , yj ) であることが保証されている。
解答例
#bit全探索 組み合わせ import itertools n, m = map(int,input().split()) friend = [[0] * (n+1) for i in range(n+1)] for i in range(m): x, y = map(int,input().split()) friend[x][y] = 1 friend[y][x] = 1 ans = 0 for bit in range(2**n): group = [] # 派閥のリスト for i in range(n): if (bit >> i) & 1: group.append(i+1) # bitが1ならiさんを派閥にくわえる # 派閥の人が互いに知り合いか判定フラグ flag = 1 for j in itertools.combinations(group,2): if friend[j[0]][j[1]] == 0: flag = 0 break if flag == 1: ans = max(ans,len(group)) print(ans)
解説
問題文の3行くらいはあまり読む意味がないですが…(^_^;)
N人の議員がいて 互いが知り合いなら派閥に入れます。
最大で何人の派閥が作れるか答える問題です。
N人の議員にたいしてbit全探索を行います。
bitが1の議員は派閥に入ると仮定して派閥候補リストgroupにいれます。
派閥候補が決まれば、そのリストから2人の組み合わせを試していきます。
friendリストを参照して、そのふたりが知り合いか判定します。
もし候補のすべての議員が互いに知り合いならansと比較して、大きいほうを代入していきます。
ループを抜けてansを出力すればACでした！
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ARC029 A - 高橋君とお肉【bit全探索】
AtCoder版！蟻本のbit全探索で類題としてあげられているARC029 A - 高橋君とお肉をPythonで解いていきます。
リンク
AtCoder Regular Contest 029 A - 高橋君とお肉
問題文
高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである 2 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。
2 つの肉焼き器にまたがって 1 つのお肉を置くことはできない。また、お肉は全部で N 個あり、お肉には 1 から N まで番号が付けられている。お肉 i を焼くのには、どちらの肉焼き器でも時間 ti だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。
高橋君はお肉を焼く係であり、N 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。
すべてのお肉を焼くのにかかる時間の最小値を求めよ。
制約
・N(1≦N≦4)
・ti(1≦ti≦50)
解答例
# bit全探索 n = int(input()) T = [] for i in range(n): T.append(int(input())) ans = 1e5 for bit in range(2**n): time1 = 0 # 肉焼き器1号で焼き終わる時間 time2 = 0 # 肉焼き器2号で焼き終わる時間 for i in range(n): if (bit >> i) & 1: # bitが1なら1号で焼く time1 += T[i] else: time2 += T[i] tmp = max(time1,time2) ans = min(ans,tmp) print(ans)
解説
2つの肉焼き器を使ってすべての肉を最も早く焼くのにかかる時間を答える問題です。
この問題もbit全探索をもちいて、bitが1の場合は肉焼き器1号で 0のときは2号で焼くことを想定しています。
各肉焼き器で必要な時間は、その機械で焼く肉の焼き上がり時間を足し合わせたものなので、1号はtime、2号はtime2にそれぞれ足し合わせました。
time1とtime2の大きいほうが その振り分けの焼き上がり終える時間になるので、ans変数と比較して小さければ その値を代入します。
ループを抜けたあとにans変数を出力すればACです！
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ABC104 C - All Green【bit全探索】
AtCoder版！蟻本のbit全探索で類題としてあげられているABC104 CをPythonで解いていきます。
リンク
AtCoder Beginner Contest 104 C - All Green
問題文
プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 それぞれの問題には、難易度に応じて点数が付けられています。 現在、
1 以上 D 以下のそれぞれの整数 i に対して、100i 点を付けられた問題が pi 問存在します。 これらの p1+…+pD 問が AtCode に収録された問題のすべてです。
AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。 ユーザーの総合スコアは、以下の 2 つの要素の和です。
基本スコア: ユーザーが解いた問題すべての配点の合計です。
コンプリートボーナス: 100i 点を付けられた pi 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci 点を獲得します (1≤i≤D)。
AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。 彼の目標は、総合スコアを G 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？
制約
・1≤D≤10
・1≤pi≤100
・100≤ci≤10^6
・100≤G
・入力中のすべての値は整数である。
・ci,G はすべて 100 の倍数である。
・総合スコアを G 点以上にすることは可能である。
解答例
# bit全探索、貪欲法 D, G = map(int,input().split()) P = [] C = [] for i in range(D): p, c = map(int,input().split()) P.append(p) C.append(c) #最小の回答数 ans = 1e9 for bit in range(2**D): # bit 1で問題コンプリート total = 0 # 合計得点 num = 0 # 回答数 for i in range(D): if (bit >> i) & 1: total += 100 * (i+1) * P[i] + C[i] num += P[i] if total >= G: # 問題コンプリートだけでGを超える場合 ans = min(ans,num) else: for j in reversed(range(D)): # 得点が大きいほうから貪欲法 if (bit >> j) & 1: # コンプリートは飛ばす continue target = G - total if target <= P[j] * (100 * (j+1)): # 問題を解くとtotalがGを超える場合 num += -(-target // (100 * (j+1))) # 切り上げ！ ans = min(ans,num) break else: total += 100 * (j+1) * P[j] num += P[j] print(ans)
解説
総合スコアを G 点以上にするために最小の問題数を答える問題です。
総合スコアは1問解くごとにもらえる基本スコア（例：A問題なら100点、B問題なら200点）と、コンプリートボーナス（例：A問題すべて解くとc1点）の合計です。
問題をすべて解く難易度の組み合わせをbit全探索し、G点を超えなかったら配点が高い問題から貪欲に解いていく方針です。
合計得点をtotal、問題の回答数をnumとおき、bitが1ならその難易度の問題をすべて解いたことにしました。
得点はその難易度の配点×問題数とコンプリートボーナスを足し合わせた値です。
もし、コンプリートだけでG点以上になった場合は、解答となるansと比較して小さければ代入します。
コンプリートだけでG点に満たなかった場合は、bit情報を用いてコンプリートしていない問題を配点の高い順に解いていくシミュレーションをしました。
この貪欲法でコンプリートしてもボーナスを考慮していません。
その場面はbit全探索でカバーされるはずなので最終的な解答には影響がないと思います。
この探索を終えてans変数を出力すればACでした。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】AOJ 0529 Darts【準備編】
AtCoder版！蟻本の準備編で類題としてあげられているAOJ0529をPythonで解いていきます。
この解答例は制限時間オーバーしてしまいますが参考のため記事にしました。
リンク
AOJ 0529 Darts
問題文
あなたは以下のルールでダーツゲームをすることになった.
あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ずしも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的は N 個の部分に区切られていて,各々の部分に点数 P1,..., PN が書か れている.矢が刺さった場所の点数の合計 S があなたの得点の基礎となる.S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.
的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ.
解答例
import bisect while True: n, m = map(int,input().split()) if n == 0 and m == 0: # 終了条件 break # 的の点数 P = [] for i in range(n): P.append(int(input())) # 投げない選択肢を足す P.append(0) # 2投で取り得る点数 S = [] for i in range(n + 1): for j in range(i,n + 1): S.append(P[i] + P[j]) # 二分探索のためソート S.sort() # Sの要素のうちm以下の最大値の位置+1 num = bisect.bisect_left(S,m) # m以上のSの要素を除外 if num < len(S): if S[num] == m: print(m) continue S = S[:num] # 取り得る最大の得点 res = 0 # 最大の得点を探索 for i in range(len(S)): tmp = bisect.bisect_left(S,m - S[i]) res = max(res,S[i] + S[tmp-1]) if res == m: break print(res)
解説
4投まで行うことのできるダーツで、最大何点とることができるか答える問題です。
4重ループでは完全に間に合わなくなるので、2投で取り得る点数をリストSに入れていく半分全列挙を用いました。
計算量を減らすためリストSの要素のうちmより大きい値は除外しておきます。（結果的に間に合いませんでしたが (^_^;)
最後に最大の得点を探索です。
2投した得点をきめたあと、mに最も近くなるようなSの値を二分探索で求めます。
合計得点をresと比較して、大きければresを更新していく方針です。
残念ながらこの方法は制限時間オーバーでしたが、半分全列挙・二分探索を使用した例として記事に残します。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ABC175 B - Making Triangle【準備編】
AtCoder版！蟻本の準備編で類題としてあげられているABC175 BをPythonで解いていきます。
リンク
AtCoder Beginner Contest 175 B - Making Triangle
問題文
1,⋯,N の番号がついた N 本の棒があります。棒 i(1≤i≤N) の長さは Li です。
このうち、三角形を作ることのできるような長さの異なる 3 本の棒を選ぶ方法は何通りあるでしょうか。
つまり、3 つの整数 1 ≤ i < j < k ≤ N の組であって次の 2 つの条件の両方を満たすものの個数を求めてください。
Li, Lj, Lk がすべて異なる3 辺の長さが Li, Lj, Lk であるような三角形が存在する。
制約
・1≤N≤100
・1≤Li≤10^9
・入力は全て整数である
解答例
n = int(input()) # 棒の長さのリスト A = list(map(int, input().split())) A.sort() # 条件を満たす三角形の数 ans = 0 for i in range(n-2): for j in range(i,n-1): if A[i] == A[j]: # 長さが等しければスキップ continue for k in range(j,n): if A[j] == A[k]: # 長さが等しければスキップ continue if A[i]+A[j]>A[k]: # 三角形として成立しているか判定 ans += 1 print(ans)
解説
N本の棒があるとき、そのなかから長さが異なる3本を選んで 合計何個の三角形が作れるか答える問題です。
3本の組み合わせを全通り試す全探索で答えを求めていきます。
あとで三角形が成り立つか判定しやすくするために棒の長さが格納されたリストAをソートします。
次は3本の棒を選ぶ3重ループをまわして全探索です。
1本目の棒iと2本目の棒jを選んだ時点で、長さが同じでないか判定します。
長さが違ったら3本目の棒kを選びます。
3本目の棒を選んだ時も長さが同じでないか判定しますが、相手は2本目のjです。
リストAはソートしてあるので、jとkが異なればiとも異なるといえますので、jとだけ比較すれば十分です。
三角形として成り立つには、一番長い棒が 残りの2つの棒を足し合わせた長さより短い必要があります。
この判定を最後に行って、通ればansに1を足していきます。
ループを抜けたあとにansを出力すればACをとれます。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ABC085 C - Otoshidama【準備編】
AtCoder版！蟻本の準備編で類題としてあげられているABC085 CをPythonで解いていきます。
リンク
AtCoder Beginner Contest 085 C - Otoshidama
問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
制約
・1≤N≤2000
・1000≤Y≤2×10^7
・N は整数である。
・Y は 1000 の倍数である。
解答例
n, y = map(int,input().split()) # 組み合わせが存在するか判定フラグ flag = False # お札の組み合わせを全探索 for a in range(n+1): # 1万円札 if flag: # 組み合わせが見つかっていたら終了 break for b in range(n-a+1): # 5千円札 c = (y - 10000 * a - 5000 * b)//1000 # 千円札の枚数候補 if c >= 0 and a + b + c == n: # 候補が条件を満たすか判定 print(a,b,c) flag = True break # 組み合わせがなければ-1を出力 if flag == False: print("-1 -1 -1")
解説
1万円、5千円、千円札をN枚組み合わせてY円にすることができるか、できるならその枚数を答える問題です。
1万円札をa枚、5千円札をb枚、千円札をc枚として全探索を行いました。
Nの範囲が最大で2000なので、3重ループにすると計算量が多くなりすぎです。
1万円札a枚と5千円札b枚、および目標金額Y円が決まっていると、千円札のc枚は計算で求めることができます。
よって、1万円札のaと5千円札のbの2重ループとして各ループごとにcの候補を計算。
候補cがこの問題の条件にあうか判別することで計算量を落としています。
条件を満たすcが見つかれば、a,b,cの組み合わせを出力し、見つからなければ-1を出力すればOKでした。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ABC051 B - Sum of Three Integers【準備編】
AtCoder版！蟻本の準備編で類題としてあげられているABC051 BをPythonで解いていきます。
リンク
AtCoder Beginner Contest 051 B - Sum of Three Integers
問題文
2 つの整数 K,S が与えられます。
3 つの変数 X,Y,Z があり、0≦X,Y,Z≦K を満たす整数の値を取ります。
X+Y+Z=S を満たす X,Y,Z への値の割り当ては何通りありますか。
制約
・2≦K≦2500
・0≦S≦3K
・K,S は整数である。
解答例
k, s = map(int,input().split()) # 条件を満たす組み合わせの数 ans = 0 # 全探索 for x in range(k+1): for y in range(k+1): z = s - x - y if z >= 0 and z <= k: ans += 1 print(ans)
解説
k以下の正の整数x,y,zがあり、x + y + z = sを満たす組み合わせの数を答える問題です。
x,y,zの3重ループにすると計算量が多くなりますので、xとyの2重ループになるよう工夫が必要です。
x + y + z = s から z = s - x - y と式変形できます。
なので、xとyが決まれば候補となるzが求まり、この候補が条件を満たすか（正の整数でk以下か）を判定します。
条件を満たせばansに1を足していけば、ループを抜けたあとのansが求める解答です。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ARC004 A - 2点間距離の最大値【準備編】
AtCoder版！蟻本の準備編で類題としてあげられているARC004 AをPythonで解いていきます。
リンク
AtCoder Regular Contest 004 A - 2点間距離の最大値 ( The longest distance )
問題文
平面上に N 個の点があり、それぞれ 0 から N−1 までの番号が付けられており、それぞれの点について x 座標と y 座標が与えられています。
その N 点のうち 2 点を選び結んで得られる線分のうち、最も長くなる線分の長さを求めてください。
入力
・入力は N+1 行ある。
・1 行目には、点の個数を表す整数 N(2≦N≦100)が与えられる。
・2 行目から N+1 行目までの i+2(0≦i
解答例
n = int(input()) X = [] Y = [] for i in range(n): x, y = map(int,input().split()) X.append(x) Y.append(y) # 最長の線分 ans = 0 # 全探索 for i in range(n-1): for j in range(i,n): tmp = (X[i] - X[j])**2 + (Y[i] - Y[j])**2 ans = max(ans,tmp**0.5) print(ans)
解説
x,y座標の組がn点与えられ、その2点をつなぐ線分のうち最も長い線分の長さを答える問題です。
nが100以下と数が少ないので全探索すれば答えが求まります。
2重ループで異なる2点のすべての組み合わせを試します。
2点間の距離は(xi - xj)^2 + ( yi - yj)^2の平方根になりますので、tmpに(xi - xj)^2 + ( yi - yj)を代入します。
その後、ansとtmp^0.5を比較して大きいほうをansとします。
すべての点の組み合わせを探索し終えると求める解答となります。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
