Distributed Code Jam 2017 Round1

2017-05-15 | [Competitive programming]

B

スタックを連続した区間に分割し，各区間ごとに「最初と最後，およびこの区間内での移動距離」を並列で求めた． 後で考えると単に S[i] > S[i+1] なる i の個数を数えればいいだけだった．

C

与えられる数字列の部分列をとって，元の桁数になるまで後ろに 0 をくっつけるのと等価である． これは次のようにすれば，最大の値が得られる：

• 現れる 9 をすべて部分列に含める．
• いかなる 9 よりも後ろにある 8 をすべて部分列に含める．
• いかなる 9, 8 よりも後ろにある 7 をすべて部分列に含める．
• … これは，9, 8, …, 1 に対して「ある範囲内での個数」「最も右の現れ」を求められればいいので，この値の各計算を並列化した．

D

二分探索を二重に使うと，2 つの列をマージした後の列において i 番目の値が何であるかを求めることができる． よって，マージ後の列における担当範囲を各ノードに決めておくと，2 つの列において対応する範囲を求めることができるから，後は普通にマージする．

E

まだ壊れていないノードを使うと，ある範囲に query of death が含まれるかどうかと，含まれないならばその範囲の総和を求めることができる． （query of death が含まれるかどうかは，同じビットに何回もアクセスして，一貫した値が返ってこないかを見ればよい）

区間全体を 99 等分し (ノードのうち 1 つは司令塔のみに使う)，各ノードが 1 つの部分をすべて調べるようにする．上の方法により，どの区間に query of death があるかと，他の区間の総和はわかるので，次調べるべき探索範囲を 1/99 くらいにすることができる． 次は，残っている区間全体を 98 等分し，まだ壊れていないノードに各部分を割り当てる．すると，探索範囲はさらに 1/98 になる． これを，区間が残っている限り繰り返す．

結果

全部通って 100 点，2 位．