トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377) E,F,G問題メモ

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377)

E - Permute K times 2

問題文

$(1,2,\ldots,N)$ の並べ替え $P=(P _ 1,P _ 2,\ldots,P _ N)$ が与えられます。
次の操作を $K$ 回行います。
- $i=1,2,\ldots,N$ に対して同時に $P _ i$ を $P _ {P _ i}$ で更新する
すべての操作を終えたあとの $P$ を出力してください。

制約

$1\leq N\leq2\times10 ^ 5$
$1\leq K\leq10 ^ {18}$
$1\leq P _ i\leq N\ (1\leq i\leq N)$
$P _ i\neq P _ j\ (1\leq i\lt j\leq N)$
入力はすべて整数

解法

問題設定としてよくありそうだけど、実は初めて？なのか、忘れてるのか、解法がすぐにはわからなかった。

i  0 1 2 3 4
P  4 2 0 1 3

まず $0→4→3→1→2→0$ のように、 $i→P_i→...$ と辿っていってループをその順に並べる。
操作の過程で、これらのindexの位置に、これら以外の数字が来ることはないので、ループ毎に考える。

1回目の操作では、 $i=0$ にある $4$ は、矢印を辿って $3$ に変化する。他の値も、1回矢印を辿った値に変化する。

$k$ 回操作後の $P$ を $Q_k$ とすると、

i   0 1 2 3 4
Q0  4 2 0 1 3
Q1  3 0 4 2 1
Q2  2 3 1 4 0
Q3  1 4 3 0 2
Q4  4 2 0 1 3

矢印を辿っていけばいいのかな？と $i=0$ の位置の変化に着目しても、 $4→3→2→1→4→...$ であり、ループの順 $0→4→3→1→2$ とは合わない。う～む。

1回1回詳しく見ると、 $Q_1[0]=3$ になった時、 $Q_1[3]=2$ であり、これが次の $Q_2[0]$ となる。

$Q_1$ までに $i=0$ から $0→4→3$ と変化しているのと同時に、 $i=3$ からは $3→1→2$ と変化しており、 $Q_1$ から $Q_2$ へは、この2回分の変化を一気に辿っていると言える。
よって、 $Q_2$ は、元のループから見ると、 $Q_1$ から2つ分進めた値となることがわかる。

同様に $Q_2[0]=2$ から $Q_3[0]=1$ へは、 $i=0$ が $0→4→3→(1)→2$ と辿った後に続き、 $i=2$ が辿った $2→0→4→(3)→1$ という4回分のループを一気に辿るといえる。
最初の $i=0$ からループを開始するとみると、あわせて8回分ループを辿った先となる。
このように、2倍ずつループを進める数が増えていく。

■Qk の時に i=0 に来る値

  0→4→3→1→2→0→4→3→1→2→0→4→3→1→2→0→4→...
k    0  1     2           3                       4

各位置から $2^K$ だけループを進めた値が、最終的な $Q_K$ になる。

Python3

F - Avoid Queen Attack

問題文

縦 $N$ マス、横 $N$ マスの $N ^ 2$ マスからなる盤面に、 $M$ 個のクイーンが置かれています。
- $k$ 番目 $(1\leq k\leq M)$ のクイーンはマス $(a _ k,b _ k)$ に置かれています。
クイーンは、縦・横・斜め45度の好きな方向に好きなだけ移動できます。
クイーンの利きにないマスがいくつあるか求めてください。

制約

$1\leq N\leq10 ^ 9$
$1\leq M\leq10 ^ 3$
$1\leq a _ k\leq N,1\leq b _ k\leq N\ (1\leq k\leq M)$
$(a _ k,b _ k)\neq(a _ l,b _ l)\ (1\leq k\lt l\leq M)$
入力はすべて整数

解法

同じクイーンが同じ列や同じナナメにあることもあるのがややこしい。
1つのクイーンの利きを4本の縦・横・ナナメの直線に分解し、「直線が引かれないマス」を数えると考える。異なるクイーンから同じ列に直線ができた場合、重複は除いて1本と捉える。

答えは以下になる。大まかに全体から直線が引かれるマスを引いた後、引きすぎた分を戻す。
重複を除くことで、あるマスに引かれうる直線の本数は最大4本となり、引きすぎた分を考えやすくなる。

                               全マス N x N
 - 各直線について個別に、引かれるマスの合計  ...①
 +            2本の直線が交差するマス数 x 1   ┬②
 +            3本の直線が交差するマス数 x 2   ┤
 +            4本の直線が交差するマス数 x 3   ┘
