CodeChef September Challenge 2020 - Chefina and Swap

• 問題
• AC

0-basedで考える。列$(S_i)$を$[0, m), [m, N)$に分けた時に、左右の和を等しくするようなスワップが何個あるか数える。まず、右の和のほうが大きいことが有効なスワップが存在する必要条件である。右の和が左の和より$D(m)$だけ大きいとする。このとき、$D(m)$が偶数なら左の区間の$S_i$と右の区間の$S_{i+D(m)/2}$を交換すると和が等しくなる。添え字$i$が有効である条件は$0\le i < m, m \le i+ D(m)/2 < N$で、これは$\max(0, m-D(m)/2) \le i < \min(m, N-D(m)/2)$とまとまる。この区間の長さが有効なスワップの数に等しいので、すべての$m$について足せばよい。ただし$D(m)=0$の場合は区間をまたいで数を移動する必要がないので特別扱いして、左の区間内と右の区間内のスワップの総数を数える。

さて、$0\le D(m) < 2N$が必要なことを考えると、有効な$m$は多くないはずだ。$m$が増加するとき、$D(m)$が正から負に変わる地点を考えると、この地点は全体の半分よりは右にあるはずだから、その付近では$m$が$1$動くごとにおおむね$2 \cdot N/2 = N$程度は$D(m)$が変化することになる。したがって、高々3つ程度の$m$について数えれば十分という見積もりができる。実装の際は$D(m) \ge 0$であるような最大の$m$を二分探索などで求めておいて、そこから下っていけばよい。

CodeChef September Challenge 2020 - Find XOR

• 問題
• AC

仮に$K=0$を尋ねることが可能だとすると、$K=0$による総和と$K=2^e$による総和の差は$(A_i)$の中で第$e$ビットが$1$であるものの総数-第$e$ビットが$0$であるものの総数に等しい。これを利用すると各桁の立っているビットの数がわかるので、偶数ならXORを0、奇数なら1とすればよい。

実際には$K\ge1$という制約があるが、代わりに全ビットを反転したもの（=$2^{20}-1$とXORを取ったもの）を$K$とすれば同じことができる。

また、素朴にやると$K=0, 2^0, 2^1, ..., 2^{19}$を全部尋ねる必要があってクエリの回数が21回になってしまう。$K=2^0, ..., 2^{18}$を調べて$K=0$の場合の生の総和と比較することで、$K=2^{19}$は省略できて20回になる。

---

$N \le 10^3 < 2^{10}$だから、11ビットくらいで区切れば2つの質問を1つのクエリでできそうと思ったが、分離がかなり複雑になりそうなので方針を変えた。

CodeChef September Challenge 2020 - Rotate the Polyline

• 問題
• AC

$v_i=P_iP_{i+1}$とした時、原点を通る直線$l$によってできた2つの（境界を含まない）半平面のそれぞれに連続した添え字のベクトルが並んでいれば、$l$に直交するベクトルが答えということになる。ただし、答えとなるベクトルは十分に原点に近い格子点を通る必要がある。

整数性の条件をいったん忘れると、直線$l$を表すベクトルの候補$u$は各$v_i$から偏角を左右に微小にずらした$2N$通りが考えられる。そこで偏角順の尺取り法をして、それぞれの$u$から偏角が$180 \degree$以内におさまるすべての$v_i$の添え字を保持することにする。添え字がすべて連続している瞬間があれば$u$を$90 \degree$回転したものを答えにすればよい。管理と判定はBITでできる。以下、実装のポイント:

• 尺取り法で区間を伸ばす場合の処理: ベクトルの候補$u$と$v_i$のクロス積がマイナスになるまで伸ばしていけばよい。^[1]
• 尺取り法で区間を縮める場合の処理: $u$と$v_i$のクロス積がプラスになるまで縮めればよい。
• $u$と同一か180度回転した偏角が$(v_i)$に含まれる場合、$u$（を$90\degree$回転したもの）は答えにできない。

さて、$2N$本の直線を用意する上で、整数性の条件を考慮しなくてはならない。単純化のために正数に限定して考える。ベクトル$(x, y)$から反時計回りに微小に偏角を進めたベクトルを得ることは、$y/x < 1$であればファレイ数列$F_{2\cdot 10^9}$において$y/x$の直後にある分数を得ることと同じである。$y/x \ge 1$の場合も、逆数を取って直前の分数を得ると考えればよい。やり方を知らないのでググったらstackexchangeの質問が見つかった。ファレイ数列の隣接項$p/q, c/d$は$cq-dp=1$を満たすので、$c, d$は互除法で求まるようだ。

---

1. クロス積がマイナスになるベクトルが存在しなかった場合はこれだとうまく処理できないように見える。こういうことが起こるのは、偏角ソートされた$(v_i)$の隣接項同士が$180\degree$より開いている場合だが、問題設定より全ベクトルを足すと$0$に戻るのでこの範囲に1つもベクトルがないということはありえない。 ↩︎

CodeChef September Challenge 2020 - Divide Candies

• 問題
• AC

べき乗和は$K$の値に関わらず奇数と偶数を交互に足すので、総和は奇、奇、偶、偶、奇、奇、……となる。総和が奇/偶の時の自明な下限がそれぞれ1/0なので、これを達成できれば最善となる。実験してみると、$N$が十分に大きければ常に下限が達成できるという予想が立つ。

$K=1$の場合、長さ4の区間は$0110$とわければよくて、$N$が$4$の倍数ならこれに従って等分できる。倍数でない場合もそれぞれ4つずつ等分した後、残りを適当にわければよい。

$K=2$について。また実験すると、長さ8の区間は$01101001$で等分できることがわかるので、$N$が小さい場合の構成を列挙した上で、以降は$8$個ずつ等分すればよい。

$K=3, 4$の場合も常に等分できるような長さの区間が見つかれば解決しそうだ。

$K=3$の場合は長さ16の区間は$0110100110010110$で等分できる。（ここでようやく、ひとつ小さい次数で得た列をflipしてくっつければよいことに気づく。）やはり$N$が小さい場合を列挙して、以降は$16$個ずつ等分すればよい。$K=4$も同様で、長さ32の区間を$01101001100101101001011001101001$で等分できる。

さて、$N$が小さい場合の解を用意する必要があるのだが、明らかにIPソルバで解けるのでOR-ToolsのCP-SATを使った。$K=3$までは愚直でいいとして、$K=4$はDPや半分全列挙でも簡単ではないように見える。（ちゃんと考えていない）