AtCoder Regular Contest 176 (Sponsored by Mynavi)
もちろんACすることも大事だが、実装量を削減できる考え方・発想ができるかで違いが生じる。。。それがARC。。。
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),...$ とすると、
していけばよい。$P$ も、$B_1,B_2,...$ で指定されているものを優先的に上に持ってくると、右上三角形に収まる。
公式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$ グループに満たなければ適当に追加すればよい。
試しに筆算で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$ から答えが分かる。
主客転倒を利用して、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$ の位置や変わる数字に依らず個数は全て同一となるので、まとめて考えられる。
の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パターンにまで落とし込める。
要は、$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) は単純に
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$ 個との差分の合計となる。
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}|)$ で計算できるので、まとめられる。
これらを全ての箇所 $i$ について合計したものが、答えとなる。
上記の過程で、$N=2,3$ など小さい場合に、分母に0が出てきうるので、例外処理が必要な点に注意。
線形計画問題として条件を与えてPythonなどの言語に入っているソルバに解かせると解けちゃうらしい。
競プロ的な想定解は、燃やす埋めるの高度なやつ。燃やす埋めるより「最小カット問題」として捉えた方がいいかも。
○○以上 1 2 3 ... 500 ,- X1 について ○→○→○→...→○-, |- X2 について ○→○→○→...→○-| | : : | |- XN について ○→○→○→...→○-| S -| |-→ T | ○○未満 500 499 498 ... 1 | |- Y1 について ○→○→○→...→○-| |- Y2 について ○→○→○→...→○-| | : | `- YN について ○→○→○→...→○-'
こういう風な、$X,Y$ の値が何以上・何未満になるかを表す頂点を用意する。
制約上、$X,Y$ の値の最大値は500なので、その分だけ用意する。
後で辺を張る都合上、意味合いは $X$ と $Y$ で逆転させておく。
$X_i$ についてのカットが $S→U_{i,1}→U_{i,2}→...→U_{i,500}→T$ のどこか1箇所のみで発生するようにしたい。
また例えば $U_{i,3}→U_{i,4}$ でカットされた場合にコストが 3 発生するようにしたい。
それには以下のように辺を設定する。
ここに $M$ 個の頂点を追加し、$A_i$ による更新の制約を追加する。ここで燃やす埋めるっぽさが出る。
$A_{i,j}=a$ とすると、
というのを、各 $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$ についてちょうどよい箇所でカットされ、答えが求まる。