1

私はCodechefでいくつかの練習問題をやっていた。あいまいな順列と呼ばれるこの問題があります：

これに対する私の解決策は次のとおりです。

while 1:
   cnt = int(raw_input())
   if cnt == 0:
      break
  vals = [int(u) for u in raw_input().split(' ')]
  valr = []
  for i in range(cnt):
    valr.append(vals.index(i+1)+1)
  if vals == valr:
    print 'ambiguous'
  else:
    print 'not ambiguous'

Trypython.orgでチェックアウトしたところ、期待どおりに機能しました。しかし、Codechefでソリューションを送信すると、タイムアウトになりました。

私の質問はこれです。コードに何か問題がありますか（/改善される可能性があります）、またはテストマシンのsysinと出力を処理する特定の方法はありますか？

[編集]受け入れられた解決策はいくつかの素晴らしい提案を提供し、私はコードロジックを再考し、それに応じてコードを変更しました。コードは時間内に実行されるようになりましたが、間違った答えで失敗します（ただし、私のテストケースでは間違った答えを複製することはできません）。アドバイスありがとうございます。

import sys
def ambigcheck(lis):
   amb = 'ambiguous'
   for i in range(1,len(lis)+1):
       if lis[lis[i-1]-1] != i:
          amb = 'not ambiguous'
          break
   return amb 
while 1:
   cnt = int(sys.stdin.readline())
   if cnt == 0:
       break
   vals = [int(u) for u in sys.stdin.readline().split(' ')]
   sys.stdout.write(ambigcheck(vals))
4

1 に答える 1

4

使用しないでくださいraw_input。sys.stdin：をイテレータとして使用するかread()、1回使用します。そして、sys.stdout.writeの代わりに使用してprintください。一度だけ使用してみてください。出力全体を事前に計算し、後で画面に書き込みます。

これにより、Pythonで最速のI/Oが得られます。

その他のヒント：

  • 新しい順列を作成する必要はありません。元の順列の要素に適切なインデックスがあるかどうかを確認するだけです。
  • 完全なチェックを行う必要はありません。少なくとも1つの要素に適切なインデックスがない場合、順列はあいまいではありません。
  • メソッドを避け.index()、値ではなくインデックスでチェックする
  • 奇数行のみを読み取ることで、入力をさらに効果的に処理できますitertools.islice（Pythonではアイテムの数は必要ありません）
于 2012-05-31T07:05:03.990 に答える