Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました＆お疲れ様でした。
難易度が高すぎて順位表が大変なことになっていましたね。。
１問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。
でも、なんだかんだ出来ることはあって座るだけにはならなかった方が多く、その点は良かったかなぁと思っています。
それでは解説を...のつもりだったのですが、解説をガッツリ書く体力が残っていないため、ヒントだけで失礼いたします。
ヒント
N=15のとき、8,4,2,1と取っていくと4回ですが、a=[0,8),b=[7,15),c=[7,8)とすると３回の質問で総和（a+b-c）が求められる。
このように引き算を駆使すると、二進数での桁数/2回くらいの質問で総和が求められる。
ちなみに10回必要になる最小のNは二進数で11010101010101011です。
50点を超える最も簡単な解法は、スターンブロッコット木を、分母をx分子をyとしてそのまま埋め込む解法だと思います。
70~90点はフラクタルっぽい図形を頑張って構成すれば良いです。
満点は64*64に収めなければなりません。余白は1点しか許されません。
これは図を使って説明しないと行けないので後で。
二分探索すると01列を切ったり捨てたりして1を残したら勝ちというゲームになります。
0,1のかわりに-1,1で考えます。
累積和をとります。
全体の累積和が0でない場合、正なら勝ち、負なら負けです。
0の場合は、累積和が0となっているような切れ目の個数が奇数個なら勝ちです。（先に切る番の場合）
戦略は上記の結果を証明しようとすると自然と導かれます。
簡単枠のはずでした（自明ではないですが）が昼の部ではなかなか解かれませんでした。
各サイクルに注目すると、
サイズが2なら1回でいい。
サイズが3以上なら2回必要になる。
サイクルに出てくる数たちを列としてみると、全体をreverseするのと1狭い区間をreverseするのをやると1shiftが作れます。
例えば234561→[165432]→1[23456]という感じです。reverseは複数のswapを並列に行うだけで実現できますね。
まずはクラスタリングしましょう。
クラスタリングは超高精度でできます。
各人に対して、その人と同じ選択肢が選ばれている回数を求めて、その順でソートして10,10,10と区切ってやればいいです。
あとは各問題について最尤値推定をすればいいです。（2/3の人で多数決をするだけでも通ります）
見掛け倒しです。
実は操作は対称性が高く、K次回文はreverseしてもK次回文になります。
mod2で答えればいいので、もともと回文であるようなK次回文の個数さえ求めれば良いことになります。
K=0のときは回文の個数を求めればいいです。
K>=2のときは追加、置換*K-2、削除とすればもとの文字列に戻すことが出来るので、これも回文の個数を求めればいいだけです。
K=1のときは「もとが回文」かつ「1長いものまたは1短いものも回文」でなければならず、どの文字とどの文字が同じでなければならないかを考えると、すべての文字が同じ文字列しか条件を満たさないということがわかります。
最大流に落としましょう。
そのグラフは平面グラフになっているので、最小カットを最短路で求めることができます。
有向グラフの場合は逆辺としてコスト0の辺を張らないといけない点に注意。
二分探索した後、結構シンプルな貪欲法で解けます。証明が面白いです。
証明は後で。
いろんな塗り分け方をして偶奇性を見ると各テトロミノ特有の性質というのが検出できます。
後で。
条件を満たすように数列を作ってくださいとしか解説のしようがあまりない気がする。
(1)はなんと、全部満たせます！
(2)は後のことをあまり考えずに貪欲に置ける数の中で最も大きいものを置いていくだけでいいです。変態的なパズルです。
open all / close all
generated by indenter
