1

ここで説明されている装置の問題を解決しようとしています。解決策はありますが、制限時間である2秒以上かかります。コードを最適化して速度を上げようとしましたが、2 秒の制限内で取得できません。

import sys
import math

for line in sys.stdin:

    line = line.strip("\n").split(" ")
    numSwitches = int(line[0])
    numPics = int(line[1])

    wiring = {}
    inValid = False
    for i in range(numPics):
        if (inValid):
            break
        x = sys.stdin.readline().strip("\n")
        f_x = sys.stdin.readline().strip("\n")

        x_ones = 0
        f_x_ones = 0

        digit = 0
        for i in range(numSwitches):
            if f_x[i]=='1':
                digit += 2**(numSwitches-i-1)
                f_x_ones += 1

        for switch in range(numSwitches):
            if (x[switch]=='1'):
                x_ones += 1
                if not (switch in wiring.keys()):
                    wiring[switch] = digit
                else:
                    wiring[switch] &= digit

        if x_ones != f_x_ones:
            inValid = True
            break

    if not inValid:
        for i in wiring.values():
            if i==0:
                inValid = True
                break

    for possibilities in set(wiring.values()):
        frequency = wiring.values().count(possibilities)
        if frequency>1:
            oneBits = 0
            while (possibilities>0):
                oneBits += (possibilities%2==1)
                possibilities /= 2
            if oneBits < frequency:
                inValid = True
                break

    if not inValid:
        print math.factorial(numSwitches-numPics)%1000003
    else:
        print 0

問題に取り組むべきだった方法の提案や、現在のコードを最適化する方法についての情報を探しています。

注: 次のテスト ケースを検討してください。

3 2
110
011
011
011

私のコードは、次の方法で無効であることがわかりました。まず、最初の写真（110、011）に遭遇したとき。配線辞書には、次のキーと値が割り当てられます。

wiring[0] = 011
wiring[1] = 011

これは、1 番目と 2 番目のスイッチが 2 番目または 3 番目のライトのいずれかを点灯できることを意味します。2枚目の写真(011、011)に遭遇。配線は次のように更新されます。

wiring[1] = 011 & 011 = 011
wiring[2] = 011

ここで、配線の状態が、3 つのスイッチすべてが 2 番目と 3 番目のライトのいずれかを点灯できることを示していることを確認します。3 つのスイッチが 3 つのライトを点灯する必要があるため、これは矛盾しています。ここでは、2 つのライトを点灯する 3 つのスイッチがあります。

4

1 に答える 1

0

これで解決できると思いますが、よくわかりません。詳しくは明日説明します

import numpy as np
from operator import mul

def apparatus(n, m, x, y):
    if not m:
        return np.math.factorial(n) % 1000003
    result = 1
    tmp = np.matrix([False] * x.shape[1])

    for i in xrange(x.shape[1]):
        if tmp[0, i]:
            continue
        tmp0 = np.prod(x[:, i] == x, 0)
        tmp1 = np.prod(x[:, i] == y, 0)
        if np.sum(tmp1) != np.sum(tmp0):
            return 0
        result *= np.math.factorial(np.sum(tmp1))
        result %= 1000003
        tmp += tmp1

    return result

x = np.matrix([[True, True, False]])
y = np.matrix([[False, True, True]])
print apparatus(3, 1, x, y)

x = np.matrix([[True, False, False, False], [False, False, False, False]])
y = np.matrix([[True, False, False, False], [False, False, True, False]])
print apparatus(4, 2, x, y)

print apparatus(1000, 0, [], [])
于 2015-11-22T23:21:35.700 に答える