AtCoder Regular Contest 190 (Div. 1) A,B問題メモ

AtCoder Regular Contest 190 (Div. 1)

A - Inside or Outside

問題文

整数列 $x = (x_1, \ldots, x_N)$ があり，$x_1=\cdots=x_N=0$ で初期化されています．
あなたはこの整数列について，$M$ 回の操作を行います．$i$ 回目の操作では，$1\leq L_i\leq R_i\leq N$ を満たす整数の組 $(L_i, R_i)$ が与えられるので，以下の $3$ つのうちちょうど $1$ つを行います．
- 操作 $0$：何もしない．この操作にはコストが $0$ かかる．
- 操作 $1$：$1\leq j\leq N$ を満たす各整数 $j$ に対して，$L_i\leq j\leq R_i$ を満たすならば $x_j=1$ と定める．この操作にはコストが $1$ かかる．
- 操作 $2$：$1\leq j\leq N$ を満たす各整数 $j$ に対して，$L_i\leq j\leq R_i$ を満たさないならば $x_j=1$ と定める．この操作にはコストが $1$ かかる．
あなたの目標は，最終的に $x_1=\cdots=x_N=1$ が成り立つようにすることです．この目標が達成できるか否かを判定してください．目標が達成可能な場合には，そのような方法のうち操作にかかるコストの総和が最小となるものをひとつ答えてください．

制約

$1\leq N\leq 1000000$
$1\leq M\leq 200000$
$1\leq L_i\leq R_i\leq N$
入力される値はすべて整数

解法

イメージとしては、$M$ 個の区間からなるべく少ない区間を選んで「区間内を塗る」か「区間外を塗る」かを行い、全てが塗られた状態にしてください、という問題。

丁寧場合分け。
達成できる場合は、3回以内で必ず達成可能。

答えが1の場合

これは明らかで、$(L_i,R_i)=(1,N)$ なる $i$ があったらOK。

$M=1$ で、答えが1の場合に当てはまらなければ、達成不可。

答えが2の場合

大きく分けて3通りの方法がある。

以下に置ける、区間の内外どちらを採用するかの記号の意味
      L    R
| - - |====| - - - -|    L～R の内を"1"にする
| = = |----| = = = =|    L～R の外を"1"にする

① 2つとも内を採用
|=========| - - - - |
| - - - |===========|

② 片方は内、片方は外を採用
②-a 左は内、右は外を採用
|=========| - - - - |
| = |---| = = = = = |
②-b 左は外、右は内を採用
| = = = = = |---| = |
| - - - |===========|
②-c 外採用の間を内採用の区間が埋める
| = = = |---| = = = |
| - - |=======| - - |

③ 2つとも外を採用。
| = = = = = |---| = |
| = |---| = = = = = |

①は、「$L_i=1$ の区間の内、$R_i$ 最大のもの」と「$R_j=N$ の区間の内、$L_j$ 最小のもの」を（存在すれば）比べればよい。

②は、どのケースを取っても、一方が一方に内包されていればよい。$(L_i,-R_i)$ でソートして確認できる。

③は、「$L_i$ 最大のもの」と「$R_j$ 最小のもの」を比べればよい。

$M = 2$ で、答えが1,2の場合に当てはまらなければ、達成不可。

答えが3の場合

「$L_i$ 最大のもの」と「$R_j$ 最小のもの」と「あと何でもいいのでもう1つ」で確実にできる。

      L       R
| = = |---------| = |  Li最大
| = |---------| = = |  Rj最小

|- - |=========| - -|  Li最大でもRj最小でもない区間は、
                       上の2つの間を必ず埋められる。

Python3

from operator import itemgetter


