AtCoder Regular Contest 176 （Sponsored by Mynavi）A,B,D,E問題メモ

AtCoder Regular Contest 176 （Sponsored by Mynavi）

もちろんACすることも大事だが、実装量を削減できる考え方・発想ができるかで違いが生じる。。。それがARC。。。

A - 01 Matrix Again

• $N \times N$ 盤面の各マスに、“0” か “1” を書き込む
• 整数 $M$ が与えられる
• 以下の条件を全て満たすように “1” を書き込むマスを決定せよ
  • 指定された $M$ 個のマス $(A_i,B_i)$ には “1” を書き込む
  • 全ての行について、書き込まれた数の総和は $M$
  • 全ての列について、書き込まれた数の総和は $M$
• $1 \le N \le 10^5$
• $1 \le M \le 10$

1個目の指定マスの条件がなければ、幅 $M$ の“11…1”をずらしていけばよい。

(例) N=6 M=4

1 1 1 1 0 0
0 1 1 1 1 0
0 0 1 1 1 1
1 0 0 1 1 1
1 1 0 0 1 1
1 1 1 0 0 1

指定マスのことを考慮すると、“1”の配置はこの考え方のまま、行・列を並べ替えることで条件を満たすようにしたい。

i\j 2 4 5 1 3 6
3   s s 1 1 0 0    s:指定マス (3,2)(3,4)(4,5)(6,5)
4   0 1 s 1 1 0
6   0 0 s 1 1 1    並べ替え方を指定する配列
1   1 0 0 1 1 1      行: P = (3,4,6,1,2,5)
2   1 1 0 0 1 1      列: Q = (2,4,5,1,3,6)
5   1 1 1 0 0 1

指定マス $M$ 個を、「上 $M$ 行、左 $M$ 列を取り出した行列の、右上の三角形◥」の中に入れられればよい。
そうなるように、列と行の並べ替え方 $P_i,Q_i$ を決定したい。

列ごとに、指定マスの個数 $C_i$ をカウントする。
指定マスが1個以上存在する列とその個数を $(B_1,C_1),(B_2,C_2),...$ とすると、

• 列の左から $C_1$ 番目 $Q_{C1}$を $B_1$ に
• 列の左から $C_1+C_2$ 番目 $Q_{C1+C2}$ を $B_2$ に
• 列の左から $C_1+C_2+C_3$ 番目 $Q_{C1+C2+C3}$ を $B_3$ に

していけばよい。$P$ も、$B_1,B_2,...$ で指定されているものを優先的に上に持ってくると、右上三角形に収まる。

Python3

公式Editorialにある、もっと楽な方法。

indexを 0-indexed に変換しておく。

前の解法の “111…1” をナナメにずらしていく考え方だが、これは別に繋がっていなくてもよい。

要は、$i+j \mod{N}$ が同じ $N$ 個のマス同士を1グループとして、$M$ グループを選び、それを全部 “1” にしたらよい。

i\j 0 1 2 3 4 5
0   a b c d e f
1   b c d e f a    同じグループは同じ文字
2   c d e f a b
3   d e f a b c
4   e f a b c d
5   f a b c d e

なので、指定マスの属するグループは必ず選び、重複があって $M$ グループに満たなければ適当に追加すればよい。

B - Simple Math 4

• 正整数 $N,M,K$ が与えられる
• $2^N$ を $2^M-2^K$ で割ったあまりの1の位を求めよ
• 1つの入力につき $T$ ケース与えられる
• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 10^{18}$
• $1 \le K \lt M \le 10^{18}$

試しに筆算で2進数の割り算をしてみる。

N,M,K=15,6,2

割る数: 2^M-2^K = 1000000 - 100 = 111100

       _____________1_0_0_0_1_0_0_0_1_0_ ←商
111100 )1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
          1 1 1 1 0 0
                1 0 0 0 0 0 0
                  1 1 1 1 0 0
                        1 0 0 0 0 0 0
                          1 1 1 1 0 0
                                1 0 0 0  ←あまり

割る数は、2進数表記では「111…100..0」のように、$M-K$ 個の1が続いた後、$K$ 個の0が続く形となる。

それで $2^N$ を割ると、商には $M-K$ ごとに“1”が立ち、あまりは2冪になる。

あまりは、「$N \equiv p \mod{M-K}$ となる $p$ の中で、$M$ 未満で最も大きな数」を $p_a$ として、$2^{pa}$ となる。

2冪の1の位は 2→4→8→6→2→4→… を繰り返すので、$p_a$ から答えが分かる。

$N \lt M$ の時、答えは $2^N$ の1の位。

$N \ge M, M-1=K$ の時、割る数も2冪になるので割り切れる。答えは0。

Python3

D - Swap Permutation