--------------------------------------------

①は $O(M)$ で計算できる。
②も、直線同士の交点となるマスの数は $O(M^2)$ に限られるので、各交点につき交差する直線ペア数を数えていけば $O(M^2)$ で求められる。

Python3

        
          
          
              
              from collections import defaultdict
 
 
def solve(n, m, queens):
    rows = set()
    cols = set()
    diag1 = set()
    diag2 = set()
    for i in range(m):
        x, y = queens[i]
        rows.add(x)
        cols.add(y)
        diag1.add(x + y)
        diag2.add(x - y)
 
    controlled = (len(rows) + len(cols)) * n
    for rc in diag1:
        if rc <= n + 1:
            controlled += rc - 1
        else:
            controlled += n * 2 - rc + 1
    for rc in diag2:
        controlled += n - abs(rc)
 
    duplicated = defaultdict(int)
    for r in rows:
        for c in cols:
            duplicated[r, c] += 1
        for rc in diag1:
            c = rc - r
            if 1 <= c <= n:
                duplicated[r, c] += 1
        for rc in diag2:
            c = r - rc
            if 1 <= c <= n:
                duplicated[r, c] += 1
    for c in cols:
        for rc in diag1:
            r = rc - c
            if 1 <= r <= n:
                duplicated[r, c] += 1
        for rc in diag2:
            r = rc + c
            if 1 <= r <= n:
                duplicated[r, c] += 1
    for rc1 in diag1:
        for rc2 in diag2:
            if rc1 % 2 != rc2 % 2:
                continue
            r = (rc1 + rc2) // 2
            c = rc1 - r
            if 1 <= r <= n and 1 <= c <= n:
                duplicated[r, c] += 1
    ans = n * n - controlled
    for cnt in duplicated.values():
        if cnt == 1:
            ans += 1
        elif cnt == 3:
            ans += 2
        else:
            ans += 3
 
    return ans
 
 
n, m = map(int, input().split())
queens = list(tuple(map(int, input().split())) for _ in range(m))
ans = solve(n, m, queens)
print(ans)

            

        
      

G - Edit to Match

問題文

$N$ 個の文字列 $S_1,S_2,\ldots,S_N$ が与えられます。各文字列は英小文字からなります。
$k=1,2,\ldots,N$ に対し以下の問題を解いてください。
- $T=S_k$ として、 $T$ に対して以下の $2$ 種類の操作を好きな順番で好きな回数繰り返すことを考える。
  - コストを $1$ 払い、 $T$ の末尾の文字を削除する。この操作は $T$ が空文字列でない時に可能である。
  - コストを $1$ 払い、 $T$ の末尾に好きな英小文字を追加する。
- $T$ を空文字列、 $S_1,S_2,\ldots,S_{k-1}$ のいずれかと一致させるために払うコストの総和の最小値を求めよ。

制約

$1\le N\le 2\times 10^5$
$S_i$ は英小文字からなる長さ $1$ 以上の文字列
$\displaystyle \sum_{i=1}^N |S_i|\le 2\times 10^5$

解法

Trie木を知っていれば、F問題より解法はわかりやすい。

最適な操作は、操作1で末尾をいい感じのところ（あるいは空文字列）まで削って、操作2でprefixが同じ他の文字列にする、という流れになる。

複数の文字列のprefixを扱うのは、Trie木の出番。
各ノード $n$ に、「 $C_n:=$ ここから末尾への文字の追加だけを行うことで、いずれかの $S_i$ と一致させることができる最小コスト」を持たせる。

はじめはルートノード $r$ だけがあり、 $k=1,2,\ldots,N$ の順に、「 $S_k$ の答えを求めた後、Trie木に $S_k$ の情報を追加」をしていく。

長さ $L$ の文字列 $S_k$ の、 $i$ 文字目までを示すノード $n_i$ がTrie木に存在した場合、操作1で $i$ 文字になるまで削るような操作のコストは

$S_k$ を $i$ 文字まで操作1で切り詰めるコスト $L-i$
切り詰めてから操作2で他の $S_l$ にするためのコスト $C_{ni}$

これらの合計となる。 $i=0,1,...,L$ について調べ、その中の最小値が $S_k$ に対する答えとなる。

Python3