Codeforces Round 719 (Div. 3) C – Not Adjacent Matrix / D – Same Differences を解いた記録
C – Not Adjacent Matrix
問題の概要
\(1\) から \(n^{2}\) までの整数をちょうど1つずつ使って \(n \times n\) の行列を作りたい．
ただし，行列中で隣接している2つの数 \(a, b\) は \(|a-b| \geq 2\) を満たさなければならない．
そのような行列を作れる場合は一例を示せ．作れない場合はその旨を報告せよ．
制約
- \(1 \leq n \leq 100\)
- 入力はすべて整数
解法
\(n = 2\) のときはどう頑張っても行列を作れません．そうでない場合は，例えば
\(a_{i, (i+j) \bmod n} = i+j \times n\) （ただし \(i, j, a_{i, j}\) は0-indexed ）とするとACできます．
実装例
D – Same Differences
問題の概要
要素数 \(n\) の数列 \(a = \{a_{1}, a_{2}, \dots, a_{n}\}\) が与えられる．
\(i < j\) かつ \(a_{j} – a_{i} = j – i\) を満たす組 \((i, j)\) の個数を求めよ．
制約
- \(1 \leq n \leq 2 \times 10^{5}\)
- \(1 \leq a_{i} \leq n\)
- 入力はすべて整数
解法
式 \(a_{j} – a_{i} = j – i\) を変形すると， \(a_{j} – j = a_{i} – i\) となります．
よって， \(b_{i} = a_{i} – i\) としてstd::mapなどを用いて \(i < j\) かつ \(b_{i} = b_{j}\)
を満たすような組 \((i, j)\) の個数を数えればよいです．