競プロTweetPocketこんにちは。ICPC国内予選参加記で書いた通り、F問題の自分の解法を書きます。2017年7月14日という反応が返ってきた解法です。証明はしていない黒魔術なので注意してくださいね。以下、必ず0-indexedで考えるので、与えられるiとjは最初に1引いてあるものとします。長さ8のリボンを折る方法8通りについて、最終的に上から何番目に左から何番目の部分が来るかを書いてみます。このパターンを眺めていると、「i番目にjがある」というパターンは必ず1つしかないので、一意に決まるんだろうな、という気がします。この表で「上からi番目にjがあるものは左から何番目?」という情報が分かれば、LR列(出力すべき操作の列)が分かるのですが、難しそうです。長い時間この表の性質を突き止めようとしましたが、無理でした。分かったことは、元の列を操作後の列に変換する写像は、もう一回行えば元に戻る、という性質ぐらいです(つまり、どの操作でも、元の並びと結果は「2数のペアの入れ替え」か「そのまま」しか起こらない、ということです。長さ3以上のループが無いということ)。最終状態から巻き戻すサンプル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進数で表現してみましょう。RRRこう見ると、規則性がありそうですね。R=1とすると、操作の列とCの位置を表すビット列が対応しそうですが、2桁目だけおかしいですね。この「Cの位置を表す2進数」に010をXORしてやると、以下のようになります。RRR2進数の列をLR列が完全に対応しています!さて、ここで出てきた010、すなわち2という数字はどこから来たのでしょうか?これは容易に想像がつきます。「Cの位置」すなわち「0-indexedでの上からの位置」でしょう。今回の「i(デクリメント済)」であろうと。j」となるようなLR列が分かれば、それが答えなのです。それを求めるのは容易で、両辺にiをXORしてやればいいのです。XORは交換可能で、同じ数のXORは0になり、0とのXORはそのままになる(0はXORにおける単位元)なので。j」という見事な式が得られます。ここまで証明無しです(ここからも証明無しです)。R=1とすると”LRR”となり、正解であることが分かります(^はXOR演算子です)。F問題はさすがにこんな単純な問題ではないだろうと思い、2つ目のサンプルでi=577、j=2213の2進数表示を手計算し、XORしたところ、どうも答えと一致しません。単純にはいかないようです。上の図に、CではなくAの位置(つまり上から0番目)を書いてみましょう。この列「62047351」をまた2進数表示して、LR列と見比べてみましょう。RRRさて、これをL=0,R=1にするためにXORする必要がある数字は何でしょうか。答えは110、すなわち「6」です。あれ、最終状態でのAの位置を表す「0」ではないんですね。j」となるのではないか、と思いました。j」で得られるのではないかと。このf(i)の正体を突き止める旅が始まります。正体を突き止めるさて、今度は上から0-indexedで5番目の位置、つまり”F”の位置を書き込んでみましょう。同じように、2進数表示とLR列を比較します。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ですね。いやー、よかったよかった。......というわけにはもちろんいきません。関数f()の第i要素を瞬時に再現する関数f()を表す列は、長さが2^Nあるので、N=60では時間もメモリも足りません。f(i)の値を、桁数オーダーぐらいで得る必要があります。(もっと時間かかってもいいですがたぶん桁数オーダーになるだろうと思っていました)とりあえず、N=3の場合のf列「61254307」を2進数表示してみます。110001010101100011000111この羅列からすぐに規則性を見出せると、頭がいいですね。そのままになっている部分と入れ替わってる部分の位置に規則性があるか、とか、N=2の場合の列から逐次的に構成できないか、とか、FFTのバタフライ計算に似てるけど覚えてないな、とか、いろいろ考えました。「最下桁が01交互に並んでいる」ということに気づき、2桁目はどうか、と考えてみました。すると、以下のような規則性があることが分かりました。10桁目は、下から「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桁目」になるので、ビット演算ですぐに計算できますね。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したものが答えになります。j」の上の桁から見ていって、0ならL、1ならRを出力すればおしまいです。N=59であるサンプルの3つ目がぴったり合ったので「証明してないけどこれはいけるやろ」と思って投げました。こんな方法でF問題を通しました。その後先輩の解法を聞いたら、自分の黒魔術解法が想定解法なら大ブーイングものだな、と思いました。所々小さなミスがあるかもしれません(桁の数が1ずれてるとか)。実際にはいろんな横道に入って無駄なこともたくさんしました。この黒魔術は試行錯誤の賜物です。考察に長い時間を要したので、その間にEを通してくれてPCの遊休時間を無くしてくれたsnteaさんと、Fの考察の補助をしてくれたMさんに感謝です。...記事を読む競プロ用C++変数ダンプ関数・マクロを作ったよこんばんは、かなり久しぶりの投稿になってしまいました。●「先輩いきなりですね。確率DPっぽい問題です。M種類のガチャがあり、各ガチャには1回引くための金額と、出現アイドルの種類と、各出現アイドル...記事を読む怠惰でもできる精進こんばんは、ふるやん(@furuya1223)です。Selection解説)こんにちは、ふるやん(@furuya1223)です。■「ちょっと見かけた問題を考えてるんだけど解けなくて。その問題なら、ちゃんと考察して解きましたよ!...記事を読むABC133の初見実況動画を投稿しましたこんばんは、ふるやん(@furuya1223)です。コメントをキャンセルメールアドレスが公開されることはありません。*サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。クリエイティヴなブログ.当サイトでは利便性向上や閲覧の追跡のためにGoogle・他連携サービスによるCookieが使用されています。サイトの閲覧を続けた場合Cookieの使用に同意したことになります。information.。