説明:

これはプログラマーのデジタルゲーム題です.
2つの整数を並べた場合、1つの配列を基準に1つの整数を比較し、より大きな得点ゲームがある場合は、並べ順を組み合わせて最大の得点を返すことを目的としています.
例えば、[5,1,3,7]および[2,2,6,8]が与えられると、[2,2,6,8]を[8,2,6,2]に組み合わせると、最大スコア3点が得られる.
シナリオ1:[5][1][3][7]
シナリオ2:[8][2][6][2]
要素8は要素5より大きい.要素2は要素1より大きい.要素6は要素3より大きい.要素2は要素7より小さい.結果、3回優勝したので3点を取ることができた.

に答える

DFS(失敗)

最初の試みの方法は、配列をツリーに構築し、最初の要素から最後の要素までのすべての組み合わせを試み、最高スコアを計算することです.このため,次のようなツリー構造を用いてノードを構築し,各ノードの高さに対応する配列の要素を比較してスコアを増加させる.
ツリーの各ノードを参照すると、比較配列(上記の例では[5,1,3,7]である)と比較して、8,2,6,2点から最大スコアを3点から3点に更新することができる.そして残りのノードでは,これまで得られたスコアと以降得られたすべてのスコアを計算することにより,最大スコアを超えなければ探索を行わず最適化を行った.
これを実現するコードは次のとおりです.

import collections

# 최고 점수를 저장하는 전역 변수.
highestScore = 0
# DFS 함수에서 비교 대상 배열에 접근하기 위한 전역 변수.
competitors = None


# 최고 점수 탐색.
def findHighestScore(nodes, usedCount, currentScore):
    global highestScore
    global competitors

    # 만약 앞으로 얻을 수 있는 점수가 최고점을 넘지 못한다면 탐색 종료.
    # 승점은 1점씩이기 때문에 노드의 갯수로만 비교해도 점수로 취급할 수 있음.
    if (len(nodes) - usedCount + currentScore) <= highestScore:
        return
    
    # 필요 시 최고 점수 갱신.
    highestScore = max(highestScore, currentScore)
    
    # 모든 노드를 탐색했을 경우 즉 모든 원소를 비교했을 경우 탐색 종료.
    if usedCount == len(nodes):
        return

    # 다음 원소와 비교할 조합 생성.
    for index, node in enumerate(nodes):
        # -1로 설정된 원소는 이미 부모 노드에서 비교하는데 사용된 값.
        if node < 0:
            continue
            
        # 자식 노드에서 사용하게 될 원소는 -1로 비활성화 처리.
        # 다음 원소랑 비교할 때 기존에 사용한 값은 사용하지 않도록 하기 위함.
        _nodes = nodes.copy()
        _nodes[index] = -1
        # 비교 대상 배열의 원소와 비교하여 누적 점수 갱신.
        # usedCount 변수는 트리에서 현재 노드의 높이와 동일하며
        # 비교 대상 배열에서 비교할 원소의 인덱스와도 동일함.
        findHighestScore(_nodes, usedCount+1, currentScore+1 if node > competitors[usedCount] else currentScore)

def solution(A, B):
    global highestScore
    global competitors
    
    # 비교 대상 배열에 A 등록.
    competitors = A
    
    # 맨 처음 원소부터 비교하여 탐색 시작.
    for index, b in enumerate(B):
        _B = B.copy()
        _B[index] = -1
        findHighestScore(_B, 1, 1 if b > A[0] else 0)
    
    # 최고 점수 반환.
    return highestScore

理論的には実行可能な方法であるが,問題で無視される点は配列Aであり,Bは1〜100000個である.上記のDFSナビゲーションでは、アレイサイズは数十個に過ぎないが、ナビゲーションが必要なノードは指数関数的に増加するため、タイムアウトの問題が発生し続けている.

Sort(成功)

したがって,1つのプールを探すと,配列を並べ替えて最初から比較したプールで実現することが多い.残念なことに、私は初めて試した答えの中でほとんど答えに近づいた.問題は配列Aが固定されており,配列Bの要素を組み合わせて最も高い積分を計算するので,配列Bの要素をどのような順序で比較しても関係ない.そこで,両方の要素をソートし,どちらの要素が大きいかを比較する方法で試みた.
しかし,当時はsort法でソートし,配列中の要素を比較する方式で実現した.このため、次の処理はできません.
シナリオ1:[2][3][4][5][6][7]
シナリオ2:[3][4][5][6][2][7]
配列1と配列2は全く同じ元素(2,3,4,5,6,7)からなる.したがって、2つの配列を並べ替えて比較すると、同じ要素間で比較されるため、0点と計算されますが、実際には以下の組み合わせで5点を得ることができます.
シナリオ1:[2][3][4][5][6][7]
シナリオ2:[3][4][5][6][7][2]
ここでは,このようなプールを放棄してDFSに移ったようで,インデックスを2つの配列で配置し,1つずつ比較してアクセスすると,これは容易に解決できる問題である.この方法のコードは次のとおりです.

def solution(A, B):
    # 만약 원소 1에 대해 승점을 얻기 위해 원소 7을 사용한다면 낭비일 것이다.
    # 하지만 원소 1에 대해 원소 2를 사용한다면 제일 효율적일 것이다.
    # 즉 원소 n과 비교하기 위해 n+1부터 하나씩 비교하기 위해 두 배열을 정렬한다.
    A.sort()
    B.sort()
    
    # A의 제일 작은 원소가 B의 제일 큰 원소보다 크다면 B가 얻을 수 있는 점수는 없다.
    # 구현되어 있진 않지만 반대의 경우도 이렇게 예외로 처리할 수 있을 것이다.
    if A[0] > B[-1]:
        return 0
    
    # 점수, 비교를 위한 인덱스 변수.
    answer = 0
    indexA, indexB = 0, 0
    
    # 두 배열의 원소를 하나씩 비교하며 B의 원소가 A의 원소보다 크다면 점수 증가.
    while indexA < len(A) and indexB < len(B):
        if B[indexB] > A[indexA]:
            indexA += 1
            answer += 1
        indexB += 1
    
    # 최종 점수 반환.
    return answer

ポスト

想像以上に簡単な問題であり、DFSに執着するだけで時間がかかる問題でもある.複雑なアルゴリズムを無条件に用いることは良くなく,レベル3が必ずしも難しいアルゴリズムを要求するわけではないことが感じられる.