AtCoder Grand Contest 023 - 情報妖精の競プロ日記

AtCoder Grand Contest 023に参加しました！
AGC023 旧版:
agc023.contest.atcoder.jp
AGC023 beta:
https://beta.atcoder.jp/contests/agc023/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Grand Contest 023
rated
4/28(土) 21:00 ～ 23:20 (140分)
200-500-800-1200-1700-1700 (6問)
ペナルティ: 5分

方針

A,B問題を早解きしてC問題に挑みたい
Cが正解できれば確実にレートは上がるはず

A - Zero-Sum Ranges

まず、総和が～という聞かれ方とN≦200000を見て、即座に累積和を作ります。
次に、累積和と実際の値を見てみましょう。入力例1を見てください。

	1	3	-4	2	2	-2
0	1	4	0	2	4	2

ここで、累積和が同値になっている場所が幾つかありますね？
これは、同値になっている場所をi,jとするとi+1～jまでの区間和は0になるという意味を示します。
ここで、ある値xについて累積和がxになっている場所がk個あったと仮定すると、kから2つの要素を取り出す方法はk(k-1)/2通りあります。
つまり、後は各kについて導出すれば良いので、累積和に $O(N)$ 、各k～はソートしてから数えればいいので $O(N\log N)$ で終わり、結果として $O(N\log N)$ で解けます。
……これ本当に200点か？詐欺でしょ

B - Find Symmetries

まずは、実際に構築してみると分かりやすいですね。
3x3で考えてみましょうか。

1	2	3
4	5	6
7	8	9

この3x3のマスを変えた配置を見てみましょう。

1	2	3	4	5	6	7	8	9
4	5	6	7	8	9	1	2	3
7	8	9	1	2	3	4	5	6

3	1	2	6	4	5	9	7	8
6	4	5	9	7	8	3	1	2
9	7	8	3	1	2	6	4	5

2	3	1	5	6	4	8	9	7
5	6	4	8	9	7	2	3	1
8	9	7	2	3	1	5	6	4

それぞれ、同じ色の行列に注目してください。
……気付きましたか？そう、ペアとなる数が同じなのです。
つまり、同じ色に関してはどれか1個が成立していれば全て成立するし、どれか1個が成立していなければ全て成立しません。
これで、調べる個数を $O(N^2)$ から $O(N)$ まで減らしました。
各行列は高々 $O(N^2)$ で調べられるので、結局 $O(N^3)$ で解けます。

C - Painting Machines

さて、まずは小さなテストケースで試してみましょう。
ここで、順列をする前にまずは全ての値がソート済みである時の解を求めておきましょう。後からでも順列は求められます。
試しに、N=7。
1 2 3 4 5 6
1 2 3 4 6
1 2 3 5 6
1 2 4 6
1 3 4 6
1 3 5 6
これらのパターンが存在します。
ここで、残念ながら自分はバカでかい漸化式を作りましたが、もっと簡単な解き方(解説の方法)を説明しておきましょう。
まず、k個のペイントマシンを動かした時に丁度塗り切れたとします。
その時、動かしていないペイントマシンの両隣の番号のペイントマシンは必ず動いている必要があります。
例えばN=10、k=7とすると、1 2 3 4 5 6 7のk-1箇所の候補があり、
それぞれに動いていないペイントマシンが存在してそれを順列のk+1番目以降に押しやったと考えることができます。
例えば123 4 567 8 9、とあって2と6を最後の2個にした、みたいな感じですね。
この決め方は、k-1個の候補にN-k-1個を入れるので ${}_{k-1} C_{N-k-1}$ 通りあります。
後は、動かしたペイントマシンの並び替えが $k!$ 通り、動かしてないペイントマシンの並び替えが $(N-k-1)!$ 通りあるので、
答えとしては $\sum_{i=\lfloor {N+1}/2 \rfloor}^{N-1} {}_{i-1} C_{N-i-1} \times i! \times (N-i-1)!$ を求めることになります。
ここで階乗やコンビネーションは、予め1からNまで階乗とその逆元を計算しておくことで $O(1)$ で導出できることから、
下準備に $O(N)$ 、各iに対し $O(1)$ より全体として $O(N)$ で導出できます。

結果

ooxxxx 2完(700点) 41:30(1WA)
334位パフォーマンス: 1928
レート: 1759→ 1777(+18)

感想

初っ端から問題の難易度上げすぎでしょ、配点が詐欺。
因みに、自分がC問題で作ってしまったバカでかい式も $O(N)$ な上に数式変形したら解説と同値になったので、
実装力の不足……ということを実感しました。
というか空白に埋める方法は高校数学で散々習うはずなので、数学力というものの大切さが分かる回でしたね。A問題は許さない。

1	2	3	4	5	6	7	8	9
4	5	6	7	8	9	1	2	3
7	8	9	1	2	3	4	5	6

3	1	2	6	4	5	9	7	8
6	4	5	9	7	8	3	1	2
9	7	8	3	1	2	6	4	5

2	3	1	5	6	4	8	9	7
5	6	4	8	9	7	2	3	1
8	9	7	2	3	1	5	6	4

1	2	3	4	5	6	7	8	9
4	5	6	7	8	9	1	2	3
7	8	9	1	2	3	4	5	6

3	1	2	6	4	5	9	7	8
6	4	5	9	7	8	3	1	2
9	7	8	3	1	2	6	4	5

2	3	1	5	6	4	8	9	7
5	6	4	8	9	7	2	3	1
8	9	7	2	3	1	5	6	4

1	2	3	4	5	6	7	8	9
4	5	6	7	8	9	1	2	3
7	8	9	1	2	3	4	5	6

3	1	2	6	4	5	9	7	8
6	4	5	9	7	8	3	1	2
9	7	8	3	1	2	6	4	5

2	3	1	5	6	4	8	9	7
5	6	4	8	9	7	2	3	1
8	9	7	2	3	1	5	6	4