• $1～N$ の順列 $P=(P_1,...,P_N)$ と、正整数 $M$ が与えられる
• ある順列 $Q$ に対し、隣り合う2要素の差分の和 $\displaystyle \sum_{i=1}^{N-1} |Q_i-Q_{i+1}|$ を、$f(Q)$ とする
• $P$ に対し「相異なる2箇所を好きに選んでSwapする」という操作を $M$ 回繰り返すことを考える
  • このような操作列は、$(N(N-1)/2)^M$ 通りある
• 全ての操作列に対し、その結果として得られる順列を $R$ として $f(R)$ を求め、その総和を $\mod{998244353}$ で求めよ
• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$

主客転倒を利用して、2数が隣り合う箇所ごとに寄与を考える。

i  1 2 3 4 5
P  3 1 4 2 5
     ^ ^        M回の操作後、この2箇所に来る数字の組は？ × そのようになるパターン数は？

「全ての箇所 $(i,i+1)$ について」「全ての数字の組 $a,b$ について」
「$(i,i+1)$ に来る数字が最終的に $(a,b)$ になるような操作列の個数 $\times |a-b|$」を合計すると答えとなる。

もちろん愚直にはできないが、操作列の個数を数えるにあたり、 「$(i,i+1)$ に来る数字が元々あった数字と変わる/変わらないような操作列」のように分類すると、 $i$ の位置や変わる数字に依らず個数は全て同一となるので、まとめて考えられる。

• 上例で $(i,i+1)=(2,3)$ の箇所を考える場合、$i=2$ の位置に最終的に来る数字を考えると、
  • a) 初期状態の 1 のまま
  • b) 相方の数字 4 が来ている
  • c) 全く別の数字が来ている

の3通りに分けられる。

相方の位置についても同様に考えると、2数の位置に来る数字がどうなっているかは $3 \times 3 = 9$ パターン（あり得ない場合を除くと7パターン）を考慮すればよいことになる。

         i=3の位置
i=2     a)4  b)1  c)他    "-"の位置は、同じ数字を2箇所に置くことになり
の a) 1  ①   -    ②    あり得ないので考慮しなくてよい
位 b) 4  -    ③   ④
置 c)他  ⑤   ⑥   ⑦

「1回のSwapで、各状態 $i=①～⑦$ から各状態 $j=①～⑦$ に遷移するようなSwap対象の選び方の個数」を $7 \times 7$ 行列で作り $A[i,j]$ とすると、$A^M[①,k]$ が、$M$ 回のSwapで状態 $k$ になっている操作列の個数となる。

$7 \times 7$ でやってもいいのだが、いくつかの状態は遷移が同じになるのでまとめてしまえる。
実は、かなり大胆にまとめることができて、3パターンにまで落とし込める。

• A) ①両方とも初期状態のまま + ③単に入れ替わっただけ
• B) ②⑤一方のみが初期状態のまま + ④⑥一方のみに相方の数字が来ている
• C) ⑦両方とも初期状態とも相方とも異なる

要は、$P_i,P_{i+1}$ の最終的な位置をそれぞれ $j_1,j_2$ としたとき、 $\{i,i+1\}$ と $\{j_1,j_2\}$ を集合として考えて、一致する個数 $\{2,1,0\}$ で場合分けすればよい。

したがって、遷移行列 $A$ は $3 \times 3$ の大きさでよい。 （まぁ、$7 \times 7$ のままでも間に合うので、ここまで詰めるかはお好みで）

$A^M$ を繰り返し二乗法で計算して $M$ 回後に A)～C) になる操作列数 $C_A,C_B,C_C$ が計算できたとする。

位置 $(i,i+1)$ について、

A) は単純に

• $|P_i-P_{i+1}| \times C_A$

B) は、まず $P_i$ と $P_{i+1}$ のどちらが残っているかで同数ずつある。
$P_i$ が残っているとしたときに、隣り合っているもう片方に置かれている数字は 「$P_i$ 以外かつ $P_{i+1}$ 以外」の $N-2$ 通りであり、それぞれ同数だけ操作列が存在する。
$\displaystyle g(i)=\sum_{k=1}^N |i-k|$ とすると、$g(P_i)-|P_i-P_{i+1}|$ が $N-2$ 個との差分の合計となる。

• ($g(P_i)-|P_i-P_{i+1}|) \times \dfrac{C_B}{2(N-2)}$
• ($g(P_{i+1})-|P_i-P_{i+1}|) \times \dfrac{C_B}{2(N-2)}$

C) も、「$P_i$ でも $P_{i+1}$ でもない2数ペア（$(N-2)(N-3)$ 個ある）の差分の合計」は、 $h(i)=\sum_i{g(i)} - 2(g(P_i) + g(P_{i+1}) - |P_i-P_{i+1}|)$ で計算できるので、まとめられる。

• $h(i) \times \dfrac{C_C}{(N-2)(N-3)}$

これらを全ての箇所 $i$ について合計したものが、答えとなる。

