【考え方】

• 大域的には、小さい番号のボールを上方向に、大きい番号のボールを下方向に動かしたい
• この意味では横移動はあまり意味ない（残り少ない場面など、状況を正確に把握できている場面以外では使うべきではない）
• 小さい番号のボールの方が行き先に関する制約が強い（たとえば \(0\) 番のボールは一番上に置くしかない）
• 小さい番号のボールから昇順に決めるのが良さそう
• 各ボールについて、各ステップで上方向に動かす方法は \(2\) 通りずつぐらいあるが、なるべく大きい番号のボールを下に落としたい
• 毎回貪欲に大きい番号を選ぶ手もあるが、もう少し先まで考えることができる
• そのボールを一番上までもっていく一連の操作の中で、全体として大きな番号のボールがある場所を通りたい
• これは DP で更新できる

【方針】

上の「考え方」を踏まえて、次のようにした。

• 入れ替えは上下のみにする
• 小さい番号のボールから昇順に決める
• 各ボールについて、確定位置（右上と左上が確定している）まで動かす方法がいくつかあるが、その中で最も評価が高いものを選ぶ
• イメージ的には、なるべく大きい番号のボールの上を通るものを高評価にしている（詳細は後述）
• 逐次更新はなしで、パラメータを変えて試して一番良い結果を選んでいる

【評価関数】

• 「なるべく大きい番号のボールを下方向に動かしたい」というのを数式化する

• 単純にボールの番号をそのまま評価として使う手もある

• \(i\) 番のボールの適正位置（上から順に配置した場合の列数）は \(\sqrt{2i}\) ぐらいなので、番号を \(0.5\) 乗する手もある

• 本解法では、その指数を \(0.4\)～\(1.1\) ぐらいまで適当に試して最も良いものを選ぶこととした

• 指数固定でも良いが、初期指数と最終指数をパラメータに持って、その間を（見るボールの番号の平方根に関して）線形に動かした

• 具体的には、評価関数は、通る道にある玉の番号を \(a_i\) とすると \(\displaystyle \frac{ \sum {a_i} ^ e}{l}\)

• \(e\) は上で書いた指数、 \(l\) は道の長さ（交換回数）

提出コード（PyPy3）