feature image

2017年12月9日 | ブログ記事

Code Thanks Festival 2017 F Limited Xor Subset 解説

この記事は解説 Advent Calendar 2017の9日目の記事です。traP Advent Calendar 2017ではありません。(ここnariさんのパクリ)

こんにちは、xxkiritoxxです。先週はCode Thanks Festivalでしたね。略すとCTFで非常に紛らわしいです。私自身はコードフェスティバル(Thanksじゃない方)に出てたので本戦出場権は無かったんですが、暇だったので家でParallel参加していました。F問題が500点にしてはかなりの重考察を要求される問題だなあと思いながら通したのですが、完全に私の誤読が原因でした。そういう訳で想定解ではない解法が生えたので紹介させてもらおうと思います。

問題

個の正の整数が与えられ、番目の正の整数はです。
個の整数のうち個以上を選んで、選んだ全ての整数のビットごとの排他的論理和を計算します。
計算結果がとなるような整数の選び方の個数をで割った余りを求めてください。
ただし、個選んだときのビットごとの排他的論理和はとします。

制約

入力は全て整数




?こいつを誤読して

と勘違いしました。

解法

以下、の排他的論理和をと表記します。

本問題において、集合と集合は「本質的に同じ」です。「本質的に同じ」というのはどういうことかと言いますと、任意のに対し、この2つは「を作れる組み合わせは何通り」「を作れる組は何通り」・・・「を作れる組は何通り」というのがの範囲で全て一致するという意味です。つまり集合の中身は変わったけど本問題においてはどんなが来ても答えは変わらないから同じようなもん・・・みたいな気持ちです。

証明をします。を作るの選び方の個数のうち、も使わないで作れるパターンについては明らかに一致しますね。を使わないでのみ使うパターンも同様に一致します。そして、のみ使っては使わないパターンというのは、の両方を使うパターンと一致します。両方を使うパターンはを使ってを使わないパターンと一致します。極めて雑ですが証明完了です。

この性質を使うことで面白い解き方が出来ます。
解法のアウトラインは、
1.ある操作を繰り返して、最初の集合と「本質的に同じ」だけどほとんど全て0で、「もし0以外の要素のみ使ってある数字を作れるならば作り方は一意」という状態を作る
2.その「ある数字」(今回は)が作れるのかを審査
3.作れないなら答えは、作れるなら答えはの(の要素数)乗
という感じです。
口頭での説明は厳しいので、「入力例3」を解くプロセスを見せながら説明しましょう。

入力例3ではです。要素数が13個もあるから縦に長くて見づらいですがご了承ください。

説明の都合で途中から2進数にしました。等号で繋がってるのおかしいですね。ごめんなさい。
さて、こいつを「本質的に同じ」な別の集合に作り変えましょう。まずから順に調べていって、先頭ビットが立っているものを探します。今回はが見つかりました。
そこで、以外で先頭ビットが立っているものは全てとのXORを取りましょう。既に示した性質より、この操作によって生まれる集合は最初の集合と「本質的に同じ」になります。

次も同じようなことをします。まずから順に前から2番目のビットが立っているものを探します。が見つかりました。以降、2番目のビットが立っているものは全てとのXORを取ります。
この処理をする上での注意なんですが、「前から2ビット目が立ってるもの」なら何を取ってきてもいいわけじゃないです。「前から2ビット目が立っていて、なおかつ先頭ビットが立っていないもの」を取ってきてください。
そうすると、集合はこのように変化します。

前から3ビット目も同様に操作します。「前から3ビット目が立っているもので前から2ビット目以降が立っていないもの」には最初にがヒットします。
ただし、実装の際に面倒なので、前から3ビット目は立っているけど2ビット目も立っているとのXORを取らないことにします。

いい感じに0の要素が増えてきました。この集合でも最初の集合と「本質的に同じ」という性質は残っています。最後に最終ビットについても操作しちゃいましょう。条件を満たすもので最初にヒットするのはです。

さて、こうした操作によって9つの0と4つの非零の値が出来ました。この集合は最初の集合と「本質的に同じ」です。目的の数を作るにあたり、0のものは使っても使わなくてもどっちでもいいのは明らかですが、非零の要素については必ず使うか必ず使わないかの2択になります。厳密に示したければ帰納法を使えばいいのでしょうが、雑に理由を説明すると「より2進数での桁数が大きいものについて使うか使わないかが全て決まっているとき、と同じ桁の値はを使うか使わないかのみに依存するから」という感じです。

今までの考察により、本問の答えは「最後に残った非零の要素を使ってを作れなければ答えは、作れたら答えは」です。これを確かめるには先頭ビットから順に使うか使わないか決めていって、最終的に作ることが出来るかを検証するだけです。この手順は操作を全て終えた後に行おうとすると意外と大変なので、上の操作を行いながら平行して検証出来るように実装するとよいでしょう。実装例は下に私のコードを貼っておきますので、そちらを参照してください。

さて、計算量を概算しましょう。一回の操作にかかり、操作の回数はもしくはの2進数での桁数ぐらいです。しかし、この操作は回やってもうまくいきません。例えばのときはどうでしょう。一番後ろのビットだけに注目するとうまくを処理出来ません。失敗です。いっぽうやれば確実にうまくいきます。
よって、この解法の全体での計算量はとなります。かなり高速になりますし、最初の条件を誤読したままでもこの計算量なら通ることが分かります。

実際の提出

https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1822899
これはコンテスト中に書いたものです。焦っていたので途中で不要なソートをしていて、そのためというかなり変なオーダーになっています。ソートはソートでもqsortなのが味わい深いですね。
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1834702
数日後に書き直しました。かなり高速になっています。
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1835196
時間計算量が落とせそうになかったんで空間計算量を落としてみたところ実行時間も若干改善しました。2017/12/08現在では実行時間、使用メモリ共に最小のようです。計算の順序を†ちょっと†工夫することで空間計算量はにまで落ちます。

まとめ

制約はちゃんと使おう!

余談

ところで、この操作完全にガウスの消去法なんですよ。線形代数の知見が生きたので面白い問題だなあと思うと同時に(これ本当に500点か・・・?)と思っていたのですが、解説読んだら遥かに簡単な解法があってブチ切れてしまいました。

xxkiritoxx icon
この記事を書いた人
xxkiritoxx

SAOを見たことはありません

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2021年4月17日
競プロと CTFの 体験会(CPCTF) を開催します!
Hmcmch icon Hmcmch
記事一覧 タグ一覧 Google アナリティクスについて