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

AtCoder Grand Contest 024に参加しました！
AGC024 旧版:
agc024.contest.atcoder.jp
AGC024 beta:
https://beta.atcoder.jp/contests/agc024/beta.atcoder.jp

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

要項

AtCoder Grand Contest 024
rated
5/21(日) 21:00 ～ 23:10 (130分)
300-500-700-1100-1200-2300 (6問)
ペナルティ: 5分

方針

DEGwer回なので、3完速解きになると思われる。
とにかく速く

A - Fairness

まず、こういう時は実際に実験してみるべきです。
制約条件から、Kが大きいのでシミュレーションではなく何かしらの数学的解法があると考えられます。
そこで、操作をn回行ったときのそれぞれの持っている値を $A_n$ , $B_n$ , $C_n$ と置きます。
この時、求めたい値は $A_K - B_K$ です。
ここで、 $A_{n+1} = B_n + C_n$ であり、 $B_{n+1} = A_n + C_n$ であることを考えると、 $A_{n+1} - B_{n+1} = B_n + C_n - A_n - C_n = B_n - A_n = -(A_n - B_n)$ となります。
ということは、 $A_n - B_n$ は符号を毎回変えるだけで、値の絶対値は不変です。
後はKを2で割った値を見て、符号がどっちになるかだけ判定すれば良いです。
こういう問題は高校数学でも出てくるので、シミュレーション系は漸化式を書く！と徹底すれば良さそうですね。

B - Backfront

まず、どう考えてもN回操作すれば揃う(Nから順に先頭に挿入すれば良い)ので、答えはN以下であることが分かります。
勿論、もっと操作回数を減らす方法があるはずです。
例えば、1 3 2 4という数列を考えると、4を動かす必要はありません。
また、2を取り除くことによって3も動かす必要が無くなります。
言い換えると、今 $i < j$ において $P_i + 1 = P_j$ ならば、 $P_{i+1}$ から $P_{j-1}$ までの数を動かせば $P_i$ と $P_j$ は隣り合うのでこの2つを動かす必要が無くなります。
ということは、このような関係をなるべく長く続けるように動かす数を選択すれば良いことになります。
ここで、 $X_{P_i}$ を $P_i$ が何個連続して上のような関係を作れるかであると定義します。
例えば3 2 5 1 4 6ならば3->4、5->6の関係があるので $X$ を1 1 1 2 1 2と置くことができます。
さて、後は $X$ をどうやって求めるか考えます。
ここで、3->4が作れる場合というのは、左から順に見ていったとき、4を見た時点で既に3があれば作ることができると言えます。
また、 $X_3$ の長さが与えられた時、 $X_4$ は $X_3 + 1$ になります。
これはDPを用いて解くことができます。
即ち、最初は $X_i$ を0にしておきます。
そして、左から順に $X_{P_i} = X_{P_i - 1} + 1$ として求めていきます。
これにより、未発見ならば1に、既に発見済みならば発見済みの値+1の長さになるので、上の条件を満たすことができます。
このような問題はLIS(最長部分増加列)に近く、こちらもDPで解くことができるので、数列問題でかつ左側の条件のみが大事/右側の条件のみが大事といった場合は漸化式を作れないか試みてみましょう。
計算量は $O(N)$ です。

C - Sequence Growing Easy

まず、条件から $A_{i + 1} \leq A_i + 1$ です。これが成り立たなければ作れません。
また、 $X_1$ は操作できないので、 $A_1$ が0でない時も $X$ は作れません。
ここで、 $A_{i+1} = A_i + 1$ ならば、先に $X_i$ を作ってから $X_{i+1}$ を作れば良いです。
そうでない時はどうなるでしょう。
この時は、前の値を利用することはできないので、別に作る必要があります。
例えば、0 1 1 0 1 2 2 1 2という数列を考えます。
この時、後ろから操作すると数字を確定させられるので、そのようにして考えてみましょう。
これは、次のような操作で実現できると考えられます。
0 0 0 0 0 0 0 1 2 2回の操作
0 0 0 0 0 1 2 0 0 2回の操作
0 0 0 0 1 2 0 0 0 2回の操作
0 0 1 0 0 0 0 0 0 1回の操作
0 1 0 0 0 0 0 0 0 1回の操作
この順に操作すると、最終的に求めたい数列になります。
この操作方法は、次のように説明できます。

$A_{i+1} > A_i + 1$ の時は不可能なので-1を出力する
$A_{i+1} = A_i + 1$ の時は1回操作する
$A_{i+1} < A_i + 1$ の時は $A_{i+1}$ 回操作する

ということは、左から順に求めていけば計算量 $O(N)$ で導出することができます。
なお、答えは最大で $(N/2)^2$ なので64bit型の整数を使っておいた方が良いと思います。

結果

oooxxx 3完(1500点) 47:29(2WA)
364位パフォーマンス: 1935
レート: 1794→ 1810(+16)

感想

やはり早解きだが、B問題のコンテスト中の考察が遅れたのは反省ですね。
また、D問題はサンプルと実験で解ける問題、E問題は見りゃ分かるようにDPなので、計算方法が分かっていて実装できないのはまずいなー。
ただまぁ、配点が優しくない(C問題まで早解きだとPerf:2200なので黄色に上がれない、D問題からは1100点問題と青色にとっては無理ゲーだった)ので、これは流石にどうしようもないかなと。
今回は考察問題としては良問でアルゴリズム知識より数学的考察力を要求しているので、水色コーダーとかにはおススメできる問題セットだったかなと思いますね。