白準-ビーズシリアルプロセス(1301)

11912 ワード
テキストリンク

質問する

N(<= 5)の異なる色のビーズを持っています.
ビーズの任意の3つの連続したビーズの色を異にしたい.
このとき、作れるネックレスの数.

アイデア


コアクリエイティブ

  • 注釈による重複計算の消去
    • 上図はRGBの3色を使用し、valのOは任意の色と仮定する.N idxの値を入力するには、異なる種類の残りのビーズの数と、以前/以前に使用したビーズの色の情報だけが必要です.
    つまり、残りのビーズを充填するには、N - 2, N - 12番目のビーズを除いて、前にどの順番でビーズを充填したかを知る必要はありません.
    このことを考慮して、下記の場合上記の場合6 idx以降の全ての場合の数を考慮し、以下の場合を考慮する.
    6 idx以前の値はやや異なるが、異なる種類のビーズの使用数と残りの数は同じである.
    この場合、6 idxにBが充填されていれば、以降の状況は既に得られており、これ以上繰り返す必要はない.6 idx以降のビーズは、残りの数と4, 5 idxのビーズの順にしか決められないので、1番ケースと2番ケースは同じです.

    実施形態

  • 7次元注記シーケンス.
  • 1,2,3,4,5次元は各ビーズの残数を表す.
  • 6,7次元は以前/以前に使用したビーズタイプを表す.

    • コード#コード#

    import sys

input = sys.stdin.readline

N = int(input())
beads = [0 for _ in range(5)]
for n in range(N):
    beads[n] = int(input())
memo = [[[[[[[-1 for _ in range(6)] for _ in range(6)] for a in range(11)] for b in range(11)] for c in range(11)] for d in range(11)] for e in range(11)]
total = sum(beads)


def memoization(size: int, pp: int, p: int) -> int:
    if size == total:
        return 1

    if memo[beads[0]][beads[1]][beads[2]][beads[3]][beads[4]][pp][p] != -1:
        return memo[beads[0]][beads[1]][beads[2]][beads[3]][beads[4]][pp][p]
    # 한번 확인한 경우, 다시 확인할 필요가 없다.
    ret = 0

    for i, b in enumerate(beads):
        if i == p or i == pp: continue
        if b == 0: continue
        beads[i] -= 1
        ret += memoization(size + 1, p, i)
        beads[i] += 1

    memo[beads[0]][beads[1]][beads[2]][beads[3]][beads[4]][pp][p] = ret
    return ret

print(memoization(0, -1, -1))
    Swiftにおける構造体とclassの混用
    [Git] git merge and conflict