[本解説の概要]

本問題では、多くの人が貪欲アルゴリズムは思いついたようだ。 特に、本番156位の得点である13426585点が得られるような簡単な貪欲アルゴリズムを思いついた人は多いようだ。 しかし、その後の改善に苦戦した人も多いように思われる。 そこで、本解説では、この貪欲アルゴリズムのアイデアを発展させることで得られる、本番33位相当となる得点である13516495点を得るようなアルゴリズムを紹介する。 このアルゴリズムのアイデア自体は、eijirouさんのAHC015のユーザー解説から得た。

[準備]

まずは、本番156位の得点が得られる貪欲アルゴリズムを紹介する。 詳しくは、k_k_pyrhonさんのユーザー解説を見ると良いだろう。 以下に簡単にアルゴリズムを示す。今後、ただ単に貪欲アルゴリズムといった時には、このアルゴリズムを指すことにする。

\(i = 0, \dots, 464\)として次の処理を繰り返す。

　　\(i\)が書かれたボールの位置を\((x, y)\)としたとき、\((x - 1, y)\)と\((x - 1, y - 1)\)に置かれた2つボールに書かれた数字の内大きい方を\(j\)として、\(j > i\)ならば、\(j\)が書かれたボールと\(i\)が書かれたボールをswapする。

[本番33位相当のアルゴリズム]

上の貪欲アルゴリズムでは、\(b_{x - 1, y} > b_{x, y}\)かつ\(b_{x - 1, y - 1} > b_{x, y}\)のとき、\(b_{x - 1, y}\)と\(b_{x - 1, y - 1}\)の内大きい方とswapしているが、この部分を改良する。 \(b_{x - 1, y}\)と\(b_{x - 1, y - 1}\)のどちらとswapする方が良いかを決めるのに、両方試して、操作回数が少なくなるような方とswapしたい。 ただ、試すのを再帰的にやっていくのでは、TLEするのは明白である。 そこで、試す部分では、貪欲アルゴリズムを使用することにする。 以下に簡単にアルゴリズムを示す。

\(i = 0, \dots, 464\)として次の処理を繰り返す。

　REPEAT:

　　 \(i\)が書かれたボールの位置を\((x, y)\)とする。

　　 IF \(b_{x - 1, y} > b_{x, y}\)かつ\(b_{x - 1, y - 1} > b_{x, y}\):

　　　　\((x - 1, y)\)と\((x - 1, y - 1)\)のどちらか一方に置かれたボールとswapした場合の2パターンについて貪欲アルゴリズムでシミュレーションして、結果的に操作回数が少なくなる方のボールと\(i\)が書かれたボールをswapする。

　　 ELSE:

　　　　\((x - 1, y)\)と\((x - 1, y - 1)\)に置かれた2つボールに書かれた数字の内大きい方を\(j\)として、\(j > i\)ならば、\(j\)が書かれたボールと\(i\)が書かれたボールをswapする。\(j < i\)ならば、repeat文をbreakする。

[コメント]

あまり綺麗なコードではないが、以下が実装例となる。なお、実行時間は50ms程度で終わるようだ。

実装例: https://atcoder.jp/contests/ahc021/submissions/42968021

わかりにくところなどのコメントがあったら、Twitterで@otera1999にメンションしていただけると嬉しい。