summerFestivalContest Dragon Curve - ferinの競プロ帳

考えたこと

今年のICPC国内予選の問題を思い出す。Nが大きいし左右ににぶたんしていってO(logN)かなあと思う。
実際に折ったりしてN＝4くらいまでどうなってるか書き出してみる。
今までに折ったもの + 谷 + 今までに追ったものの反転という規則になっていることがわかる。
区間[low, high)をdを含むように範囲を二分の一ずつ狭めていくとする。
区間の右半分を選んでいたか、左半分を選んでいたかを覚えておいてd番目が選ばれたとき山折りか谷折りかを決める。
mid = (low+high)/2 が d のとき、右半分を選択していたら山折り、左半分を選択していたら谷折りになる
最終的に区間の要素が1つになったときも同様に決定できる

区間をhigh = 2^nとして初期化したいがオーバーフローするので不可能。
10^18 < 2^63よりn=63になるまで左側にあり続ける。よってnは最大63と考えられる。
あとは二分割していきながら答えを求める。

罠

1LL<<64でオーバーフローさせていた。

学び

数学でがんばるとO(1)でできる。