11

先週の金曜日、フランスのプログラミング コンテストで、次のような紙の折り方の問題が出されました。

正方形の紙と折りパターンが与えられた場合、パターンに関してシートを累積的に (半分に) 折り畳んだ結果として生じる層の順序を与える関数「fold(pattern)」を記述します。

それはあまり明確ではないかもしれないので、少し説明させてください (私を助けるためにそこまで行っても構わないと思っているなら、正方形の紙を手元に用意しておくと理解するのに役立つかもしれません)。

正方形の紙に N*N グリッドを描画し、内側のすべての正方形に番号を付けるとします。パターン「LTRB」が与えられた場合、この紙を縦に半分に折り、左の部分を右の部分に重ねます。次に、それを水平に折り、上部を下部に重ねます。次に、もう一度縦に折り、右の部分を左の部分の上に置きます。最後に、それを水平に折り、下部を上部に重ねます。これにより、1 枚の正方形と N^2 層のサイズの紙が残ります。予想される答えは、元の各正方形の結果の順序です。

たとえば、正方形の紙に 2*2 のグリッドを描画し、内側の各正方形に 1 から 4 (左上から右下、水平方向) の番号を付け、パターン "LT" を指定すると、次のようになります。この出来事：

fold("LT"):

 1 | 2   L  1,2  T
---|--- ==> --- ==> 2,1,3,4
 3 | 4      3,4

および「RB」パターンを使用します。たとえば、次のようになります。

fold("RB"): 

 1 | 2   R  2,1  B
---|--- ==> --- ==> 3,4,2,1
 3 | 4      4,3

おそらくご想像のとおり、基本的には N*N 行列の再帰的変換に要約されます。これは簡単な部分でした。これが私の解決策です。

http://ideone.com/QaXGq

次に興味深い部分です。

  • 関数 unfold(order) を書いて、与えられた層の順序付けに対して、この順序付けを生成したパターンを与えます。unfold(fold("LRTB")) => "LRTB" であることに注意してください

そして、私の脳はしばらくの間機能を停止し、十分な速さで解決策を見つける時間がありませんでした (合計 4 時間から残り 2 時間)。

私の最初のアイデアは次のとおりです。

  1. 力ずくでやってみてください。入力の長さが N^2 であることがわかっているため、初期行列を作成し、入力と同じ次数に達するまで可能なすべての折り畳みを試すことができます。O(4^N) の複雑さ、実行不可能。

  2. ブルートフォースリバース。入力から始めて、正しい初期状態に到達するまで展開の可能性をすべて試します。少し良くなりましたが、それでも遅すぎます。

  3. ???

誰にもアイデアがありますか？

4

2 に答える 2

9

各ステップで、リストの最初の要素と最後の要素を知る必要があるだけです。最初の要素が最後の要素の左側にある場合、折りたたみ方向は左でした (右、上、下と同じ)。

于 2012-05-07T16:39:36.947 に答える
2

これが私の試みです。とても簡単に聞こえますが、いつものように、悪魔は細部に宿ります。

まず、fold:

  type Matrix = IndexedSeq[IndexedSeq[IndexedSeq[Int]]]

  def initial(folds: Int): Matrix = {
    val sideLen = math.pow(2, folds / 2).toInt
    (1 to sideLen * sideLen) map (Vector(_)) grouped sideLen toIndexedSeq
  }

  def leftFold (m: Matrix): Matrix = m map { r => 
    val (a, b) = r splitAt (r.size / 2) 
    (a.reverse, b).zipped map (_.reverse ++ _)
  }

  def rightFold(m: Matrix): Matrix = m map { r => 
    val (a, b) = r splitAt (r.size / 2) 
    (b.reverse, a).zipped map (_.reverse ++ _)
  }

  def topFold   (m: Matrix): Matrix = leftFold(m.transpose).transpose
  def bottomFold(m: Matrix): Matrix = rightFold(m.transpose).transpose

  def fold(input: String): Seq[Int] = {
    def go(in: String, m: Matrix): Seq[Int] = in match {
      case "" => m(0)(0)
      case s  => go(s.tail, s.head match {
        case 'L' => leftFold(m)
        case 'R' => rightFold(m)
        case 'T' => topFold(m)
        case 'B' => bottomFold(m)
      })
    }
    go(input, initial(input.length))
  }

第二に、unfold:

  def unfold(input: Seq[Int]): String = { 
    val m0: Matrix = Vector(Vector(Vector(input: _*)))
    val sideLen = math.sqrt(input.length).toInt 

    def go(m: Matrix, out: String): String = {
      val tl = m.head.head
      val bl = m.last.head
      val tr = m.head.last
      if (m.length == sideLen && m.head.length == sideLen) out.reverse
      else if (tl.head == tl.last - 1)       go(leftUnfold(m),   out + 'L')
      else if (tr.head == tr.last + 1)       go(rightUnfold(m),  out + 'R')
      else if (tl.head == tl.last - sideLen) go(topUnfold(m),    out + 'T')
      else if (bl.head == bl.last + sideLen) go(bottomUnfold(m), out + 'B')
      else sys.error("no fold found " + m) 
    }
    go(m0, "")
  }    

  def leftUnfold (m: Matrix): Matrix = m map { r =>
    val (a, b) = r.map(e => e.splitAt(e.size / 2)).unzip
    a.map(_.reverse).reverse ++ b
  }

  def rightUnfold(m: Matrix): Matrix = m map { r =>
    val (a, b) = r.map(e => e.splitAt(e.size / 2)).unzip
    b ++ a.map(_.reverse).reverse
  }

  def topUnfold   (m: Matrix): Matrix = leftUnfold (m.transpose).transpose
  def bottomUnfold(m: Matrix): Matrix = rightUnfold(m.transpose).transpose

私はいくつかのテストを実行しましたが、合格しました...

于 2012-05-08T05:12:32.970 に答える