AtCoder Beginner Contest 147 C～F問題メモ

AtCoder Beginner Contest 147

C - HonestOrUnkind2

• $N$ 人の人がいて、各人は「正直者」と「不親切な人」のどちらかである
• 「正直者」は必ず本当のことをいう
• 「不親切な人」は本当を言ったり嘘を言ったりする
• 人には $1～N$ までの番号が付いていて、$i$ 番目の人は $A_i$ 個の証言をしている
  • $i$ 番目の人の $j$ 番目の証言は、$x_{ij},y_{ij}$ によって表される
  • これは「$x_{ij}$ 番目の人は、$y_{ij}$（1=正直、0=不親切）である」を意味する
• 正直者の人数としてあり得る最大値を求めよ
• $1 \le N \le 15$

制約が小さいので、全探索が可能。

……けど、実装がやや面倒なので「C問題でそんなん出るか？もっと簡単な方法があるのでは？」と無駄な読みをしてしまう。結果的には全探索が想定解法。

判定は、最大 $N$ 人が $N-1$ 個の証言をしている1つ1つを正しいか確認していくので、1回の判定に $N^2$ かかる。 列挙と合わせて $O(2^N N^2)$ となり、だいたい $7.3\times 10^6$ くらいになる。まぁ間に合いそう。

判定は、正直者の証言のみを確認すればよい。 正直者として立っているbitのみを順に取り出すには、以下のようにする。

グラフ探索のように、「1番目の人を正直者と仮定したら、正直者と確定する人は誰々で、不親切と確定する人は誰々で……」を 連鎖的に確定させていっても解けそうに思う（そしてその方が期待計算量は抑えられる）が、 証言のつながりが連結でない場合など、どちらとも確定しない人が出てきてしまう。 そしたらその内の1人をまた仮定して……と再帰的にやる必要がありややこしいので、全探索で間に合いそうならその方が流れを整理しやすい。

D - Xor Sum 4

• 数列 $A_1,A_2,...,A_N$ が与えられる
• 全てのペアのXORの総和を $\mod{10^9+7}$ で求めよ
• つまり、$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}(A_i XOR A_j)$ を求めよ
• $2 \le N \le 3 \times 10^5$
• $0 \le A_i \le 2^{60}$

bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では他の桁が影響することはないので、桁毎に独立に考えて問題ない。

N = 5
A = {   1   2   3   4   5 }
               ↓
    { 001 010 011 100 101 }

たとえば2桁目を取り出すと
       0   1   1   0   0

各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 0はいくら足しても0なので、(0,1)の数だけわかれば良い。

それは、(0の個数)×(1の個数)で計算できる。

    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12

これを各桁について足し合わせる。

E - Balanced Path

• $H \times W$ のグリッドの各マスに、2つの正整数 $A_{ij},B_{ij}$ が書き込まれている
• 各マスの数字を、一方は赤、一方は青で塗り分ける
• 左上座標 $(1,1)$ から右下座標 $(H,W)$ まで、縦横に隣接するマスを移動して最短で移動する
• 経路上のマス（出発・到着マス含む）の「赤だけを拾った合計と、青だけを拾った合計の差の絶対値」を $S$ とする
• 赤青の塗り分け方、また経路を適切に選んで、$S$ を最小化せよ
• $1 \le H,W \le 80$
• $0 \le A_{ij},B_{ij} \le 80$

制約が微妙に小さいのが気になる。

Dijkstraなどのアルゴリズムは、そのマスまでの「最短距離」さえわかればよいのでそれだけを情報として残しておけばよいが、 この問題の場合、途中までの差の絶対値を小さくしていても、 後半で大きな差を持つ $A_{ij},B_{ij}$ を通過するなら途中までは大きな差のまま残しておけばよかった、ということがあり得る。 （部分問題の最適値＋部分問題の最適値＝全体の最適値、とならない）

結局、途中までの段階でどういう塗り分けをしておくのが最適かは、以降の $A_{ij},B_{ij}$ 次第であり、それは読めないので、全パターンを記録するほかない。 そう考えると、制約が小さいのも、その解法を裏付けていそう。

ただし通過した $A_{ij},B_{ij}$ を全て残しておく必要は無く、「このマスに到達するまでに作ることが可能な差の絶対値」の候補集合を持っておけばよい。

$DP[i][j]=$ マス $(i,j)$ に到達（そのマスの数字も反映済）した時に作ることが可能な差の絶対値の集合

マス $(i,j)$ へは、$(i,j-1)$ または $(i-1,j)$ から到達できる。 $(i,j)$ に書かれた2数の差がたとえば9だったとすると、$DP[i][j-1]$ と $DP[i-1][j]$ の和集合に ±9を施したものが新たな集合となる。

{x,y,z}... そのマスまでに作ることが可能な差の絶対値集合
[a, b] ... そのマスに書かれた数字2つがa, b

         {3, 5, 6}
            ↓
{1, 4}→ [ 45  36 ]  =>  {3-9, 3+9, 5-9, 5+9, 6-9, 6+9,
                          1-9, 1+9, 4-9, 4+9}
                     =>  {6, 12, 4, 14, 3, 15, 8, 10, 5, 13}

集合は、set()で持つと遷移に要素数分の計算量がかかることになり、TLE濃厚となる。

多倍長整数を扱えるPythonなら整数をそのままbit列として扱えるので、bit演算とshiftで遷移できる。

その際、要素の取り得る値の範囲が重要だが、制約を見ると、通過するマス数が約 $H+W=160$、各マスで取り得る差が±80まで。 それぞれのマスで80が足したり引いたりされても、-12800～12800を超えることは無い。25600くらいのbit列なら、十分計算可能。

