1

私はscalaのcodechefからのフリッピングコインの問題を解決しようとしています。問題の説明は次のとおりです。

テーブルには0からN-1までの番号が付けられたN枚のコインがあります。最初は、各コインはテールアップで保持されます。2種類の操作を実行する必要があります：1）AとBの間に番号が付けられたすべてのコインを裏返します。これはコマンド「0A B」で表されます。2）AとBの間に番号が付けられたコインの数に答えます。これは、コマンド「1AB」で表されます。入力：最初の行には、NとQの2つの整数が含まれています。次のQ行はそれぞれ、上記のように「0AB」または「1AB」のいずれかの形式です。

出力：対応するクエリに必要な回答を含む「1AB」形式のクエリごとに1行を出力します。

サンプル入力：

 4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3

サンプル出力：

0
1
0
2
1

制約：1 <= N <= 100000 1 <= Q <= 100000 0 <= A <= B <= N-1

最も単純な方法で、私は次のようにscalaでIntの配列を初期化することを考えていました。

 var coins = new Array[Int](1000)

コマンド0ABに遭遇した場合、次のようにB+1が1になるまでAのインデックスを設定します。

 for(i <- 5 until 8){
      coins(i) = 1
    }

コマンド1ABに遭遇した場合、AからB + 1までの配列のスライスを取得し、その特定のスライス内の1の数をカウントし、次のように実行します。

val headCount = coins.slice(5,8).count(x => x == 1)

この操作は最悪の場合O（n）を取るようであり、明らかにこれは対数時間で解くように最適化することができます。

誰かが私がここで間違っているかもしれないことを指摘できますか、そしてこの問題を最適な方法でどのように解決できますか？

ありがとう

4

2 に答える 2

2

最近は scala についてあまり知りませんが、O(log(n)) に関するより一般的な質問に対する回答を提案できます。通常、そのようなアルゴリズムはツリーを使用しますが、ここでもそうできると思います。

コインを葉としてバランスの取れたツリーを構築すると、各ノードにコインの総数とそのノードの下の葉の表の数を格納できます。ノード情報からどのリーフを訪問するかを計算し、O(n) 時間で動作するコインを投げるコードを想像できます (コインを投げる必要があります)。しかし、フリッピングコードがノードデータも更新した場合、ノード情報を使用できるため、ヘッドの数は O(log(n)) になります。リーフに移動する必要はありません。

これにより、一方のコマンドで O(n) が得られ、もう一方のコマンドで O(log(n)) が得られます。

しかし、あなたはそれよりもうまくいくことができます。フリップ操作 O(log(n)) も作成できると思います。これを行うには、各ノードに「反転」フラグを追加します。設定すると、そのポイントより下のすべてのノードが反転します。簿記の詳細がいくつかありますが、一般的な考え方はそこにあります。

これを論理的な結論に導くと、少なくとも最初は葉を実際に保存する必要はありません。コマンドを処理するときに必要な詳細レベルでノードを追加するだけです。この時点で、基本的にコメントに記載されている間隔ツリーがあります。

于 2012-05-01T22:50:26.273 に答える
0

これをモデル化する明確な方法の 1 つBitSetは、セット内の整数値がボード上のヘッドのインデックスを表す として使用することです。次に、次のような範囲でコインを投げることができます。

def flip(coins: BitSet, a: Int, b: Int) = coins ^ BitSet(a to b: _*)

同様に、範囲内の頭を数えることができます。

def heads(coins: BitSet, a: Int, b: Int) = (coins & BitSet(a to b: _*)).size

または（おそらくより高速な）変更可能なjava.util.BitSetバージョン：

import java.util.BitSet

def flip(coins: BitSet, a: Int, b: Int) { coins.flip(a, b + 1) }
def heads(coins: BitSet, a: Int, b: Int) = coins.get(a, b + 1).cardinality

これは必ずしも最適ではありませんが、ビットを反転しているだけなので、かなり効率的なアプローチです。

于 2012-05-01T21:24:54.797 に答える