プログラマーアーチェリー大会


この問題は3つの方法を使っていて、それぞれの方法がいいようなので、3つの方法を使いました.
問題に近づくと、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
    
  • グリディ+在貴
    上記のようなビットマスク法を用いて再帰的に解決することもできる.
  • 各インデックスは、Ryanが得点したとき/得られなかったときを基準に、枝を切ってRyanのスコアを獲得し、インデックスが最後であれば矢があれば、すべてのスコアを0に集約します.
    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)