def solve(n, m, ops):
    ans = [0] * m

    ops = [(i, l - 1, r) for i, (l, r) in enumerate(ops)]
    op1_left = []  # l=1 の中で最大 r を持つものの (番号, l, r)
    op1_right = []  # r=n の中で最小 l を持つものの (番号, l, r)
    op2_left = []  # l!=1 の中で最大の l をもつものの (番号, l, r)
    op2_right = []  # r!=n の中で最小の r をもつものの (番号, l, r)
    for i, l, r in ops:
        if l == 0:
            op1_left.append((i, l, r))
        else:
            op2_left.append((i, l, r))
        if r == n:
            op1_right.append((i, l, r))
        else:
            op2_right.append((i, l, r))

    op1_left.sort(key=itemgetter(2), reverse=True)
    op1_right.sort(key=itemgetter(1))
    op2_left.sort(key=itemgetter(1), reverse=True)
    op2_right.sort(key=itemgetter(2))

    # print(op1_left)
    # print(op1_right)
    # print(op2_left)
    # print(op2_right)

    if op1_left and op1_left[0][2] == n:
        ans[op1_left[0][0]] = 1
        return 1, ans

    if m == 1:
        return -1, None

    if op1_left and op1_right:
        if op1_left[0][2] >= op1_right[0][1]:
            ans[op1_left[0][0]] = 1
            ans[op1_right[0][0]] = 1
            return 2, ans

    if op1_left and op2_right:
        for i, j in ((0, 0), (0, 1), (1, 0)):
            if len(op1_left) <= i or len(op2_right) <= j:
                continue
            if op1_left[i][0] == op2_right[j][0]:
                continue
            if op1_left[i][2] >= op2_right[j][2]:
                ans[op1_left[i][0]] = 1
                ans[op2_right[j][0]] = 2
                return 2, ans

    if op2_left and op1_right:
        for i, j in ((0, 0), (0, 1), (1, 0)):
            if len(op2_left) <= i or len(op1_right) <= j:
                continue
            if op2_left[i][0] == op1_right[j][0]:
                continue
            if op2_left[i][1] >= op1_right[j][1]:
                ans[op2_left[i][0]] = 2
                ans[op1_right[j][0]] = 1
                return 2, ans

    if op2_left[0][1] >= op2_right[0][2]:
        ans[op2_left[0][0]] = 2
        ans[op2_right[0][0]] = 2
        return 2, ans

    ops.sort(key=lambda a: (a[1], -a[2]))
    max_r = (0, 0)
    for i, l, r in ops:
        if max_r[0] >= r:
            ans[i] = 2
            ans[max_r[1]] = 1
            return 2, ans
        max_r = (r, i)

    if m == 2:
        return -1, None

    li = op2_left[0][0]
    ri = op2_right[0][0]
    ans[li] = 2
    ans[ri] = 2
    for i in range(m):
        if i != li and i != ri:
            ans[i] = 1
            break
    return 3, ans


n, m = map(int, input().split())
ops = [tuple(map(int, input().split())) for _ in range(m)]
cost, ans = solve(n, m, ops)
if cost == -1:
    print(-1)
else:
    print(cost)
    print(*ans)

B - L Partition

問題文

$N\times N$ のマス目があります．上から $i$ 行目，左から $j$ 列目のマスを $(i,j)$ で表します．
$K=1,2,\ldots,N$ に対して，レベル $K$ の L 型とは，以下のような形、及びこれを90,180,270度回転させた形を指します。
- ```
レベル1    レベル2    レベル3
             □       □
  □         □□     □
                      □□□
```

マス $(a,b)$ および $Q$ 個のクエリ $k_1, \ldots, k_Q$ が与えられます．
各 $i$ に対して，マス目全体をレベル $1, \ldots, N$ それぞれひとつずつの L 型に分割する方法であって，マス $(a,b)$ がレベル $k_i$ の L 型に含まれるようなものの個数を $998244353$ で割った余りを答えてください．

制約

$1\leq N\leq 10^7$
$1\leq a\leq N$
$1\leq b\leq N$
$1\leq Q\leq \min\lbrace N, 200000\rbrace$
$1\leq k_1 \lt \cdots \lt k_Q \leq N$
入力される値はすべて整数である

解法

レベル $k$ のL型の位置を固定した時の数え上げ

大きいレベルのL型から埋めて行くことを考えると、

レベル $N$ は、盤面をフルに使って4通りの転回形のどれかの形でしか入れられない
- →残る盤面は（位置こそ異なれど）$N-1 \times N-1$
レベル $N-1$ は、残った盤面をフルに使って4通りの転回形のどれかの形でしか入れられない
- →残る盤面は $N-2 \times N-2$
…

なので、$(a,b)$ に置く種類を無視すると、あり得る盤面は全部で $4^{N-1}$ 通りとなる。
レベル1のL型は転回しても同じなことに注意。

ここから、なんかタングラムのように複雑にL型が絡み合った配置にはなりようが無く、レベル $k-1$ 以下のL型は、全てレベル $k$ のL型のへこんだ部分に収まるしか無いということも分かる。

逆からの発想として、レベル $k$ のL型を置く位置を決めてしまった場合の、他のL型の配置方法の個数を考える。
（実装上、マス目のindexを0から始めるとする）

   0 1 2 3 4 5 6 7
0 □□□□□□□□    (2,3)～(5,6) の矩形に レベル4 のL型を置く
1 □□□□□□□□
2 □□□■■■■□
3 □□□○○○■□
4 □□□○○○■□
5 □□□○○○■□
6 □□□□□□□□
7 □□□□□□□□

この時、残る $3 \times 3$ の矩形（上記○印）をレベル3以下のL型で埋めるのは、先ほどの考え方で $4^{k-2}$ 通り。

