AtCoder Regular Contest 197 (Div. 2) A,B,C,D,E問題メモ

AtCoder Regular Contest 197 (Div. 2)

A - Union of Grid Paths

問題文

$H\times W$ のマス目があります．上から $h$ 行目，左から $w$ 列目のマスを $(h,w)$ で表します．
さらに，'D', 'R', '?' からなる長さ $H+W-2$ の文字列 $S=S_1\cdots S_{H+W-2}$ が与えられます．
はじめ，すべてのマスは白色で塗られています．あなたは次の $3$ つの手順からなる操作を何度でも行うことができます：
1. 以下の条件をすべて満たす長さ $H+W-2$ の文字列 $X=X_1\cdots X_{H+W-2}$ をひとつ選ぶ．
  - $X$ は $H-1$ 個の 'D' および $W-1$ 個の 'R' からなる．
  - $X$ は、 $S$ の '?' を 'D' または 'R' に置き換えた文字列である。
2. マス $(1,1)$ に立つ．さらに $i=1,2,\ldots$ の順に，文字 $X_i$ の表す方向に $1$ マス移動する．つまり， $X_i$ が 'D' ならば下方向， $X_i$ が 'R' ならば右方向に $1$ マス移動する．なお， $X$ が手順 1 の条件を満たすとき，移動先のマスは必ずマス目内に存在することが証明できる．
3. 手順 2 においてあなたが通ったすべてのマス（最初・最後のマスも含む）について，そのマスが白色で塗られているならば，黒色で塗る．
最終的に黒色で塗ることができるマスの個数としてありうる最大値を求めてください．
$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 2\times 10^5$
$2\leq H, W\leq 2\times 10^5$
$T,H,W$ は整数．
$S$ は 'D', 'R', '?' からなる長さ $H+W-2$ の文字列．
$S$ に含まれる 'D' の個数は $H-1$ 以下．
$S$ に含まれる 'R' の個数は $W-1$ 以下．
すべてのテストケースにわたる $H+W$ の総和は $4\times 10^5$ 以下．

解法

$S$ の '?' を、先頭からなるべく 'D' を優先して置換したものを $X_D$ 、'R' を優先して置換したものを $X_R$ とする。

答えは、 $X_D$ の軌跡と $X_R$ の軌跡、およびそれに挟まれたマスとなる。

各行 $i$ につき、以下を定義する。

$first_D[i]:= X_D$ の軌跡がはじめて $i$ 行目に訪れた時の列index
$last_D[i]:= X_D$ の軌跡が $i$ 行目から出る時の列index
$X_R$ に対しても同様に定義

$X_D$ は最大限早く下に降りる軌跡なので、 $(i, first_D[i])$ より左側はどんな $X$ でも通ることはできない。
$X_R$ は最大限長く上の方の行に留まる軌跡なので、 $(i,last_R[i])$ より右側はどんな $X$ でも通ることはできない。
その間は適当に置換した 'D' と 'R' を入れ替えれば通れる。

よって、 $\displaystyle \sum_{i=1}^{H}last_R[i]-first_D[i]+1$ が答えとなる。

Python3

B - Greater Than Average

問題文

空でない整数列 $x = (x_1, \ldots, x_n)$ のスコアを，「 $x$ の要素のうちで $x$ の平均値より大きなものの個数」として定めます．
- つまり， $x$ のスコアは $x_i \gt \dfrac{x_1+\cdots+x_n}{n}$ を満たす $i$ の個数です．
長さ $N$ の整数列 $A=(A_1,\ldots,A_N)$ が与えられます．
$A$ の空でない部分列に対するスコアの最大値を求めてください．
$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 2\times 10^5$
$2\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^9$
入力される値はすべて整数
すべてのテストケースにわたる $N$ の総和は $2\times 10^5$ 以下．

解法

とりあえず順番は関係ないのでソートする。

例えば、最適解が以下のような形だったとすると、

  小←---------------→大
A:  o  o  o  o  o  o  o     ~: 最適解で x に採用した値
    ~       |~  ~     ~     |: 最適解の x の平均値

