回答編集履歴
1
VBScript版追記
test
CHANGED
|
@@ -72,3 +72,73 @@
|
|
|
72
72
|
1 2 0
|
|
73
73
|
2 0 1
|
|
74
74
|
```
|
|
75
|
+
---
|
|
76
|
+
C++の知識がないとのことなので、VBScriptで書き直したものを載せておきます。(Excelは手元にないので)
|
|
77
|
+
入力(形式は上で説明した通り)をテキストファイルに保存したうえで、このVBScriptにドラッグ&ドロップすれば動作します。
|
|
78
|
+
こちらで試した限りでは、製品数20で10秒以上かかっています。やはり動作させるのは厳しそうです。
|
|
79
|
+
```vb
|
|
80
|
+
Option Explicit
|
|
81
|
+
Dim objFSO, objTextStream
|
|
82
|
+
Set objFSO = WScript.CreateObject("Scripting.FileSystemObject")
|
|
83
|
+
Set objTextStream = objFSO.OpenTextFile(WScript.Arguments(0))
|
|
84
|
+
|
|
85
|
+
' 製品数と、可否が1の条件の数
|
|
86
|
+
Dim aryStrings, N, M
|
|
87
|
+
aryStrings = Split(objTextStream.ReadLine())
|
|
88
|
+
N = CInt(aryStrings(0))
|
|
89
|
+
M = CInt(aryStrings(1))
|
|
90
|
+
|
|
91
|
+
' 製品 ⇒ 後ろに並べられる製品群
|
|
92
|
+
Dim edge(), i, a, b
|
|
93
|
+
ReDim edge(N - 1)
|
|
94
|
+
For i = 1 To M
|
|
95
|
+
aryStrings = Split(objTextStream.ReadLine())
|
|
96
|
+
a = CInt(aryStrings(0))
|
|
97
|
+
b = CInt(aryStrings(1))
|
|
98
|
+
edge(a) = edge(a) Or 2 ^ b
|
|
99
|
+
Next
|
|
100
|
+
objTextStream.Close()
|
|
101
|
+
|
|
102
|
+
' 製品群 ⇒ その製品群を全て並べた際に先頭になりえる製品群
|
|
103
|
+
Dim start(), j
|
|
104
|
+
ReDim start(2 ^ N - 1)
|
|
105
|
+
For i = 1 To UBound(start)
|
|
106
|
+
' 製品が1つの場合は、その要素を並べればOK
|
|
107
|
+
If (i And i - 1) = 0 Then
|
|
108
|
+
start(i) = i
|
|
109
|
+
Else
|
|
110
|
+
' 製品群内の製品それぞれについて
|
|
111
|
+
For j = 0 To N - 1
|
|
112
|
+
If i And 2 ^ j Then
|
|
113
|
+
' その製品の後ろに並べられる製品が、残りの製品群の先頭になりえるなら、
|
|
114
|
+
' その製品は先頭になりえる
|
|
115
|
+
If edge(j) And start(i Xor 2 ^ j) Then
|
|
116
|
+
start(i) = start(i) Or 2 ^ j
|
|
117
|
+
End If
|
|
118
|
+
End If
|
|
119
|
+
Next
|
|
120
|
+
End If
|
|
121
|
+
Next
|
|
122
|
+
|
|
123
|
+
' 各製品を先頭にした場合の組み合わせを1組ずつ出力
|
|
124
|
+
Dim x, y, ret
|
|
125
|
+
For i = 0 To N - 1
|
|
126
|
+
x = 2 ^ N - 1
|
|
127
|
+
' その製品が先頭になりえるなら
|
|
128
|
+
If start(x) And 2 ^ i Then
|
|
129
|
+
j = i
|
|
130
|
+
ret = ""
|
|
131
|
+
Do
|
|
132
|
+
ret = ret & j & " "
|
|
133
|
+
x = x Xor 2 ^ j
|
|
134
|
+
If x = 0 Then Exit Do
|
|
135
|
+
' 現在の製品の後ろに並べられて、残りの製品群の先頭になりえる製品を選ぶ
|
|
136
|
+
y = edge(j) And start(x)
|
|
137
|
+
For j = 0 To N - 1
|
|
138
|
+
If y And 2 ^ j Then Exit For
|
|
139
|
+
Next
|
|
140
|
+
Loop
|
|
141
|
+
WScript.Echo ret
|
|
142
|
+
End If
|
|
143
|
+
Next
|
|
144
|
+
```
|