矩形の外側をレベル5以上のL型で埋めるのは、$\binom{4}{2} \times \binom{4}{3}$ 通りとなる。
レベル5,6,… の順にキャベツの葉のように覆い被せながら配置を決めていく様子をイメージする。
矩形の外側には「縦に見ると上に2個、下に2個の空行」「横に見ると左に3個、右に1個の空列」が残っていて、 1つのL型で、1行1列を埋めることができる。
「上、左の組合せなら┌ 型」のように、転回すればどの ( {上,下}, {左, 右} ) の組にも対応できるので、縦と横は独立に決めてもよい。よって、$\binom{4}{2} \times \binom{4}{3}$ で求められる。

一般化すると、左上が $(i,j)$ である $k \times k$ の矩形の中にレベル $k$ のL字を向きを決めて置いたとすると、

$k=1$ の時、$\binom{N-k}{i} \times \binom{N-k}{j}$
$k \ge 2$ の時、$4^{k-2} \times \binom{N-k}{i} \times \binom{N-k}{j}$

通りの他のレベルの配置があり得ることになる。

よって、「$(a,b)$ にレベル $k$ のL型が置かれる」ような各場合に付き、上記を足し合わせれば求められる。

しかし、それでは1クエリ $O(N)$ かかり、全体で $O(NQ)$ でTLEしてしまう。

二項係数の累積和

$k=1$ の時は上記で問題なく求められるため、$k \ge 2$ とする。

レベル $k$ のL型を $(a,b)$ に置こうと思うと、 $k \times k$ の矩形の上下左右のいずれかの端を $(a,b)$ に合わせつつ、矩形全体が $N \times N$ に収まっていないといけない。

$k \times k$ の矩形の上、下、左、右それぞれの端を $(a,b)$ に合わせられるか確認し、合わせられるならその場合の答えを合計する。
ただし、$(a,b)$ を矩形の角に合わせられる場合、2回重複して数えられているので引く。
これで $k$ に対する答えが求められる。

たとえば右端を $(a,b)$ にあわせるためには、

   0 1 2 3 4 5 6 7       0 1 2 3 4 5 6 7    (a,b)=(2,6)  k=4
0 □□□■■■■□    0 □□□□□□□□
1 □□□□□□■□    1 □□□□□□□□    bを右端に合わせるとき、
2 □□□□□□●□    2 □□□■■■●□    左端の列は b-k+1 より、
3 □□□□□□■□    3 □□□□□□■□    これが >= 0 なら右端に合わせられる。
4 □□□□□□□□    4 □□□□□□■□
5 □□□□□□□□    5 □□□□□□■□    u = max(0, a-k+1) から
6 □□□□□□□□    6 □□□□□□□□    d = min(N-k, a)   までの i に対し
7 □□□□□□□□    7 □□□□□□□□    (i, b-k+1) を左上とした矩形が合わせられる。

この時、（上下ひっくり返したL型もあるので2倍して）矩形の右端に $(a,b)$ を合わせてレベル $k$ のL型を置き、それに合わせて他のL型も配置する方法は以下の数だけある。

$\displaystyle \sum_{i=u}^{d} 2 \times 4^{k-2} \times \binom{N-k}{i} \times \binom{N-k}{b-k+1}$
$\displaystyle = 2 \times 4^{k-2} \times \binom{N-k}{b-k+1} \times \sum_{i=u}^{d} \binom{N-k}{i}$

Σの外は $k$ と定数のみに依存するので、Σの中、パスカルの三角形の $N-k$ 段目の、左から $u～d$ 番目の項の合計が高速に分かれば良い。
これを求めるのはどうしても $O(N)$ かかり、普通にやると $O(NQ)$ のまま計算量は減ってない。

だが実は、クエリを通して様々な $k$ で必要になるこの区間和の区間 $[u,d]$ は、段毎に規則的な形となっている。

0        ●
1       ●●       ●: 区間和として各段で必要となる要素
2      ●●●
3     ●●●○     ←a+1 段目から右端が欠け始める
4    ●●●○○
5   ●●●○○○
6  ○●●○○○○  ←N-a 段目から左端が欠け始める
7 ○○●○○○○○

パスカルの三角形の各要素は下段に2回ずつ波及するので、区間和が大きく被っているとほぼ「$i$ 段目の区間和 = $i-1$ 段目の区間和 $\times 2$」となる。
端の要素だけが2回でなく1回だけ加算されるため、そこだけ調整すればよくなる。

類題: ABC235 G

よって、各段で必要となる区間和を $O(N)$ でまとめて事前計算できる。

今回は右端を合わせたが、上下左端を合わせる場合も同様に計算し、後は角で重複する分を引けば、$k$ に対する答えが求められる。

左右端をあわせる場合は上記のように $a$ を基準とした区間和が必要になるが、上下端を合わせる場合はまた別途 $b$ を基準とした区間和が必要になるので、事前計算は2通り必要になる。