プログラマーアーチェリー大会
20642 ワード
この問題は3つの方法を使っていて、それぞれの方法がいいようなので、3つの方法を使いました.
問題に近づくと、n個を射出し、10点から0点のうち、どのようにn個をリストすべきかを考えます.したがって,0から10までの間にn個の数字を繰り返し抽出し,すべての場合に数字を探索して最適解の方向を求めて解く.ブルトフ
その名の通りPython反復コンポジットライブラリ組合せwith replacementを用いてコンポジットを求め,魚餅とRyanのスコアテーブルを比較することにより,スコア差が既存のスコア差より大きい場合は更新,あるいはスキップで実現する. 階調+ビットマスク
この問題はギリシャ語で解決できますが、ライアンの立場で、点数差を最大限に広げるためにはどうすればいいかと思います.考えてみれば、魚の皮魚は中の1つより多く、2つより多く、同じ点数を得ることができます.
したがって、ライアンはある点数iに対してi点か0点しかないか、あるいは2つの場合しかない.
問題を解決するために、ライアンの数の手配を考えるよりも、ライアンがどの点数で勝つかを考えたほうがいい.
例えば、ライアンが10、9、8点のみで得点した場合は[1000000]であり、ビットマスクを使用して10桁の数であれば1024桁でループすることができ、ビットマスクと&演算で勝った場所の点数のみを反映することができ、ライアンが射た矢の数は魚皮値ペアの矢の数+1と書くことができる. グリディ+在貴
上記のようなビットマスク法を用いて再帰的に解決することもできる. 各インデックスは、Ryanが得点したとき/得られなかったときを基準に、枝を切ってRyanのスコアを獲得し、インデックスが最後であれば矢があれば、すべてのスコアを0に集約します.
問題に近づくと、n個を射出し、10点から0点のうち、どのようにn個をリストすべきかを考えます.したがって,0から10までの間にn個の数字を繰り返し抽出し,すべての場合に数字を探索して最適解の方向を求めて解く.
その名の通りPython反復コンポジットライブラリ組合せwith replacementを用いてコンポジットを求め,魚餅とRyanのスコアテーブルを比較することにより,スコア差が既存のスコア差より大きい場合は更新,あるいはスキップで実現する.
from itertools import combinations_with_replacement
def compare(a,b):
apeche = 0
lion = 0
for i in range(11):
if a[i] == 0 and b[i] == 0:
continue
elif a[i] >= b[i]:
apeche += 10 - i
else:
lion += 10 - i
return apeche,lion
def solution(n, info):
score_diff = 0
possible = []
combination = combinations_with_replacement(range(11),n)
for comb in combination:
lion = [0]*11
for c in comb:
lion[c] += 1
apeche_score,lion_score = compare(info,lion)
if lion_score - apeche_score > score_diff:
del possible[:]
possible.append(lion)
score_diff = lion_score - apeche_score
elif lion_score - apeche_score == score_diff and score_diff != 0:
possible.append(lion)
# 배열 원소 순으로 정렬
if len(possible) == 0:
return [-1]
for i in range(len(possible)):
possible[i].reverse()
possible.sort(reverse = True)
possible[0].reverse()
return possible[0]この問題はギリシャ語で解決できますが、ライアンの立場で、点数差を最大限に広げるためにはどうすればいいかと思います.考えてみれば、魚の皮魚は中の1つより多く、2つより多く、同じ点数を得ることができます.
したがって、ライアンはある点数iに対してi点か0点しかないか、あるいは2つの場合しかない.
問題を解決するために、ライアンの数の手配を考えるよりも、ライアンがどの点数で勝つかを考えたほうがいい.
例えば、ライアンが10、9、8点のみで得点した場合は[1000000]であり、ビットマスクを使用して10桁の数であれば1024桁でループすることができ、ビットマスクと&演算で勝った場所の点数のみを反映することができ、ライアンが射た矢の数は魚皮値ペアの矢の数+1と書くことができる.
def compare(a, b):
return a[::-1] > b[::-1]
def solution(n, info):
ans = [-1] * 12
for lionbit in range(1024): ##
lion = [0] * 12
ascore = 0
lscore = 0
cnt = n
for maskbit in range(10):
x = lionbit & (1 << maskbit)
if x: ## 비트가 켜져 있다면 라이언이 이겨야 하는 경우
lscore += 10 - maskbit
lion[maskbit] = info[maskbit] + 1
cnt -= lion[maskbit]
elif info[maskbit] != 0: ## 어피치가 이기는 경우
ascore += 10 - maskbit
if lscore <= ascore or cnt < 0:
continue
lion[10] = cnt
lion[11] = lscore - ascore
if compare(lion, ans):
ans = lion[:]
if ans[-1] == -1:
return [-1]
else:
ans.pop()
return ans
上記のようなビットマスク法を用いて再帰的に解決することもできる.
answer = [-1] * 12
def compare(a, b):
return a[::-1] > b[::-1]
def solution(n, info):
dfs(n, 0, [0] * 12, info)
answer.pop()
return answer
def dfs(arrow_left, idx, lion, apeche):
global answer
if arrow_left < 0:
return
if idx >= 10: ## dfs의 끝
lscore = 0
ascore = 0
lion[10] = arrow_left
print(arrow_left,lion)
for j in range(10):
if apeche[j] == 0 and lion[j] == 0:
continue
if lion[j] > apeche[j]:
lscore += (10 - j)
else:
ascore += (10 - j)
if lscore > ascore:
lion[11] = lscore - ascore
if compare(lion, answer):
answer = lion[:]
return
lion[idx] = apeche[idx] + 1
dfs(arrow_left - (apeche[idx] + 1), idx + 1, lion, apeche)
lion[idx] = 0
dfs(arrow_left,idx+1,lion,apeche)Reference
この問題について(プログラマーアーチェリー大会), 我々は、より多くの情報をここで見つけました https://velog.io/@wook2pp/프로그래머스-양궁대회テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol