AtCoder Beginner Contest 117 C,D問題メモ

AtCoder Beginner Contest 117

• AtCoder Beginner Contest 117 解説放送 - YouTube

C - Streamline

• 数直線上のマスと、$N$ 個のコマでゲームを行う
  • まず、好きなマスにコマを配置する
  • いずれかのコマを、隣り合う左右いずれかのマスに動かす操作を1回とする
• $M$ 個のマス（座標 $X_1,X_2,...,X_M$）の全てに、いずれかのコマを訪れさせたい
• 最低何回の操作が必要か

行ったり来たりは無駄なので、1つのコマはずっと同じ方向に進ませることになる。 それぞれのコマに「訪れるべき担当マス」を割り当てると、自分の担当の中で一番左から出発して、一番右まで行くのがいい。

担当区間が被るのは無駄なので、$M$ 個のマスを連続した区間の $N$ グループに分ける形になる。 一番操作回数が少なくなる分け方を見つければよい。

入力例2
座標   -100     -10 | -3  0 | 2   9     17
         o------->  |  o -> | o--------->     分け方の例
操作回数     90          3        15

ここで、訪れるべき $M$ 個のマス間の距離に着目する。

座標   -100     -10   -3  0   2   9     17
マス間距離   90     7   3   2   7    8

ある分け方における操作回数は、その区間のマス間距離の和になる。

座標   -100     -10 | -3  0 | 2   9     17
         o------->  |  o -> | o--------->
             90     |   3   |   7     8     →  90+3+7+8=108

逆に言うと、グループの境界線のマス間は操作しなくてよい。

座標   -100     -10 | -3  0 | 2   9     17
         o------->  |  o -> | o--------->
             90    (7)   3 (2)  7     8
                    ↑      ↑
             この間は移動させなくてよい

境界線は $N-1$ 個あるので、ここに長距離のマス間をもってくるような分け方が、操作回数が最も少なくなる。

座標   -100  |  -10   -3  0   2   9  |   17
         o   |    o--------------->  |    o
                    7   3   2   7             → 7+3+2+7=19

D - XXOR

• $N$ 個の非負整数 $A_1,A_2,...,A_N$ と、非負整数 $K$
• ある非負整数 $k$ について、$f(k)=(k \oplus A_1)+(k \oplus A_2)+...+(k \oplus A_3)$ とする
  • ここで、$\oplus$ はXOR(ビット排他的論理和)
• $0 \le k \le K$ について、$f(k)$ の最大値を求めよ
• $1 \le N \le 10^5$
• $0 \le A_i,K \le 10^{12}$

XOR問題なので、2進数にして、桁ごとに独立に考えられないか試みる。

以下「桁」は2進数での桁を、上から数えた数で表す。$10^{12} \lt 2^{40}$ のため、桁の最大は40くらいまで考えればよい。

$f(k)$ を求める際、具体的な個々のXORの結果を求めずとも、桁ごとに考えて足し合わせてよい。

       2進数   k=3(0011)のときXOR  XORを10進数で表すと
A1  1   0001       0010                       2 ┐
A2  6   0110       0101                       5 ┼14  ←┐
A3  4   0100       0111                       7 ┘      │
                    |||                                 │
                    ||`-> 1の位、'1'が2個: 1 x 2 = 2  一致する
                    |`--> 2の位、'1'が2個: 2 x 2 = 4    │
                    `---> 4の位、'1'が2個: 4 x 2 = 8    │
                                           ---------    │
                                                  14  ←┘

$d$ 桁目（$=2^{40-d}$ の位）で足し合わせる数は、$2^{40-d} \times (k \oplus A_i$ のうち $d$ 桁目に'1'が立っている個数$)$ なので、最大化するにはなるべく'1'を多くしたい。

よって、$k$ の $d$ 桁目は以下のようにするとよい。

• $A_i$ の $d$ 桁目は'1'の数字が多い…$k$ の$d$桁目は'0'がよい
• $A_i$ の $d$ 桁目は'0'の数字が多い…$k$ の$d$桁目は'1'がよい

       2進数
A1  1   0001
A2  6   0110
A3  4   0100
        |||`-> 0が多い→1
        ||`--> 0が多い→1
        |`---> 1が多い→0
        `----> 0が多い→1  → k=1011 が最適（簡単のため4桁でやったが、実際は40桁）

しかし、これでは最適な $k$ が $K$ を超えてしまうかも知れない。

どこか1箇所、$K$ が'1'である桁について $k$ を'0'にすることで、それ以下の桁についてはどう選んでも $K$ を超えることは無くなる。

桁         12345678
       K = 01010100
最適な k = 01111011

Kを超えない最適候補: たとえば4桁目について K=1 のところ k=0 とする
       k = 01001011
           010      4桁目まではKと一致させる
              0     4桁目は'0'とする
               1011 4桁目以降は最適に取れる

$K$ が'1'となっている桁を全探索することで、答えが得られる。

それには、各桁について、以下の値を求めておけばよい。

• best[i]: ($K$の制約を無視して)最適に取った場合の $i$ 桁目で足される数
• thr[i]: $k=K$ の時に、$i$ 桁目で足される数
• base[i]: $k=0$ の時に、$i$ 桁目で足される数

すると、$i$ 桁目を0に変えた場合の$f(k)$は、$(thr[0]～thr[i-1]までの和)+base[i]+(best[i+1]以降の和)$ で求められる。

ただし、この方法では $k=K$ の場合は探索されない。候補としてはあり得るため、別途計算しておく（thrの合計がそれとなる）

桁を上から見ていく必要がある処理は、ビット演算でもよいが、制限時間がよほど厳しくなければわかりやすく文字列にしてしまってもよい。（printとかでそのまま確認しやすい）

pythonでは、ゼロ埋めした2進数が欲しい場合は、以下のいずれかの方法を使うとよい。

{:040b} は、「右詰で、足りない桁は0で補って、40桁に揃えて、binary(2進数)で文字列化」する。

• 書式指定文字列

binは2進数の文字列表現を得るが、先頭に2進数を示す'0b'が付くため、[2:]で省く。 そこにzfill関数を使うと、右詰で指定の桁でゼロ埋めしてくれる。

貪欲でも通ってしまったらしい？

• 上の桁から見て、$k$ の $d$ 桁目が'0','1'どちらがよいか調べる
• 基本的によい方を採用する
• '1'の方がよいが、今まで選んできた上位桁から、'1'を選ぶと$K$ を超えてしまう場合は、'0'にする

貪欲ではこんなケースでおかしくなる。

              貪欲        正解
 K  10000     k  10000    k  01111
---------     
A1  10000        00000       11111
A2  10000        00000       11111
A3  00000        10000       01111
A4  00000        10000       01111
A5  00000        10000       01111
             答: 48      答: 107

一番上の桁だけ見ると、確かに'1'の方がよいのだが、それ以降の桁で'0'しか選べなくなってしまうというデメリットが大きい。