Scalaを使ってコインを反転する

Question

私はscalaのcodechefからFlippingコインの問題を解決しようとしています。問題文は次のとおりです。

Nコインがありますが、0からNまで番号が付けられ、テーブルの上に保管 - Initally 1. 、各コインが尾を続けています。 操作の2つのタイプを実行する必要があります：1）AとBの間に番号が付けられたすべてのコインを反転します。これは、コマンド "0 A B"によって表される です。2）AとBの間の 番のコインこれは、コマンド "1 A B"によって表されます。入力：最初の行には2つの整数NとQが含まれています。 次のQ行のそれぞれは、前述の のように "0 A B"または "1 A B"のいずれかの形式です。

出力： "1 A B" という形式の各クエリの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 = Q < = 100000 0 < = A < = B < = N - 最も単純な方法で1

、私は次のようにScalaでintの配列を初期化することを考えた：

var coins = new Array[Int](1000) 

Iコマンド0 ABが発生した場合、I私は、コマンド1 ABが発生した場合、私はB + 1までAから配列のスライスを取り、数をカウントします

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

次のように単にBまで+ 1にAのインデックスを設定します与えられたスライスと

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

この操作は、最悪の場合にはO（n）を取ると、どうやらこれは対数時間で解決するように最適化することができるように思え：次のように私はそれを行います。

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

Answer 1

最近、スカラーに関することはよく分かりませんが、O（log（n））に関するより一般的な質問に対する答えを提案できます。典型的には、このようなアルゴリズムはツリーを使用しています。

コインを葉にしてバランスの取れたツリーを作成すると、コインの総数とそのノードの下の葉の頭の数を各ノードに格納できます。ノード情報から訪問するために出発するコインを反転させ、O（n）時間（あなたはまだコインを反転する必要があります）で作業するコードを想像することができます。フリッピングコードがノードデータを更新した場合、ノード情報を使用できるため、ヘッド数はO（log（n））になります。リーフに行く必要はありません。

ですから、あるコマンドではO（n）、もう一方のコマンドではO（log（n））となります。

でも、それ以上にうまくいく可能性があります。フリップ操作をO（log（n））することもできます。これを行うには、各ノードに「反転」フラグを追加します。設定されている場合は、その点の下のすべてのノードが反転されます。いくつかの帳簿の詳細がありますが、一般的な考え方はそこにあります。

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

Answer 2

一方クリーンな方法は、セット内の整数値は、ボード上のヘッドのインデックスを表しBitSet、通りである

おかげ。

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 

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

あなたは、同様の範囲で頭を数えることができます。そして、あなたはこのような範囲でコインを反転することができます

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