一番番号の小さい箱を運び出すために、上に乗っている箱を移動させます。このとき、一番番号が小さくなくともある程度小さいものに対して別処理をすることで、点数を上げていくことができます。

1356657点解法

この点数を取った方が一番多かったのではないでしょうか。愚直に一番番号の小さい箱を見つけ、その上に乗っている箱を、「番号の最小値が最も大きい山」に移動させます。

このときの実装例 (C++, 3ms) https://atcoder.jp/contests/ahc026/submissions/47298964

1373967点解法

上の解法では、一番番号の小さい箱のみに特別な処理をしました。

一番番号の小さい箱の番号を \(i\) とします。\(i\) が属する山で \(i\) の上に乗っている箱のうち、 \(i < j \leq i + 8\) となるような番号 \(j\) の箱についても特別処理をします。それ以外の番号の大きい箱について「番号の最小値が最も大きい山」に移動させるのは同じです。

上記の番号 \(j\) の箱について具体的には、\(i\) や \(j\) が属する山と、番号の大きい箱を移動させる先の山以外の \(8\) つの山を使用します。

• \(i\) が属する山を上から、\(i\) が見つかるまで探す

• その間、\(i < j \leq i + 8\) となる \(j\) があった場合、上に乗っている箱を、番号の最小値が最も大きい山に移動させ、 \(j\) の箱を、番号の最小値が \(j\) 以上な中で最小値を取るような山に移動させる。

このときの実装例 (C++, 1ms) https://atcoder.jp/contests/ahc026/submissions/47300316

1394046点解法

上記で \(i < j \leq i + 8\) としていた部分については変わらずです。\(i + 9 \leq j \leq i + t\) となる \(j\) においても、ランダムで特別処理をするようにします。このときの確率には傾斜を付けました。小さい方が採用されやすくしました。 \(t\) は \(12\) から \(17\) あたりを試しました。

この解法からは、実現できない移動を試みることがあります。なので、そう判断できるときに都度処理を止めるとよいです。

このときの実装例 (C++, 1903ms) https://atcoder.jp/contests/ahc026/submissions/47301089

1399716点解法

上の解法でランダムな部分について、貪欲にすべて採用するようなコードを追加しました。また、\(12\) から \(17\) としていたものを、\(9\) から \(30\) としました。

このときの実装例 (C++, 1613ms) https://atcoder.jp/contests/ahc026/submissions/47301498

1399810点解法

パラメータや解法の優先順位を多少変えただけです。37位となりました。

最終的な実装 (C++, 1958 ms) https://atcoder.jp/contests/ahc026/submissions/47308495

1400000点突破のために

上記以外でやりたかったこととしては、上記の1394046点解法以降で、新たに特別処理をする箱が現れたときに移動できないときに諦めて処理を止めていた部分を、既に移動させた \(j\) を別の場所に移すことで、そこに新しい箱を移動させようとしました。

しかし、コンテスト中はバグが取れませんでしたし、あまり得点は増えませんでした (もしかしたらバグってるままかもしれません)。

https://atcoder.jp/contests/ahc026/submissions/47313763

また、他の方の解法にあるように、各山をソートされた状態で持つものを組み合わせれば点数自体は1400000点は超えそうです。

追記

超えました https://atcoder.jp/contests/ahc026/submissions/47346965