“全ての解答”を見てると、コンテスト終了直後、上記のコード全く同じものを使って別の人が通してるのを観測したんだけど、いいのかな。 終了後ならいいかと思いつつも、完全にOKとするとAtCoder Problemsの「解いた問題数ランキング」などが意味をなさなくなる危険性もあるわけで。

F - Sum Difference

• 初項 $X$ 公差 $D$ 長さ $N$ の等差数列がある
• 要素を2つのグループに分けて、それぞれの和を $S,T$ とする（一方が空集合でも可）
• $S-T$ が取り得る値の種類数を求めよ
• $−10^8 \le X,D \le 10^8$
• $1 \le N \le 2 \times 10^5$

まず、$S-T$ を求めると言いつつ、$S$ を固定すれば $T$ も決まり、$S-T$ も決まる。 また、異なる $S$ からは異なる $S-T$ が生まれるため、求めるのは $S$ が取り得る値の種類数でよい。

等差数列を変数で書くと、$X,X+D,X+2D,...,X+(N-1)D$ となる。

$S$ を変数で表したい。ここで、$S$ の算出元のグループの要素数を $k$ とし、$k$ で場合分けすれば表せそう。

$$S_{k,t}=kX+t_kD$$

ここで、$t_k$ は $N,k$ に依存する変数であり、取り得る値は「$0～N-1$ から相異なる $k$ 個を取ってきた合計」とする。 つまり、$N=5, k=2$ なら、0,1,2,3,4から2個取ってきた合計なので、0+3=3 や 2+4=6 などの値を取る。

とりあえず、$k$ が固定された状態で $t_k$ のみ動かす時の $S$ の種類数は？を考えてみる。 これは純粋に、$t_k$ の取り得る種類数がそのまま答えとなる。

$N=5$ 個の中から $k=2$ 個選ぶ際、0+3=3、1+2=3 などは同じ値となるため、これは除いて数えなければならない。

$t_k$ の取り得る最小値・最大値で挟みうつとよい。 例では、最小値は0+1=1、最大値は3+4=7であり、この間なら適当にずらしていけば全ての値を作ることが出来る。 よってこの場合の種類数は7個。

最小値は $0,1,2,...$ から $k$ 個取った場合の和、最大値は逆に $N-1,N-2,...$ から $k$ 個取った場合の和であり、簡単に事前計算できる。

考察しやすくするため、$X,D$ を最大公約数 $g$ で割ったものに置きかえて、互いに素にしておく。 こうしても、等差数列の要素やS,Tなどが全て $\frac{1}{g}$ 倍になるだけで、取り得る値の種類数は変わらない。

また、$D$ が負の場合、$X,D$ を同時に正負逆転させて正にしておく。これも取り得る値の種類数に影響はない。

答えを求めるには、$k$ ごとに個別に種類数を求めて足し合わせていくとよさそうだが、異なる $k$ 間でダブりが発生する可能性について考慮する必要がある。

基本的に異なる $k$ 同士では、$D$ で割った余りが異なる場合にはダブりは発生しない。 だが、周期 $D$ ごとに $D$ で割った余りが等しくなり、ダブる可能性が出てくる。

  k   * X   +   t(k)   * D    ≡  k   X  mod D        ┬ ダブり得る
(k+1) * X   +   t(k+1) * D    ≡ (k+1)X  mod D        │
...                                                   │
(k+D) * X   +   t(k+D) * D    ≡ (k+D)X ≡ kX  mod D  ┘

N=10, X=2, D=3
  0   * 2   +   t(0)   * 3   =>   { 0}
  1   * 2   +   t(1)   * 3   =>   { 2, 5, 8,11,...,26,29} ←
  2   * 2   +   t(2)   * 3   =>   { 7,10,13,16,...}
  3   * 2   +   t(3)   * 3   =>   {15,18,21,24,...}
  4   * 2   +   t(4)   * 3   =>   {26,29,32,35,...}       ←

$k$ と $k+D$ を比べていくらダブっているかを求めたい。

$t_k$ が取り得る最小値・最大値をそれぞれ $l_k,r_k$ として、これの重なり範囲をベースに考える。

• $N=10,k=1$ の時、$(l_k,r_k) = 0, 9$
• $N=10,k=4$ の時、$(l_k,r_k) = 6, 30$

ただしこのまま比較は出来ない。 $kX+t_kD$ の $kX$ の部分については $k=1$ と $k=4$ では $XD$ だけ差があるため、 実際の数字の重なりを調べるにはその分だけ範囲をずらす必要がある。

$k=4$ の時は、$X=2$ だけ大きな範囲を扱っていると考えてよい。

k=1                                    1 * 2  +  0～ 9 * 3
k=4  4 * 2  +  6～30 * 3  →2ずらす→  1 * 2  +  8～32 * 3
k=7  7 * 2  + 21～42 * 3  →4ずらす→  1 * 2  + 25～46 * 3
k=10 10* 2  + 45～45 * 3  →6ずらす→  1 * 2  + 51～51 * 3

このように、$\mod{D}$ が共通する $k$ ごとにグループ化して、範囲を揃えてやれば、 あとは始点・終点をソートして、少なくとも1つの範囲に含まれる区間の長さを求める問題に還元できる。

$D=0$ なら、ずっと同じ数字が並ぶだけなので、「何個取ったか」だけが重要になる。よって $N+1$ が答え。

ただしその中でも、$X=D=0$ なら、どう足掻いても双方0にしかならないので、$1$ が答え。