こんにちは。
ICPC国内予選参加記で書いた通り、F問題の自分の解法を書きます。
他チームでFを解いた先輩に軽く説明したら
後輩チームのF解法イミフ過ぎてワロタ
— きひろちゃん (@aki33524) 2017年7月14日
という反応が返ってきた解法です。
全く証明はしていない黒魔術なので注意してくださいね。
Step0: パターン全列挙
以下、必ず0-indexedで考えるので、与えられるiとjは最初に1引いてあるものとします。
まず、長さ8のリボンを折る方法8通りについて、最終的に上から何番目に左から何番目の部分が来るかを書いてみます。
このパターンを眺めていると、「i番目にjがある」というパターンは必ず1つしかないので、一意に決まるんだろうな、という気がします。
この表で「上からi番目にjがあるものは左から何番目？」という情報が分かれば、LR列（出力すべき操作の列）が分かるのですが、難しそうです。
かなり長い時間この表の性質を突き止めようとしましたが、無理でした。
分かったことは、元の列を操作後の列に変換する写像は、もう一回行えば元に戻る、という性質ぐらいです（つまり、どの操作でも、元の並びと結果は「2数のペアの入れ替え」か「そのまま」しか起こらない、ということです。長さ3以上のループが無いということ）。
最終的に、この表の大部分は使わないのですが、これが最後に繋がる伏線になるのです……
Step1: 最終状態から巻き戻す
サンプル1では、最終状態で「2番目に1がある」という状態になっている必要があります（0-indexedにしているので日本語が変です。）
したがって、最終状態の2番目を1にして、それに8パターンの折り方の逆再生を適用し、元の列がどうであったかを確認しましょう。
最終状態で上から「ABCDEFGH」だったときに、Cの位置に1が来ているということは、これを展開したときには、Cの位置は左から1番目（0番目の隣なので実質2番目）となるはずです。
たとえば、一番左の例（LLLの操作でABCDEFGHになる例）では、元の並びは「GBCFEDAH」になるので、Cの位置は0-indexedで2番目です（つまり左から3番目）。
Cの位置が1になるのは、LRRの折り方であることが分かります。正解ですね。
ここで、Cの位置を表す数字を2進数で表現してみましょう。
010 LLL
110 RLL
000 LRL
100 RRL
011 LLR
111 RLR
001 LRR
101 RRR
こう見ると、規則性がありそうですね。
L=0, R=1とすると、操作の列とCの位置を表すビット列が対応しそうですが、2桁目だけおかしいですね。
つまり、この「Cの位置を表す2進数」に010をXORしてやると、以下のようになります。010
000 LLL
100 RLL
010 LRL
110 RRL
001 LLR
101 RLR
011 LRR
111 RRR
2進数の列をLR列が完全に対応しています！
さて、ここで出てきた010、すなわち2という数字はどこから来たのでしょうか？
これは容易に想像がつきます。おそらく「Cの位置」すなわち「0-indexedでの上からの位置」でしょう。すなわち今回の「i（デクリメント済）」であろうと。
つまり、入力のi,jをデクリメントした上で、「i XOR LR列 = j」となるようなLR列が分かれば、それが答えなのです。
それを求めるのは容易で、両辺にiをXORしてやればいいのです。XORは交換可能で、同じ数のXORは0になり、0とのXORはそのままになる（0はXORにおける単位元）なので。
そうすると、「LR列 = i XOR j」という見事な式が得られます。ここまで証明無しです（ここからも証明無しです）。
実際、サンプル1では、i,jをデクリメントすると、i = 2, j = 1 となるので、010^001=011となり、L=0, R=1とすると”LRR”となり、正解であることが分かります（^はXOR演算子です）。
ですが、F問題はさすがにこんな単純な問題ではないだろうと思い、2つ目のサンプルでi=577、j=2213の2進数表示を手計算し、XORしたところ、どうも答えと一致しません。
そう単純にはいかないようです。
さて、上の図に、CではなくAの位置（つまり上から0番目）を書いてみましょう。
この列「62047351」をまた2進数表示して、LR列と見比べてみましょう。
110 LLL
010 RLL
100 LRL
000 RRL
111 LLR
011 RLR
101 LRR
001 RRR
さて、これをL=0,R=1にするためにXORする必要がある数字は何でしょうか。
答えは110、すなわち「6」です。あれ、最終状態でのAの位置を表す「0」ではないんですね。
つまり、「i XOR LR列 = j」ではなく、謎の関数f()が存在して、「f(i) XOR LR列 = j」となるのではないか、と思いました。
したがって、解は「LR列 = f(i) ^ j」で得られるのではないかと。
このf(i)の正体を突き止める旅が始まります。（実はこの時点でf(i)の正体は分かるのだが、自分は気付かず……）
最終状態での上からの位置が「2」のときは、LR列に「2」をXORしたものが出てきて、「0」のときは「6」をXORしたものが出てくる……
「2」なら「2」、「0」なら「6」、……
ん？ これはもしや……
Step2: 謎の関数 f() の正体を突き止める
さて、今度は上から0-indexedで5番目の位置、つまり”F”の位置を書き込んでみましょう。
同じように、2進数表示とLR列を比較します。
011 LLL
111 RLL
001 LRL
101 RRL
010 LLR
110 RLR
000 LRR
100 RRR
さて、L=0,R=1とするためにXORすべき数字は何でしょうか？
答えは011、すなわち「3」です。
このあたりでやっと気づきました。
LLLを000にしたいのだから、XORすべき数字は「LLLのときに上からi番目になる部分が左から何番目にあったか」を表す数字なのですね。
f(2)=2、f(0)=6、f(5)=3、となるわけですが、ここで最初に載せた全パターン列挙の図を見てみましょう。
この、最も左の列「61254307」が、謎の関数f()の正体だったのです！！！
この列は「LLLの操作をした結果の上からi番目には、元々左から何番目だった部分が来ているのか」を表す列です。「f(i)=この列の第i要素」です。
謎の関数f()が謎ではなくなったので、これでACですね。いやー、よかったよかった。
……というわけにはもちろんいきません。
Step3: 関数f()の第i要素を瞬時に再現する
関数f()を表す列は、長さが2^Nあるので、N=60では時間もメモリも足りません。
つまり、f(i)の値を、桁数オーダーぐらいで得る必要があります。（もっと時間かかってもいいですがたぶん桁数オーダーになるだろうと思っていました）
とりあえず、N=3の場合のf列「61254307」を2進数表示してみます。
110
001
010
101
100
011
000
111
この羅列からすぐに規則性を見出せると、頭がいいですね。私には無理でした。
そのままになっている部分と入れ替わってる部分の位置に規則性があるか、とか、N=2の場合の列から逐次的に構成できないか、とか、FFTのバタフライ計算に似てるけど覚えてないな、とか、いろいろ考えました。
そしてやっと「最下桁が01交互に並んでいる」ということに気づき、2桁目はどうか、と考えてみました。
すると、以下のような規則性があることが分かりました。
1 1 0
0 0 1
0 1 0
1 0 1
1 0 0
0 1 1
0 0 0
1 1 1
0桁目は、下から「10101010」が並んでいます。
1桁目は、下から「1010」が並んだあと、それが上下反転して続いています。
2桁目は、下から「10」が並んだあと、それが反転して続き、さらに全体が反転して続いています。
（桁数を0-indexedで書いています）
すなわち、下から見ていくと、各桁「1010…」が並ぶ部分と「0101…」が並ぶ部分が交互に現れているのです。先頭（一番下）は「1010…」です。
0-indexedでd桁目では、各部分が2^(N-d)の長さで続いています。（上の例ではN=3）
下から見ていくために、上からi番目、という部分を、下からk番目、というように言い換えます。k=2^N-1-iです。（i,kともに0-indexedのため、iはデクリメント済み）
すると、f(i)のd桁目は「kを2^(N-d)で割った商の偶奇」でまず場合分けできます（1010…の部分か0101…の部分か）。
「kを2^(N-d)で割った商の偶奇」は「kのN-d桁目」になるので、ビット演算ですぐに計算できますね。
さらに、1010…にいる場合は、kが偶数ならf(i)のd桁目が1, kが奇数ならd(i)のd桁目が0になりますね。各繰り返し部分の長さは必ず偶数なので。
0101…にいる場合はその逆になります。
したがって、d=[0,N)に対して、「kのN-d桁目」と「kの0桁目」で4通りに場合分けして、f(i)のd桁目が0か1かを計算します。
こうすることで、f(i)をO(N)で計算することができます。
こうして得られたf(i)とjをXORしたものが答えになります。（証明無し）
「f(i) ^ j」の上の桁から見ていって、0ならL、1ならRを出力すればおしまいです。
N=59であるサンプルの3つ目がぴったり合ったので「証明してないけどこれはいけるやろ」と思って投げました。通って良かったです。
こんな方法でF問題を通しました。その後先輩の解法を聞いたら、自分の黒魔術解法が想定解法なら大ブーイングものだな、と思いました。
所々小さなミスがあるかもしれません（桁の数が1ずれてるとか）。
実際にはいろんな横道に入って無駄なこともたくさんしました。この黒魔術は試行錯誤の賜物です。
とにかく考察に長い時間を要したので、その間にEを通してくれてPCの遊休時間を無くしてくれたsnteaさんと、Fの考察の補助をしてくれたMさんに感謝です。
自分と同じ解法の人がいないのか気になりますが、講評で言及されたししますかね……？