AtCoder Grand Contest 023
Updated:
レーティングは上がったけど、とても悔しいミスが出てしまいました。 制約は正しく読んで配列の大きさを取る のをいつもいつも心がけないといけません。馬鹿馬鹿しいと思うかもしれないけど、自分のためにはっきり明示的に書いておこうと思う。
- $N \leq 10^5$ のときは
int A[100010]; - $N \leq 2 \times 10^5$ のときは
int A[200010]; - $N \leq 10^6$ のときは
int A[1000010];
Source codes
Solutions
A - Zero-Sum Ranges
$S[i] = \sum_{k \leq i} A[k]$ とする。$\sum_{j < k \leq i} A[k] = S[i] - S[j]$ であるから、 $S[i] = S[j]$ かつ $0 \leq j < i < N$ なる $(i, j)$ の組を数えればよろしい。そこで map<ll, int> M; で $S[i]$ たちの数をカウントする。カウントが $1$ 以上のカウント $c$ に対し ans += c * (c-1) / 2; とする。ただし便宜上 $S[-1] = 0$ をストッパーとして持っておくべきなので、最初に M[0] = 1; としておく。
ポイント
気をつけるべき点が多く、 200 点にしては難しい。 ARC だと 300 点か 400 点が妥当だ。他の問題との兼ね合いでこの点数になったのだろうと思う。
B - Find Symmetries
$A, B \in \mathbb{Z}/N\mathbb{Z}$ に対し、 $(A, B)$ が条件を条件を充たすことは $(A + 1, B + 1)$ が条件を充たすことと同値である。したがって、探索をする際は $(A, 0)$ の形のものを調べれば十分である。すなわち $(A, 0)$ が条件を充たすなら任意の $i \in \mathbb{Z}/N\mathbb{Z}$ に対し $(A + i, i)$ が条件を充たすので $N$ 個の組が見つかったことになるし、そうでないならスルーすれば良い。答えは必ず $N$ の倍数になる。
実装としては、まず $T[i] = \sum_{j} S[j][i]$ で縦読みを持っておく。$k = 0, \dots, N-1$ に対し以下のことをする。
- 任意の $i$ に対し、 $S[(i + k)\%N] = T[i]$ で一致判定してカウンタを進める。
- 全ての $i$ に対し
T[i] = T[i].substr(1, N - 1) + T[i].substr(0, 1);とする。
これで、カウンタの $N$ 倍を出力する。
ポイント
「$(A, B)$ が条件を条件を充たすことは $(A + 1, B + 1)$ が条件を充たすことと同値である」がすぐに思いついたのでスムーズにクリアできた。
C - Painting Machines
$1$-indexed とする。置換 $\tau \in \mathfrak{S}_{N-1}$ の逆変換を $\sigma$ とする。問題文の操作を $\tau$ に対して行った操作は、 $\sigma$ の側からすると次のように特徴付けられる。すなわち、最終的な得点は、 \[ \max_{0 \leq i \leq N-1} \min(\sigma(i), \sigma(i + 1)) \] である。ただし $\sigma(0) = \sigma(N) = \infty$ とみなす。
$S[i] = \sigma(i)$ とする長さ $N-1$ の配列をイメージすると、次のことがわかる：得点が $A$ 点以下であるような条件は、長さ $N-1$ の配列 $S$ に $A + 1$ 以上 $N - 1$ 以下の数字を隣合わないように並べることが必要十分条件である。ただし端にもおいてはいけない。すると得点が $A$ 点以下であるような場合の数は
\[
I[A] = \begin{pmatrix} N - 2 - (N - 1 - A) \\ N - 1 - A \end{pmatrix} (N - 1 - A)! A!
\]
である。この部分を詳しく解説すると以下の通り： $A + 1$ 以上 $N - 1$ 以下の数字は全部で $N - 1 - A$ 個ある。「端にも置かない、隣に置かない」という条件を (置く, 置かない) のペアをひとまとめにして考える。最初のマスは「置かない」なので、事実上長さ $N - 2$ の配列に (置く, 置かない) の部分を $N - 1 - A$ 個見出す。ことになる。これは $N - 2 - (N - 1 - A)$ 個の横に並んだ石のうち $N - 1 - A$ 個を (置く, 置かない) に変換し、残りを (置かない) に変換する場合の数に等しい。階乗のところは実際に数字を置くのでこれがつく。
あとは求めるもの $X$ は \[ X = \sum_{1 \leq A \leq N-1} A (I[A] - I[A - 1]) \] で求まる。
ポイント
とにかくまず定跡である 置換の問題は逆変換で捉え直す を 100 分くらい忘れていたから全く救いようがない。以下は、同じ定跡を使う問題である：
- AtCoder Regular Contest 095 の F - Permutation Tree
- AtCoder Grand Contest 008 の D - K-th K (正確にはこれは置換ではないが $f(i) = x_i$ の逆写像 $f^{-1}$ が定義でき、これを考察すると答えにたどり着く)
最後は制約ミスとか笑えない。猛省するしかない。
$N \leq 10^5, 2 \times 10^5, 10^6$ は全部違う。配列外参照するので気をつけられたい。 $N \leq 10^6$ だと相当シンプルな実装が求められている。
D - Go Home
ポイント
E - Inversions
ポイント
F - 01 on Tree
ポイント
Others
いやあやってしまったああああ。制約読み間違いで 1 問落としてしまった。プログラム書き始めたのがすでに深い時間帯だったので仕方ないのだろうか。制約ミスさえなければ順位が 40 くらい上がっていた…そう 0 を 1 個追加するだけだったのに。いやあああああああああああ。考えようによっては今までの AtCoder で参加したコンテストでで一番くだらないミスだと思う。