平均以下の値を追加して平均値が上がることはないので、採用していない平均以下の値は採用していい。
これによってスコアが悪化することはない。

  小←---------------→大
A:  o  o  o  o  o  o  o
    ~  ^  ^| ~  ~     ~

また、平均より大きい2要素 $i \lt j$ で、 $i$ を採用せず $j$ を採用している場合、代わりに $i$ を採用することにして平均が上がることはない。

  小←---------------→大
A:  o  o  o  o  o  o  o
    ~  ~  ~| ~  ~  i  j

これを繰り返していくと、結局、スコアを悪化させず「小さい方から $k$ 個を全て採用」という形にできる。

他の最適解があっても、必ず同じスコアで小さい方から全て採用した形も存在すると言えるので、そういう形のみ調べればよい。

これは、 $k=1,2,3,...,N$ の順に素直に平均を計算し、 $A$ から平均を超える位置を二分探索することで、 $O(N \log{N})$ などで全て調べられる。

Python3

C - Removal of Multiples

問題文

すべての正整数からなる集合 $S$ があります．
$Q$ 個のクエリを順に処理してください． $i$ 番目のクエリでは， $2$ 以上の整数 $A_i$ および，正整数 $B_i$ が与えられるので，次の $2$ つのことを順に行ってください．
- $S$ から $A_i$ の倍数である要素をすべて削除する．
- $S$ の要素のうち小さい方から $B_i$ 番目のものを出力する．
  - なお本問の制約のもとで， $S$ はこの時点で $B_i$ 個以上の要素を含むことが証明できる．

制約

$1\leq Q\leq 10^5$
$2\leq A_i\leq 10^9$
$1\leq B_i\leq 10^5$
入力される値はすべて整数

解法

上限見積もりと計算量見積もりをちゃんとできますか、という問題。
ただ、できなくても本番中では勘やダメ元で解けた人もいそう。（手段がそれくらいしか無さそう、というのもある）

削除するパートはひとまず置いといて、答えを求めるパートは「 $x$ 以下で残っている $S$ の要素数はいくつ？」が解ければ $x$ を二分探索できる。だが、それにも二分探索のスタートとなる「答えの上限」が必要となる。

答えの上限を見積もる。
素数に着目する。素数は、 $A_i$ によって直接的に指定されない限り、 $S$ から削除されることは無い。
よって、 $Q \le 10^5$ 個の素数が削除された後、それ以外で小さい方から $B_i \le 10^5$ 番目の素数より大きな値が答えとなることは無い。
つまり、答えは $2 \times 10^5$ 個目の素数以下である。
そしてこれは、調べると $2.8 \times 10^6$ 程度であることが分かる。（これを $L$ とする）

$1～L$ くらいならあらかじめ全て $S$ として持っておくことができるので、 FenwickTree や SegmentTree で実装すれば、「 $x$ 以下の個数」がわかるため二分探索は可能となる。

残る問題は「削除パートで、SegTree から $A_i$ の倍数を削除する方法」である。
愚直にやってたら、毎回 $L/A_i$ の計算量がかかり、TLEしそう。上手い方法があるのか……？

実は愚直で良い。「過去にクエリとして飛んできた $A_i$ と同じものは再処理しない」などの自明な枝刈りをすれば通る。

調和級数1+1/2+1/3...が発散することの３通りの証明 | 高校数学の美しい物語

$A_i$ が全て異なる場合、調べる箇所数は以下となる。

$\displaystyle \left\lceil \frac{L}{A_1} \right\rceil + \left\lceil \frac{L}{A_2} \right\rceil + ... + \left\lceil \frac{L}{A_Q} \right\rceil$

これは、 $\displaystyle \sum_{i=1}^{L} \left\lceil \frac{L}{i} \right\rceil$ より小さい。
そしてこの式のオーダーは $O(L \log{L})$ となることが知られている。

Python3

        
          
          
              
              from operator import add
from typing import Callable, Any
import sys
 