上記の過程で、$N=2,3$ など小さい場合に、分母に0が出てきうるので、例外処理が必要な点に注意。

Python3

E - Max Vector

• 長さ $N$ の2つの数列 $X=(X_1,...,X_N)$ と $Y=(Y_1,...,Y_N)$ がある
• また、長さ $N$ の $M$ 個の数列 $A_i=(A_{i,1},...,A_{i,N})$ がある
• $i=1,2,...,M$ ごとに、以下のいずれか一方を選んで操作をおこなう
  • $j=1,...,N$ について、$X_j←\max(X_j,A_{i,j})$ で更新する
  • $j=1,...,N$ について、$Y_j←\max(Y_j,A_{i,j})$ で更新する
• 上手く操作を行うことで、操作後の $\displaystyle \sum_{j=1}^N X_j+Y_j$ を最小化し、その最小値を求めよ
• $1 \le N \le 10$
• $1 \le M \le 500$
• $1 \le X_i,Y_i,A_{i,j} \le 500$

線形計画問題として条件を与えてPythonなどの言語に入っているソルバに解かせると解けちゃうらしい。

競プロ的な想定解は、燃やす埋めるの高度なやつ。燃やす埋めるより「最小カット問題」として捉えた方がいいかも。

         ○○以上   1   2   3  ... 500
   ,- X1 について  ○→○→○→...→○-,
   |- X2 について  ○→○→○→...→○-|
   |   :                    :          |
   |- XN について  ○→○→○→...→○-|
S -|                                   |-→ T
   |     ○○未満 500 499 498  ...   1 |
   |- Y1 について  ○→○→○→...→○-|
   |- Y2 について  ○→○→○→...→○-|
   |                        :          |
   `- YN について  ○→○→○→...→○-'

こういう風な、$X,Y$ の値が何以上・何未満になるかを表す頂点を用意する。
制約上、$X,Y$ の値の最大値は500なので、その分だけ用意する。
後で辺を張る都合上、意味合いは $X$ と $Y$ で逆転させておく。

• グループSに属するとき「$X_i$ が $j$ 以上になる」ことを示す頂点を、$U_{i,j}$ とする
• グループSに属するとき「$Y_i$ が $j$ 未満になる」ことを示す頂点を、$V_{i,j}$ とする

$X_i$ についてのカットが $S→U_{i,1}→U_{i,2}→...→U_{i,500}→T$ のどこか1箇所のみで発生するようにしたい。
また例えば $U_{i,3}→U_{i,4}$ でカットされた場合にコストが 3 発生するようにしたい。

それには以下のように辺を設定する。

• $X_i$ について
  • $U_{i,j}→U_{i,j+1}$ に、コスト $j$ の辺
    • $U_{i,500}→T$ にはコスト $500$ の辺
  • $U_{i,j}←U_{i,j+1}$ に、コスト $\infty$ の辺（戻るの禁止）
  • $S→U_{i,Xi}$ に、コスト $\infty$ の辺（初期値未満になるの禁止）
• $Y_i$ について
  • $V_{i,j+1}→V_{i,j}$ に、コスト $j$ の辺
    • $S→V_{i,500}$ にはコスト $500$ の辺
  • $V_{i,j+1}←V_{i,j}$ に、コスト $\infty$ の辺（戻るの禁止）
  • $V_{i,Yi}→T$ に、コスト $\infty$ の辺（初期値未満になるの禁止）

ここに $M$ 個の頂点を追加し、$A_i$ による更新の制約を追加する。ここで燃やす埋めるっぽさが出る。

• グループSに属するとき「$A_i$ の更新は $X$ の方に適用する」ことを示す頂点を $W_{i}$ とする
  • Tに属するときは $Y$ の方に適用することを示す

$A_{i,j}=a$ とすると、

• $A_i$ を $X$ に適用する（＝$W_i$ をグループSに属させる）場合、
  • $X_j$ が $a$ 未満であってはならない（＝$U_{j,a}$ がTに属してはならない）
  • $W_i→U_{j,a}$ に $\infty$ の辺を張る
• $A_i$ を $Y$ に適用する（＝$W_i$ をグループTに属させる）場合、
  • $Y_j$ が $a$ 未満であってはならない（＝$V_{j,a}$ がSに属してはならない）
  • $V_{j,a}→W_i$ に $\infty$ の辺を張る

というのを、各 $i,j$ に対しておこなっていく。

A[1,1] = 3 の場合

         ○○以上   1   2   3  ... 498 499 500
   ,- X1 について  ○→○→○→...→○→○→○-,
   |                   ∞↗                    |
S -|                  (W1)                     |-→ T
   |                     ↖_∞____             |
   |     ○○未満 500 499 498  ...＼ 3   2   1 |
   `- Y1 について  ○→○→○→...→○→○→○-'

これで最小カットを流すと、各 $X_i,Y_i$ についてちょうどよい箇所でカットされ、答えが求まる。

Python3