Offline in Echtzeit schreiben 14. (28. September) http://atnd.org/events/43076 Referenzproblem "Überqueren des Umfangs" http://nabetani.sakura.ne.jp/hena/ord14crosscircle/ Implementierungsbeispiel.
Mit unbekannter Python.
Beispiele für Antworten in anderen Sprachen http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42 Sie können folgen aus.
damit.
#coding:utf-8
#tested with Python 2.7.5 and Python 3.3.2
import re
def solve( src ):
return str(len(
[ 0
for a in range( 0, len(src) )
for b in range( 0, a )
for c in range( 0, b ) if src[a]==src[c]
for d in range( 0, c ) if src[b]==src[d] ] ))
def test( samples ) :
for line in samples.splitlines():
a=re.split( "\s+", line ) # num, input, expected
if len(a) <3:
continue
actual = solve( a[1] )
ok=actual==a[2]
print( [ "ok" if ok else "***NG***", a[1:3], actual ] )
test( """
0 aabbca1bcb 14
1 111ZZZ 0
2 v 0
""")
Wie üblich werden die meisten Testdaten weggelassen.
Eine schrecklich naive Umsetzung. Das Schlimmste ist O (N ** 4), aber das reicht für dieses Problem.
Wähle 4 Punkte. Wenn der erste und der dritte den gleichen Namen haben und der zweite und der letzte den gleichen Namen haben, gibt es eine Kreuzung. Probieren Sie sie alle aus und Sie sind fertig.
Ich denke nicht, dass es der Fall sein sollte, die Listeneinschlussnotation zu verwenden, aber ich möchte sie verwenden, also verwende ich sie ohne zu zögern. Ich habe mich entschieden, es zu verwenden, aber ich war nicht an den Inhalten der Liste interessiert, also habe ich beschlossen, es mit 0 zu füllen, was mich ein wenig seltsam machte (ich fühle mich danach, aber es ist nicht Pythonista, also frage ich mich, ob es wirklich seltsam ist. Ich bin mir nicht sicher).
Wenn Sie die Reihenfolge ändern, ist der typische Fall schneller, aber der schlimmste Fall ist nicht schneller, also habe ich ihn so belassen, wie er ist.
Recommended Posts