input = sys.stdin.buffer.readline
 
 
class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木
 
    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成
 
    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """
 
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.n = n
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory
 
    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins
 
    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)
 
    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)
 
    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])
 
    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()
 
        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1
 
        return func(result_l, result_r)
 
    def get_all(self):
        return self.tree[1]
 
    def get_point(self, i):
        return self.tree[i + self.offset]
 
    def max_right(self, l: int, f: Callable[[Any], bool]) -> int:
        """
        [l,r) の集約値を op(l,r) としたとき、以下を満たす l <= r <= N の値 r のいずれか1つを得る。
          * f(op(l, r)) = True または r=l
          * f(op(l, r+1)) = False または r=N
 
        fが単調性を満たす場合、集約値で右端を二分探索する関数と解釈できる。
        """
        assert 0 <= l <= self.n
 
        if l == self.n:
            return self.n
 
        l += self.offset
        sm = self.idf()
        func = self.func
        tree = self.tree
 
        first = True
        while first or (l & -l) != l:
            first = False
            while l & 1 == 0:
                l >>= 1
            if not f(func(sm, tree[l])):
                while l < self.offset:
                    l <<= 1
                    tmp = func(sm, tree[l])
                    if f(tmp):
                        sm = tmp
                        l += 1
                return l - self.offset
            sm = func(sm, tree[l])
            l += 1
 
        return self.n
 
    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。
 
        Notes:
            "単体で" ev を満たす要素位置を求める関数である点に注意。
            a,a+1,a+2,... の集約値で評価する場合は max_right の方を使う。
 
        使用できる条件:
            [l, r) の集約値を f(l,r) としたとき、以下の2つが同値である。（(func, ev) = (min,ge), (max,le) など）
            ev(x, f(l,r))=True である ⇔ l <= i < r 内に ev(x, Ai)=True となる要素がある
 
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1
 
        if r_found == -1:
            return -1
 
        return self._leftmost_sub(r_found, x, ev)
 
    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset
 
    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。
 
        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1
 
        if l_found == -1:
            return -1
 
        return self._rightmost_sub(l_found, x, ev)
 
    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset
 
    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1
 
 
def solve(q, queries):
    limit = 1 << 22
    init = [1] * limit
    init[0] = 0
    fwt = SegmentTreeInjectable.from_array(init, int, add)
 
    def update(a):
        if a >= limit:
            return
        if fwt.get_point(a) == 0:
            return
        fwt.update(a, 0)
        for b in range(a + a, limit, a):
            if fwt.get_point(b) == 1:
                fwt.update(b, 0)
 
    buf = []
    for a, b in queries:
        update(a)
        ans = fwt.max_right(0, lambda x: x < b)
        buf.append(ans)
    return buf
 
 
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(q, queries)
print('\n'.join(map(str, ans)))

            

        
      

D - Ancestor Relation

問題文

$N\times N$ 行列 $A = (A_{i,j})$ ( $1\leq i,j\leq N$ ) が与えられます． $A$ の成分は $0$ または $1$ です．
頂点に $1$ から $N$ までの番号が付けられた $N$ 頂点の木 $G$ であって，次の条件を満たすものの個数を $998244353$ で割った余りを求めてください．
- $A_{i,j}=1$ であることと，以下の $2$ 条件のうち少なくともひとつが成り立つことは同値である：
  - 頂点 $1$ を根としたとき頂点 $j$ は頂点 $i$ の祖先である．つまり頂点 $j$ は，頂点 $1, i$ を結ぶ $G$ 上のパス上にある．
  - 頂点 $1$ を根としたとき頂点 $i$ は頂点 $j$ の祖先である．つまり頂点 $i$ は，頂点 $1, j$ を結ぶ $G$ 上のパス上にある．
ただし，パスの端点もパス上にあると見なします． $G$ は木であるとき， $2$ 頂点を結ぶ $G$ 上のパスは一意に存在することにも注意してください．
$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 10^5$
$2\leq N\leq 400$
$A_{i,j}\in \lbrace 0,1\rbrace$ $(1\leq i,j\leq N)$
$A_{i,i}=1$ $(1\leq i\leq N)$
$A_{i,j}=A_{j,i}$ $(1\leq i,j\leq N)$
すべてのテストケースにわたる $N^2$ の総和は $400^2$ 以下．

解法

行列 $A$ の $i$ 行目を、長さ $N$ のbitフラグとして捉えたものを $B_i$ とする。

頂点 $i$ に着目したとき、 $A_{i,j}=1$ は、「 $i$ の祖先か子孫に $j$ がいる」ことと同じになる。

❶--●--●-...-(i)--●--●--●    iにとって、
 |       |        `-●--●        ●: A_{i,j}=1 である相手頂点
 `--○   `--○--○   `--●        ○: A_{i,j}=0 である相手頂点
             `--○

$i$ とその子孫 $j$ にとって、 $B_i \supseteq B_j$ となる。

❶--●--●-...-(i)--◎--◎--◎    ●: i,j ともに 1 である相手
 |       |        `-●--(j)       ◎: i のみ 1 である相手
 `--○   `--○--○   `--◎        ○: i,j ともに 0 である相手

このような包含関係が成り立つように、各 $B_i$ に矛盾せず木を作れるか？をまず判定する必要がある。

ところで、サンプルなどからも確認できるように、 $i$ と $j$ の間に枝分かれが無く1本道の場合、 $B_i=B_j$ となる。

①--②--③--④    ②③④同士、⑤⑥同士は、それぞれBiが同じとなる
 `--⑤--⑥--⑦
         `--⑧

よって、 $B_i$ が同じ頂点同士は縮約して考える。

$D=(D_1,...,D_k):=B$ から重複を除いたもの
$G=(G_1,...,G_k):=(B_j=D_i)$ である $j$ の集合をbitフラグ化したもの
$C=(C_1,...,C_k):=(B_j=D_i)$ である $j$ の個数

これを元に、矛盾の判定方法を考える。

まず、頂点1は全ての頂点と子孫関係にあるので、 $B_1=1111...1$ でなければならない。0が含まれる場合は矛盾なので $0$ 通り。

$D$ をbit中に含まれる '1' が多い順にソートする。（ $G,C$ もそれに合わせて並び替える）
これで、 $i$ の親 $p$ は（存在するとすれば） $p \lt i$ の範囲にあることが保証され、考えやすくなる。

$i=2,...,k$ の順に、以下を調べる。

$j=1,...,i-1$ に対し、 $D_i \subset D_j$ か（ $D_i \& D_j = D_i$ か）調べる。
- 当てはまる場合、 $j$ は $i$ の祖先である。
  - $G_j \subset D_i$ か調べる。違ったら矛盾。
- 当てはまらない場合、 $j$ と $i$ はどこかで分岐した別の枝にあり、子孫関係にあってはいけない。
  - $D_i$ と $G_j$ に共通部分が無いか調べる。存在したら矛盾。
  - $D_j$ と $G_i$ に共通部分が無いか調べる。存在したら矛盾。

最後まで矛盾が無ければ、各 $D_i$ は「自分と祖先・子孫関係にある頂点番号は立ち、それ以外の頂点番号は立っていない」ので、問題文中の定義通りであることが確認できる。

$O(N^3)$ で判定できる。

矛盾が無い場合、条件を満たす木から、 $B_i$ が同じもの同士を入れ替えても成り立つ。
逆に言うと、 $D$ から導かれる親子関係はガチガチに決まってしまうため、それくらいしか自由度が無い。
各 $i$ につき並べ方は $C_i!$ 通りだが、 $C_1$ に限っては、必ず根で無ければならない頂点1を含む。

答えは、 $\displaystyle (C_1-1)! \times \prod_{i=2}^k C_i!$ となる。

Python3

        
          
          
              
              from collections import defaultdict
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    return factorials
 
 
def solve(n, aaa):
    full = (1 << n) - 1
    if aaa[0] != full:
        return 0
 
    loc = defaultdict(list)
    for i in range(n):
        loc[aaa[i]].append(i)
 
    keys = list(loc.keys())
    keys.sort(key=lambda bit: (bit ^ full).bit_count())
 
    groups = []
    for k in keys:
        g = 0
        for l in loc[k]:
            g |= 1 << l
        groups.append(g)
 
    m = len(loc)
    for i in range(1, m):
        ki = keys[i]
        for j in range(i):
            kj = keys[j]
            if ki & kj == ki:
                if ki & groups[j] != groups[j]:
                    return 0
            else:
                if kj & groups[i] != 0:
                    return 0
                if ki & groups[j] != 0:
                    return 0
 
    MOD = 998244353
    lens = list(map(len, loc.values()))
    mx = max(lens)
    facts = precompute_factorials(mx, MOD)
    ans = facts[lens[0] - 1]
    for l in lens[1:]:
        ans *= facts[l]
        ans %= MOD
    return ans
 
 
t = int(input())
for _ in range(t):
    n = int(input())
    aaa = []
    for _ in range(n):
        row = int(input().replace(' ', '')[::-1], base=2)
        aaa.append(row)
    ans = solve(n, aaa)
    print(ans)

            

        
      

E - Four Square Tiles

問題文

正整数 $N, H, W$ が与えられます．ただし， $H, W \leq 3N-1$ が成り立ちます．
$H\times W$ のマス目に $N\times N$ の正方形のタイルを $4$ 個置く方法であって，以下の条件をすべて満たすものの個数を $998244353$ で割った余りを求めてください．
- 各タイルは，マス目のちょうど $N^2$ 個のマスを完全に覆う．
- ひとつのマスが複数のタイルによって覆われてはならない．
ただし，タイル同士は区別しません．
$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 2\times 10^5$
$1\leq N,H,W\leq 10^9$
$H,W\leq 3N - 1$
入力される値はすべて整数

解法

$H,W \le 3N-1$ より、タイルは3つは縦横に並べられないという制約がある。

タイルは、位置関係を「左上、右上、左下、右下」と呼べるような位置関係にしか配置できない。

厳密な定式化と証明
- 解説 - AtCoder Regular Contest 197 (Div. 2)

グリッドを2次元座標と捉え、格子点を $(0,0)～(H,W)$ （左上が原点）とし、各タイルの位置を以下のように定義する。

$(y_1,x_1)$ : 左上タイル（タイル1とする）の右下の格子点座標
$(y_2,x_2)$ : 右上タイル（タイル2とする）の左下の格子点座標
$(y_3,x_3)$ : 左下タイル（タイル3とする）の右上の格子点座標
$(y_4,x_4)$ : 右下タイル（タイル4とする）の左上の格子点座標

(y1,x1) (y2,x2)
 ─┛     ┗─
 ─┓     ┏─
(y3,x3) (y4,x4)

こうすると、全て共通して $N \le y_i \le H-N,N \le x_i \le W-N$ という制約にできる。
また、重ならない判定も、 $x_i \le x_j$ or $y_i \le y_j$ のように、単純な形になる。

この上で配置を数えたいのだが、取っかかりとして、以下を使う。

$y_1 \le y_4$ または $y_2 \le y_3$ の少なくともいずれか一方は成り立つ（★）

要は、対角上にあるタイルの組のどっちかは、高い方の下辺が、低い方の上辺と、同じか、より上にある。
こうなっているペアをまず固定して、そこに残り2つを配置することを考えると、タイルが重なるような配置が限定され、多少考えやすくなる（ような気がした）。

(★)が成り立つペアを（1,4）に固定した場合の数 × 2 - 両方のペアが(★)を満たす場合の数

が、答えとなる。

「(★)が成り立つペアを（1,4）に固定した場合の数」を考える。 $y$ 座標と $x$ 座標を別々に考える。
まず、「タイル (2,3) が重なってもよい場合の数」を数え、重なる場合の数を引く。

重なっても良い場合の数
- $y$ 座標
  - 以下のいずれかの大小関係を満たす $(y_1,y_2,y_3,y_4)$ の組の個数
    - $N \le y_1 \le y_2 \le y_3 \le y_4 \le H-N$
    - $N \le y_2 \le y_1 \le y_3 \le y_4 \le H-N$
    - $N \le y_1 \le y_2 \le y_4 \le y_3 \le H-N$
    - $N \le y_2 \le y_1 \le y_4 \le y_3 \le H-N$
    - $N \le y_1 \le y_3 \le y_2 \le y_4 \le H-N$
  - それぞれは $\dbinom{H-2N+4}{4}$ だが、単純に5倍ではどこかで＝が成立する場合に重複する。
  - 包除原理で「＝が成立する個数」で場合分けし、重複を除く。
  - $5\dbinom{H-2N+4}{4}-5\dbinom{H-2N+3}{3}+\dbinom{H-2N+2}{2}$
- $x$ 座標
  - 「 $N \le x_1 \le x_2 \le W-N$ となるような $(x_1,x_2)$ の数」の2乗
  - $\dbinom{W-2N+2}{2}^2$
重なる場合の数
- 以下の2つが同時に成り立つとき、重なる。
  - $N \le y_1 \le y_3 \lt y_2 \le y_4 \le H-N$
  - $N \le x_1 \le x_3 \lt x_2 \le x_4 \le W-N$
- 差分を取って考えると、 $H-2N-1$ 個のボールを5個の箱に重複を許して入れると考えられる
- $\dbinom{H-2N+3}{4} \times \dbinom{W-2N+3}{4}$

「両方のペアが(★)を満たす場合の数」を考える。
$x$ 座標は重なっても良い場合と変わらない。
$y$ 座標は、重なっても良い場合から最後の $N \le y_1 \le y_3 \le y_2 \le y_4 \le H-N$ を除いたものとなる。

同様に包除原理で考えて、
- $4\dbinom{H-2N+4}{4}-4\dbinom{H-2N+3}{3}+\dbinom{H-2N+2}{2}$

以上で必要な情報は揃った。いずれも $O(1)$ で計算できるため、全体 $O(T)$ で求められる。

Python3

より簡単な解法

上の解法で、途中で「 $y$ と $x$ を分けて考えていい」と気付いて、フラットに最初からもう一度考えると確かにこの解法はわかるんだけど、試行錯誤の途中だとなかなか今試している解法から脱却できないね。

解説 - AtCoder Regular Contest 197 (Div. 2)

2変数ずつ4ペアを、独立に決めればよい。

    N ≦ x1 ≦ x2 ≦ W-N
         │    │
N        │    │       N
∧       │    │       ∧    ※∧は≦の縦書きの代用のため
y1 ───┘    └─── y2      実際はイコールを含む
∧                      ∧
y3 ───┐    ┌─── y4
∧       │    │       ∧
H-N      │    │       H-N
         │    │
    N ≦ x3 ≦ x4 ≦ W-N

この決め方は、 $\dbinom{H-2N+2}{2}^2\dbinom{W-2N+2}{2}^2$ となる。

このように座標を決めると、上下左右に隣り合うタイルは重ならないことが保証されるが、「対角上にある位置関係のタイル」のみ、重なっているものまで数えている。

斜めのタイルが重なる場合の数は1つめの解法で求めたように、 $\dbinom{H-2N+3}{4} \dbinom{W-2N+3}{4}$ となる。
重なりうるペアは2通り（1と4、2と3）あり、この2ペアが同時に重なることはないため、単純に全体からこの2倍を除けばよい。

Python3

−目次

AtCoder Regular Contest 197 (Div. 2) A,B,C,D,E問題メモ

A - Union of Grid Paths

問題文

制約

解法

B - Greater Than Average

問題文

制約

解法

C - Removal of Multiples

問題文

制約

解法

D - Ancestor Relation

問題文

制約

解法

E - Four Square Tiles

問題文

制約

解法

より簡単な解法