私はcodility</p> <blockquote> <p>「でも合計」</p> </blockquote> <p>が、そうすることができませんから、問題を解決しようとしていたアルゴリズム

Question

背後にあるロジックは何ですか。ここに、以下の質問があります。

偶数和は、2人のプレーヤーのゲームです。プレイヤーには、N個の正の整数のシーケンスが与えられ、交互に交代する。各ターンにおいて、プレイヤーは、このスライス内の値の合計が偶数であるように、空でないスライス（連続した要素のサブシーケンス）を選択し、スライスを除去し、シーケンスの残りの部分を連結する。法的な動きをすることができない最初のプレイヤーはゲームを失う。

あなたは相手に対してこのゲームをプレイし、あなたとあなたの対戦相手の両方が最適にプレイしていると仮定して、勝利できるかどうかを知りたいと思う。あなたは最初に移動します。 、

string solution(vector< int>& A); Nの整数からなるゼロインデックス配列を与え、

は、フォーマット「X、Y」の文字列を返し、XおよびYは、それぞれ、次のとおり

関数を書きますあなたが勝利戦略を取っていると仮定して、勝つために最初の移動で削除すべきスライスの最初と最後の位置（両端を含む）。このような勝利スライスが複数存在する場合、関数はXの値が最小のスライスを返す必要があります.Xの値が最小のスライスが2つ以上ある場合、関数は最短のスライスに戻ります。あなたが勝利戦略を持っていない場合、関数は "NO SOLUTION"を返します。

A [0] = 4 A [1] = 5 A [2] = 3 A [3] = A [4] = 2

：以下の配列を指定例えば

、

関数は "1,2"を返します。スライスを位置1から2（偶数の合計が5 + 3 = 8）から削除した後、残りの配列は[4,7,2]です。その後、相手は最初の要素（偶数の偶数の4）または最後の要素（偶数の偶数の2）を削除することができます。その後、あなたは[7]だけの配列を残すように移動することができるので、あなたの相手は法的な動きをしなくなり、失われます。可能なゲームの1つがfollowing picture

に表示されています（3 + 7 = 10の偶数の合計で）スライス「2,3」を取り除くと、次の配列についてX.

の値：

Aは[0] = 2 A [1] = 5 A [2] =

4機能「解を返すべきではありません"、あなたに勝利を保証する戦略がないので。

と仮定する：

Nは範囲[1..100,000]内の整数です。配列Aの各要素は[1..1,000,000,000]の範囲内の整数です。複雑さ：

予想される最悪ケースの時間複雑度はO（N）です。予想される最悪ケースの空間複雑度は、入力記憶域を超えて（入力引数に必要な記憶域を数えない）O（N）です。入力配列の要素は変更できます。 私はPythonでオンラインで解決策を見つけました。

def check(start, end): 
    if start>end: 
     res = 'NO SOLUTION' 
    else: 
     res = str(start) + ',' + str(end) 

    return res 

def trans(strr): 
    if strr =='NO SOLUTION': 
     return (-1, -1) 
    else: 
     a, b = strr.split(',') 
     return (int(a), int(b)) 


def solution(A): 
    # write your code in Python 2.7 

    odd_list = [ ind for ind in range(len(A)) if A[ind]%2==1 ] 

    if len(odd_list)%2==0: 
     return check(0, len(A)-1) 


    odd_list = [-1] + odd_list + [len(A)] 
    res_cand = [] 
    # the numbers at the either end of A are even 
    count = odd_list[1] 
    second_count = len(A)-1-odd_list[-2] 
    first_count = odd_list[2]-odd_list[1]-1 
    if second_count >= count: 
     res_cand.append( trans(check(odd_list[1]+1, len(A)-1-count))) 

    if first_count >= count: 
     res_cand.append( trans(check(odd_list[1]+count+1, len(A)-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(odd_list[1]+(first_count-(count-second_count))+1, odd_list[-2]))) 

    ########################################### 
    count = len(A)-1-odd_list[-2] 
    first_count = odd_list[1] 
    second_count = odd_list[-2]-odd_list[-3]-1 
    if first_count >= count: 
     res_cand.append( trans(check(count, odd_list[-2]-1))) 

    if second_count >= count: 
     res_cand.append( trans(check(0, odd_list[-2]-count-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(count-second_count, odd_list[-3]))) 



    res_cand = sorted(res_cand, key=lambda x: (-x[0],-x[1])) 

    cur = (-1, -2) 
    for item in res_cand: 
     if item[0]!=-1: 
      cur = item 

    return check(cur[0], cur[1]) 

このコードは機能し、コードと1つの関数の流れを理解できません。しかし、私はアルゴリズムの論理を理解していません。どのように問題に近づいて解決したかこれは長い作業かもしれませんが、誰でも私にアルゴリズムを説明するのに十分気をつけてください。前もって感謝します。

Answer 1

これまでのところ、奇数の数が結果を見つけるために重要であることを理解しました。特に重要な値を計算するには、最初の奇数と最後の奇数のインデックスが必要です。

"if first_count> = count"と "second_count < count < = twosum"のような比較の背後にあるロジックを理解する必要があります。

更新： 私の質問に対する解決策を見つけ出し、最終的にアルゴリズムのロジックを理解しました。

このアイデアは、アレイの対称性の背後にあります。配列が対称であれば勝つことはできません。ここで対称とは、中間に1つの奇数があり、その1つの奇数のいずれかの側に等しい数のevensがある場合の配列として定義されます。

偶数のオッズがある場合は、直接ゲームに勝つことができます。

オッズが奇数の場合は、常に配列を対称にするようにしてください。これがアルゴリズムがしようとしていることです。

今、2つのケースがあります。最後の奇数が残るか、最初の奇数が残ります。皆さんがそれを理解していない場合、私はもっと説明してくれるでしょう。ありがとう。