−目次

AtCoder Regular Contest 176 （Sponsored by Mynavi）A,B,D,E問題メモ
- A - 01 Matrix Again
  - 問題
  - 解法
  - 解法2
- B - Simple Math 4
  - 問題
  - 解法
- D - Swap Permutation
  - 問題
  - 解法
- E - Max Vector
  - 問題
  - 解法

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

解法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$ グループに満たなければ適当に追加すればよい。

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

説明中では、3パターンにまでまとめられると言っているが、この実装では、②と⑤、④と⑥がそれぞれ同じになることのみ利用して、5×5の遷移行列を計算している。

        
          
          
              
              import numpy as np
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs
 
 
def get_matrix(n, MOD):
    facts, finvs = precompute_factorials(n, MOD)
 
    def ncr(n, r):
        if n < r:
            return 0
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD
 
    # 1回の入れ替えにより、隣り合った2つの状態の個数の変化を表す遷移行列。
    # 2つの初期状態が (X,Y)、入れ替わった後の状態を (x,y) とし、X,Yのいずれでもない数を Z とすると
    #   0: x=X, y=Y 初期から変わらない
    #   1: (x=X,y=Z) or (x=Z,y=Y) 一方のみ変わらず、もう一方が異なる数字が入っている
    #   2: x=Y, y=X 初期から入れ替わっている
    #   3: (x=Y,y=Z) or (x=Z,y=X) 一方にもう一方の数字が入り、もう一方は異なる数字が入っている
    #   4: x=Z, y=Z どちらにも、初期と異なる数字が入っている
 
    # ※後からわかったが、この場合分けは、より少ない (0,2),(1,3),(4) の3要素にまとめることができる
 
    mat = np.zeros((5, 5), np.int64)
    mat[0, 0] = ncr(n - 2, 2)
    mat[0, 1] = (n - 2) * 2
    mat[0, 2] = 1
    mat[1, 0] = 1
    mat[1, 1] = ncr(n - 1, 2) - 1
    mat[1, 3] = 2
    mat[1, 4] = n - 3
    mat[2, 0] = 1
    mat[2, 2] = ncr(n - 2, 2)
    mat[2, 3] = (n - 2) * 2
    mat[3, 1] = 2
    mat[3, 2] = 1
    mat[3, 3] = ncr(n - 1, 2) - 1
    mat[3, 4] = n - 3
    mat[4, 1] = 2
    mat[4, 3] = 2
    mat[4, 4] = ncr(n, 2) - 4 if n >= 4 else 0
    return mat
 
n, m = map(int, input().split())
ppp = list(map(int, input().split()))
MOD = 998244353
 
if n == 2:
    print(abs(ppp[0] - ppp[1]))
    exit()
 
mat = get_matrix(n, MOD)
base = np.eye(5, dtype=np.int64)
k = m
while k:
    if k & 1:
        base = base @ mat % MOD
    mat = mat @ mat % MOD
    k >>= 1
 
result = base[0]
INV2 = pow(2, -1, MOD)
INV_N2 = pow(n - 2, -1, MOD)
c1 = int(result[0] + result[2])  # 初期で隣り合った2つが（入れ替わっているかもしれないにせよ）隣り合った状況が変わらないパターン
c2 = int(result[1] + result[3]) * INV2 % MOD * INV_N2 % MOD  # 一方だけが残っているパターン（※1）
if n > 3:
    c3 = int(result[4] * 2) * INV_N2 % MOD * pow(n - 3, -1, MOD) % MOD  # 両方、いずれとも異なる数字になっているパターン（※2）
else:
    c3 = 0
# ※1: 続く差分の計算時、p1,p2 以外の N-2 個との差分の合計をまとめてかけるため、あらかじめ実際の個数の N-2 分の1倍しておく
# ※2: 続く差分の計算時、p1,p2 以外の数字のペア (N-2)(N-3)/2 個の差分の合計をまとめてかけるため、実際の個数の それ 分の1倍しておく
 
total_diff = []  # i を一方として、他のN-1個の数字との差分の絶対値の合計
for i in range(n):
    tmp = i * (i + 1) // 2 % MOD
    j = n - i - 1
    tmp += j * (j + 1) // 2
    total_diff.append(tmp % MOD)
all_total_diff = sum(total_diff) % MOD * INV2 % MOD
 
ans = 0
for i in range(n - 1):
    p1 = ppp[i] - 1
    p2 = ppp[i + 1] - 1
    d = abs(p1 - p2)
    others = all_total_diff - total_diff[p1] - total_diff[p2] + d
    ans += d * c1 % MOD
    ans += (total_diff[p1] - d + total_diff[p2] - d) * c2 % MOD
    ans += others * c3 % MOD
    ans %= MOD
 
print(ans)

            

        
      

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

        
          
          
              
              from collections import deque
from typing import Tuple, List
 
 
class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """
 
    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
 
    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
 
    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth
 
    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]
 
        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0
 
        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])
 
        for link in fwd_links:
            link[0] -= f
 
        for link in bwd_links:
            link[0] += f
 
        return f
 
    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow
 
    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges
 
 
n, m = map(int, input().split())
xxx = list(map(int, input().split()))
yyy = list(map(int, input().split()))
aaaaaa = [list(map(int, input().split())) for _ in range(m)]
 
max_a = max(max(map(max, aaaaaa)), max(xxx), max(yyy))
dnc = Dinic(n * max_a * 2 + m + 2)
 
s = n * max_a * 2 + m
t = s + 1
INF = 1 << 60
 
offset1 = n * max_a
offset2 = n * max_a * 2
 
for k in range(n):
    x = xxx[k]
    u = k * max_a + x - 1
    dnc.add_link(s, u, INF)
    for j in range(x, max_a):
        u1 = k * max_a + j - 1
        u2 = u1 + 1
        dnc.add_link(u1, u2, j)
        dnc.add_link(u2, u1, INF)
    u1 = k * max_a + max_a - 1
    dnc.add_link(u1, t, max_a)
 
    y = yyy[k]
    v = offset1 + k * max_a + y - 1
    dnc.add_link(v, t, INF)
    for j in range(y, max_a):
        v1 = offset1 + k * max_a + j - 1
        v2 = v1 + 1
        dnc.add_link(v2, v1, j)
        dnc.add_link(v1, v2, INF)
    v1 = offset1 + k * max_a + max_a - 1
    dnc.add_link(s, v1, max_a)
 
for i in range(m):
    u = offset2 + i
    aaa = aaaaaa[i]
    for k in range(n):
        a = aaa[k]
        v = k * max_a + a - 1
        dnc.add_link(u, v, INF)
        v = offset1 + k * max_a + a - 1
        dnc.add_link(v, u, INF)
 
ans = dnc.max_flow(s, t)
print(ans)

            

        
      