無限行W列のグリッドで、2人ゲームが行われる。このゲームでは2人交互に長方形のブロックを上から落とし、ブロックの各列は一番下か他のブロックにつくまで落下を続ける。ブロックを落とすことである列の高さがHを超えたとき、そのブロックを落としたプレイヤーに1列につき1ポイント入る。すべての列がHを越えたとき多くのポイントを獲得している方が勝者になる。あるゲームでどこにブロックが置かれたかの記録が順番にN個与えられるので、ゲームの勝敗を求めよ。各列の高さを管理しつつ、並列二分探索をする。一点取得が高速でできるデータ構造が欲しい。区間和取得が可能な普通のBITで実現できる。r]に一律nを足すときはtable[l]にnを足し、table[r+1]に-nを足す。一点取得ともにO(logW)でできるようになる。次にある1列のみにおいてどちらが得点を得たかを判定してみる。これは前述のBITがあればブロックのクエリを二分探索してO(NlogNlogW)で求めることができる。この二分探索を全部の列で行うことを考えると、普通にやったらO(NWlogNlogW)になって全く間に合わない。これを全部並列に行うことで計算量を落とすことができる(並列二分探索)。具体的には以下のような手順で行う。middleはどこか」を覚えておく。lowの再計算を行う。ブロックを最後まで積み終わったら、また最初に戻って積むことを繰り返す。全部の二分探索が収束したら終わり個別の二分探索はlogN回で収束するため、ブロックの積みは高々logN回までしか繰り返されない。各繰り返し内でBITによるブロックのシミュレートはO(NlogW)かかるため、このパートはO(NlogNlogW)になる。各二分探索の保持を平衡二分木とかでやると一回の処理がO(logW)ででる。W個の二分探索それぞれがlogN回行われることになるので二分探索を捌くのはO(WlogNlogW)になる。2つのパートを合わせてO((N+W)logNlogW)となる。(たぶん)感想AGC002Dの解説で並列二分探索を知り、よくわからずにいろいろググってたらこの問題が並列二分探索の例題として挙げられていたのを見つけたので解いてみました。並列二分探索は頭良すぎて理解した瞬間感動しました。実装面の細かい話として最初各にぶたんを溜めておくところで連想配列内の動的配列に入れてたんですが、偏った入力で同じところへのpushがたくさん発生すると動的配列の伸長が起こりまくってクソ遅くなってしまったところ、平衡二分木に切り替えたらまともな速度になりました。何気にyukicoderの問題記録を書くのこれが初めての気がします。yukicoderも結構解いてるんですがブログに問題記録を書く習慣をつける前に適正レベルの問題を解きつくしてしまった感じなのであまり書く機会がありませんでした。今後もちょうどいいやつがあれば書いていきたいですね。数直線の原点上に人が2人いる。N要素の数列AとM要素の数列Bが与えられる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。