ABC137-E:Coins Respawn ~負閉路検出について~

はじめに ~この記事の経緯~

 AtCoderで久々にBellman-Ford法を要求する問題が出題されました。Bellman-Ford法は蟻本でも紹介されている有名な単一始点最短経路アルゴリズムであり、負閉路の検出を行うこともできます。ところが今回扱う問題では、この負閉路検出の部分に工夫が必要です。過去にほぼ同様の問題が出題されたこともあり(D - Score Attack)、中~上級者にとっては難なく通されていました。ところがコンテスト終了後、Twitter上にそれらの提出の多く(本当に多くかは知りませんが)をhackするケースが現れ、議論が行われることになりました。本記事では、これらの議論をまとめることを目的としています。

問題

E - Coins Respawn

解法概要

 解法としては、各辺のコストをc_iからP-c_iに変えるというものです。すると、このグラフの頂点1から頂点Nまでの最短距離の-1倍が答えとなります。負の重みをもつ辺があるので、Bellman-Ford法を使います。ところで、上述のように重みを変えたグラフについて、頂点1から頂点Nのパス上に負閉路がある場合、ゲームのスコアを無限に大きくできるので、この場合は-1を出力するようにしなければいけません。

Bellman-Ford法とは?

 そもそもBellman-Ford法ってなに?という方のために簡潔に紹介をします。詳細は他の蟻本や記事に委ねることにします。
 アルゴリズムは以下のようになります。頂点数をN、辺数をMとします。また、辺u,vの距離をc_{u,v}頂点vへの現在の距離をd_vとします。

  • N回ループを回す。

    • すべての辺(u,v)について、d _ v \lt d _ u+c _ {u,v}ならば、d _ v = d _ u+c _ {u,v}とする。
    • N回目にある頂点vについて、d_vが更新された場合、負閉路が検出されたと返す。
  • d_1,\cdots,d_Nが各頂点への最短距離である。

 これで最短距離が求まることの証明は割愛しますが、負閉路検出について簡単に書いておきます。N頂点のグラフにおいて、あり得る最大の負閉路に含まれる辺の数はNです。従って、N回目にある頂点vについて更新があったかどうかを調べれば、与えられたグラフ上に負閉路が存在するかどうかを判定できます。

本題 ~頂点1から頂点Nへのパス上の負閉路検出~

 ここからが本題です。頂点1から頂点Nへのパス上の負閉路をどのように検出すればよいでしょうか。

誤解法1 普通にBellman-Ford法

 普通にBellman-Ford法すれば終わりじゃないか、と思う方がいるかもしれません。しかし、上述のBellman-Ford法をそのまま適用すると、検出したくない負閉路も検出してしまいます。次の例を見てみましょう。 f:id:sigma1113:20190811165053p:plain 頂点1がスタートで、頂点4がゴールです。この例では、頂点2と頂点3を往復する負閉路が存在しますが、今回の場合では、最終的に頂点4にたどり着ける閉路にしか興味がありません。しかし、Bellman-Fordによる通常の負閉路検出では、このような負閉路も検出してしまいます。工夫が必要です。

誤解法2 追加でN回ループを回して頂点Nが更新されたかを見る

 Twitter上で散見された誤解法のうち、最も多く見られたものです。まずこの解法の気持ちを説明します。
 元々のBellman-Ford法では、負閉路検出のために、N回目のループである頂点の最短距離が更新されたかをチェックしていました。今回知りたいのは、頂点1から頂点Nへのパス上に負閉路があるか、つまりBellman-Ford法のループを何度も行ったときに、頂点Nの最短距離が更新されることはあるか、ということです。N回目のループの際にある頂点の最短距離が更新されたとき、その影響が頂点Nに伝搬されるかどうかをチェックするには、最低であと何回ループを回せばよいでしょうか。負閉路の長さは最大Nであることから、追加でN回行えばよさそうに思えます。従って、追加でN回Bellman-Ford法によるループを回した後に頂点Nが更新されたかどうかをチェックすれば、目的を達成できそうです。

 残念ながら、この解法は誤りです。次の例を見てみましょう。 f:id:sigma1113:20190812102459p:plain この例で先に述べたアルゴリズムを用いるとどうなるでしょうか?頂点2と頂点3の間に負閉路が存在します。しかし、頂点4の最短距離は-100000ですから、たった4回のループでは当然頂点4にはこの負閉路があるという情報は伝わりません。従って、このアルゴリズムは答えとして100000を返し、無事Wrong Answerとなります。この例はMが小さいですが、Mが大きい場合にはもちろん100000回もループを回すわけにはいきません。もう少し工夫が必要ということになります。

解法1

 さて、ここから正しい解法の説明に入っていきます。誤解法2の問題点はどこにあるのでしょうか?それは、負閉路検出パートである頂点の最短距離が更新されたときに、実際に最短距離を正確に更新していることです。こうしてしまっているために、上に挙げた反例のように、辺の重みの差が極端な場合に、なかなか頂点Nの最短距離が更新されないという事態が起こってしまいます。
 そこで、頂点vに正確に最短距離に反映される代わりに「更新された」という事実のみを記録することにします。さらに、各ループ内で辺(u,v)をチェックする際に、頂点uが「更新された」という事実が記録されているなら、頂点vにも「更新された」という記録を残すことにします。頂点uの最短距離が更新されたならば、そこから伸びている辺の行き先の頂点のも、いつかは必ず更新されるという事実を伝搬させていくのです。このような伝搬を行えば、検出したい負閉路が存在する場合に、最大でもN回のループで頂点Nに「更新された」という記録をつけることができます。またそのような記録がない場合は、検出したい負閉路は存在しなかったということになります。
 以下の提出によって実装例を示します。頂点vが「更新された」という記録をnegative_vで管理しています。
Submission #6859372 - AtCoder Beginner Contest 137

解法2

 解法1と考え方はほとんど同じですが、面白いと思ったので紹介します。誤解法2では、負閉路検出パートである頂点が更新された後の正確な最短距離を反映させていました。そうではなくて、更新があった場合にその頂点の最短距離を-\inftyとします。すると、以後の更新では最短距離を-\inftyとした影響が伝搬され、結果的に解法1と同じ挙動をすることになります。頂点Nの最短距離が-\inftyであれば、検出したい負閉路が存在することになります。イメージとしては、負閉路を見つけたらその閉路だけ先に十分な回数更新を行っておく、というところでしょう。
 実装例を以下に示します。負閉路検出のために新たに配列を用意したりする必要がなく、簡潔な実装になっています。
Submission #6860850 - AtCoder Beginner Contest 137

解法3

 上の2つの解法とは異なる視点を持った解法です。現在の目的は、頂点1から頂点Nのパス上に負閉路があるかを調べるということでした。つまり、そもそも頂点1からたどり着けなかったり、頂点Nにたどり着けないような頂点には興味がありません。そこで、そのような頂点をあらかじめ削除しておくことを考えます。このためには、元のグラフの辺の向きをすべて反転させたグラフを考え、このグラフ上で頂点Nからたどり着ける頂点を列挙します。ここで列挙された頂点は、元のグラフにおいて頂点Nにたどり着ける頂点であり、それ以外の頂点からはたどり着くことができません。さらに、これらの頂点のうち頂点1からたどり着けない頂点も削除します(頂点Nにたどり着けるが、頂点1からたどり着けないような負閉路も検出してはいけないことに注意してください)。そして、この時点で残った頂点だけを見ながら通常のBellman-Ford法を行えば、検出された負閉路は頂点1から頂点Nのパス上に存在するものだけであり、目的を達成することができます。こちらは直感的にわかりやすいかもしれません。実装例はAtCoderの解説放送をご覧ください(丸投げ)。

 少し工夫が必要な負閉路の検出について紹介しました。果たして次にAtCoder上でBellman-Ford法が要求されるのはいつになることやら....。

(AOJ1635) ICPC2019 国内予選-D:計数カウンタ

想定解は結構難しいと思ってしまった。

解法

 「ある区間を選び、その区間の数字を同時に1増やす」という操作が1回であるとどういうことが起きるかを考えてみる。例えば、3つのカウンタがあって、すべてa_i\lt b_iが成り立っていても、両端の2つはたくさん押す必要があるが、真ん中の1つはほとんど押さなくてよいという状況を考えてみる。このとき、両端の2つを別々に押すよりも、3つ同時に押すことを何回か行った方が得をするということがあり得る。このとき真ん中のカウンタではMから1に戻るということが何回か起きるが、これは目標となるb_iの値を、整数jを用いてb_i+jMに置き換えることにしよう。解くべき問題は、「各カウンタiについてjをうまく選んだとき、カウンタiの値をa_iからb_i+jMにするには最小で何回の操作が必要か?」というものである。jの値としては、カウンタの数であるNまで考えれば十分である。
 ところで、1番目のカウンタが最適解において何回押されるかということはすぐにわかる(カウンタが1つのときを考えればよいから)。1番目のカウンタの状態が決まれば、1番目のカウンタのことは考えなくてよいので、その状態において2番目のカウンタを何回押すべきかも計算できる。このように考えてみると、端からdpをしたくなってくる。dp_{i,j}:「i番目のカウンタまで見て、i番目のカウンタの値をb_i+jMにするときの操作の回数の最小値」としよう。
 dp_{i,j}への遷移を考えよう。基本的には、カウンタi-1とカウンタiの、各状態における押すべき回数の差分を足し合わせていくことになる。このとき、カウンタi-1の方が押すべき回数が多いということがあり得るが、その場合はカウンタi-1を「先に押しておいた」と解釈し、ノーコストでカウンタiのときの値に遷移することで解決する。カウンタib_i+jMにするためには、そのカウンタを(b_i-a_i)+jM回押す必要がある(j=0かつb_i\lt a_iの場合は除く)。この値をc(i,j)としよう。dp_{i-1,k}からdp_{i,j}への遷移は

  • dp_{i,j} = \min(dp_{i,j},dp_{i-1,k}+c(i,j)-c(i-1,k)) \ (c(i-1,k)\lt c(i,j))
  • dp_{i,j} = \min(dp_{i,j},dp_{i-1,k}) \ (c(i-1,k)\geq c(i,j))

となる。これでは遷移がO(N)かかり、計算量は全体でO(N^3)である。ICPC国内予選なら多少待てばよい(僕のチームはこれで通した)が、AOJでは通らない。
 遷移を高速化しよう。上の遷移のほとんどは「無駄」である、つまり不必要な計算であることがわかる。例えば、j+1 \lt kであるkでは、常にc(i,j) \lt c(i-1,k)が成り立つ。つまり、dp_{i,j}への遷移はjの大きい方からj+2までの累積minを取っておけば、O(1)で行うことができる。k\lt jの方の遷移はどうだろうか。c(i,j)-c(i-1,k)を書き下すとc(i,j)-c(i-1,k) = (b_i-b_{i-1})-(a_i-a_{i-1})+(j-k)Mであり、前半2項の最小値は-2(M-1)であることを考えると、k\lt j-2では、jに遷移する際にカウンタiを単独でM回以上押すことになる。しかし、カウンタiを単独でM回押すなら、カウンタi-1をさらにM回押して損がない。つまり、k \lt j-2であるkからjへの遷移は、k=j-2,j-1からjへの遷移に勝ることがない。従って、そのようなkからの遷移は計算する必要がないことがわかった。
 以上のことより、遷移として計算すべきはk=j-2,j-1,j,j+1j+1\lt kだけで、これはそれぞれO(1)で可能であった。よって、dpの遷移を無事O(1)にすることができた。全体の計算量はO(N^2)となり、これならAOJでも間に合う。

実装

AIZU ONLINE JUDGE: Code Review
実装は標準的。

ちゃんとやると考察難易度が高いと思う。想定解で通した通したところはすごいなあ...。

(AOJ0625) JOI2015/2016本選-1:オレンジの出荷

なんかAOJ-JOIの難易度6(AOJ/AtCoder-JOI)で難しいという声があり、実際苦戦したので記事にしてみた。

問題

A - オレンジの出荷 (Oranges)
有志の方の尽力によってAtCoder上で問題が見れるようになって嬉しい。ありがとうございます。

考察・解法

 こういうのを見ると、i個目のオレンジをj個めの箱に入れたときに...みたいな感じでdpをしたくなりがち(僕だけ?)だが、それではうまくいかない。よく考えると、箱に関するコストは一定だから、箱を何個使ったかみたいな情報は必要ない。それよりも、箱に入れるオレンジの数、大きさの最大値・最小値という値がコストに関わる方が厄介である。ここで、「ひとつの箱には連続した番号のオレンジしか詰めることができない」という文言に注目しよう。これは、ある箱に詰めるオレンジの集合は区間をなすことを意味する。そしてその区間の長さ、その区間に含まれる値の最大値・最小値が問題になると言っているので、「全体をいくつかの区間を分割する」タイプのdpが相性がよさそうだ。
 dp_i:i番目のオレンジまで詰めたときのコストの最小値 とする。そして0 \leq j \leq M-1を満たすjについて、区間[i-j,i]を同じ箱に詰めると考えて遷移を行う。この遷移はjの小さい順に行えば、a,bの値を順次更新していくことができるので、iへの遷移をO(M)で行える。全体の計算量はO(NM)となり、十分高速である。

実装

Submission #4243568 - 第15回日本情報オリンピック 本選(オンライン)
実装は軽いと思う。dp2とか書いたのは試行錯誤の跡...。

ICPC2019国内予選 参加記

 皆さんこんにちは、おきもちです。2019年7月12日(金)に行われたICPC2019国内予選の参加記です。やや長いです。

結果

チームokimochiは全体4位で、無事アジア地区予選横浜大会に出場できることになった。やったね!

f:id:sigma1113:20190713110852p:plain
5完内1位でした、全体的に早かった

メンバー

  • risujiroh:なんかいろんなことを知っている。ICPC的には幾何に強いのが特長(模擬国内予選では幾何を通してくれた)。国内予選時点ではcodeforces赤だったが...。
  • idsigma:上の2人には実力は劣るのでAOJ-ICPCの400点くらいまでをできるだけ埋めて前半の問題で詰まらないようにしていた。練習では最短距離系やグリッドでなんかやるのをよくやっていた気がする。冗談で冷えたらおきもちとか言ってたらチーム名になった。

 東大B4のトップ層(ツートップ?)の2人と駒場に幽閉されたM1のチーム。3月くらいにチームを組みませんかと言われたのだが、まさかこの2人と組めるとは思っていなかったのでかなり嬉しかった。「アジア連れてってもらうか~w」と思いつつ、実力は劣るのでなんとか足を引っ張らないようについていきたいという焦りもあった。
 3月のRUPCから何回かチーム練をしてきたが、チームで総合するとそれなりにバランスが取れていて、それなりにICPC力のあるチームだと思う。分担もうまくいくようになって、チーム力が上がってきているのも感じていた。模擬国内予選がかなりうまくいって5位だったので、十分チャンスはあるねという印象だった。

当日の様子

開始前

 13:00くらいに先に会場に来て適当に何問か解く。その後risujirohが来て、kort0nを待つ。彼にPCとプリンターを持ってきてもらうことになっており、雨だったので傘を差しに駅まで迎えに行く。ところで

f:id:sigma1113:20190713112741p:plain
各駅停車に乗らないと駒場に着けない
 全員揃ったのでとりあえず準備を始める。プリンターくんをPCに接続しようとするが、プリンターくんが大学のWi-Fiを検知してくれなかった。よく考えたら市販のプリンターがそういうWi-Fiを検知しくれるわけなくないんですよね...。
 仕方がないので生協に有線を買いに行く。戻ってきてプリンターくんに接続するが、PCが認識してくれない。よく考えたらこういうのはPCにドライバーを入れる必要があるのでいろいろ探して入れる。ついに接続がうまくいき、「よかった~」とか言いながら試しにリハーサルの問題文を印刷しようとて出てきたのがこれ。
f:id:sigma1113:20190713113218j:plain
は?


「??????」じゃないんですよ、「??????」なのはこっちなんですが...。

完全におきもちになってしまった。確かにチーム名はokimochiだけどこんなところでおきもちになるとは思っていなかった。必死でググりながらコマンドプロンプトでなんかするとかを試していたが、まともな状態に至らず時間もないことから用意したプリンターくんの使用を諦める。かなしい。

仕方がないので会場の印刷機を使うことにしたのだが、手段を選ばないので、印刷機の一番近くのスペースに陣取った。一応席は割り当てられていたのだが、後ろのスペースも使ってよいとのことだったのでそうした。catsatmatと背中合わせだった。

f:id:sigma1113:20190713140309p:plain
2分くらいで書いた会場の本質情報
 その後なぜかPC上のICPC用のアカウントからkort0nのメインのアカウントのファイルが参照できることに気付いたので(ルール違反)、また必死でググりながらなんとか解決する。chmodとかいうコマンドを使ったんですが、慶應のチームでchmodなんとかみたいなチームがあるのを後で見つけて笑ってた。その後なんとか監督から競技開始の許可をもらえた。競技開始10分前だった。

コンテスト中

 まずkort0nが一瞬で問題文をpdfでUSBに保存し(駒場会場では印刷用途に限りUSBの使用が許可されていた)、すぐさまrisujirohに受け渡す(この間20秒なかったと思う)。この流れがあまりにスムーズすぎて開始早々面白かった。kort0n曰くこの流れをシミュレーションしていたらしい。
 Aをkort0nがすぐに通しFA。それと同じくらいにBの問題文を理解し、bfsするのか~と思いながら実装に入る。実装が重いと考えていたのだが、よく考えると各文字の位置を持てばマンハッタン距離で終わりということに気付きあぶね~と思いながら実装を終える。サンプルが合ったので出すと通る。沼にハマる前に気付けてよかった~。
 Dをkort0nが解けたというので実装してもらうが嘘だったので考え直してもらう。コードを印刷しに行くと言ってからなかなか帰ってこないなと思っていたのだが、テストケースも印刷していたらしく大量の紙を持って帰ってきた。なんやねん。
 実装を紙で詰めていたrisujirohがCを通す。Dも正しい解法がわかったらしく書いてもらう。その間にE以降を読む。Eは問題を読んでこれはkort0nの担当ですねとなる。Fはグラフで面白そうだけど全く分からん。Gはやりたくない。Hは問題文を理解するのもつらくて捨てっぽい。チームとしては幾何はそれなりに戦えるはずなのだが、これは無理そうですねという気持ちになった。
 Dが通ったのでrisujirohがなんとなくの方針を伝えてEをkort0nに投げる。この時点で2位だったのでEでハマらなければ大丈夫そうみたいな気持ちはあった。risujirohとFを考え始めるが、何もわからない。「FはFlowのF」ということわざがあるが、全域木でFlowなんて聞いたことがない。40分くらい2人で唸っているとkort0nがサンプルが合ったと言い出したので実行を始める。5分くらいで実行が終わって投げるとケース1が通る(ここで叫びそうになった)。サンプル2も投げると通り5完。kort0nの実装力にちょっと引いてしまった。
 かなり安心したが気を抜かずにFを考える。いろいろ3人で言い合いながら貪欲を立てたりするがサンプルに打ち砕かれる。線型代数的なアプローチも試していたのだが全然うまくいかない。実験コードはバグる。そうこうしているうちに残り10分となり、この時点で3位だったので通過を確信する。順位表を見ながら雑談をしておしまい、と思ったら突然Heno Wolrdに抜かれてさすがだなあと思った。終わった後は通過の喜びを分かち合った。

 終了後satashunからFの解法を聞く。綺麗でかなり感動したのだが、的外れなことばかりを考えていて悔しかった。こういう問題が解けるようになりたいね。
 監督の先生に挨拶しに行く(僕は元々お世話になっていたので、他の2人の紹介という感じ)。kort0nは存在が認知されていた。自腹で海外大会行ってもいいよとは言われたけどどうしようかなあ(思い出づくりになりそう)。

打ち上げ

 駒場キャンパスの近くにはOaksという定食屋があるのでそこに入った。そうしたら次々とICPCのチームが入ってきて実質ICPC打ち上げになった。他チームのトークがかなり面白かった。Gの考察が終わっていたチームがあったので聞いた。まあ考察内容的には解けてもおかしくないくらいだとは思ったけど、実装に2億時間かかりそうだった。
 ところでこれは日経コン懇親会のときも思ったのですが、risujirohはワイングラスが似合う。

まとめ

 自分のした仕事はわずかなものだったけど、横浜大会に行けることになって素直に嬉しい。このチームで5時間セットを戦えるということも嬉しい。5時間ともなると一人ひとりのやるべきことも増えてくるはずで、力をつけていきたいなあと思った。
 チームメイトの2人には本当に感謝しています。もう数か月よろしくお願いします。また、他の横浜大会に出場されるチームの方とお会いできるのを楽しみにしています。

ところで

 研究しないと...。

ABC133-F:Colorful Tree

オイラーツアーとかはともかく、この解法が思いつけないのは悔しい...。

解法

 まず、色の変更のことは忘れて、「木上の2u,v間の距離を求めよ。」というクエリに効率的に答えることについて確認する。このクエリに答えるには、u,vの最小共通祖先(LCA:Least Common Ancestor)が重要になる。木を1を根とする根付き木だと思って、d(v)を頂点vの根からの距離とする。lca(u,v)uvLCAとすれば、u,v間の距離はd(u)+d(v)-2d(lca(u,v))と書ける。つまり、u,v,lca(u,v)についての情報さえわかれば十分だということがわかる。LCAの効率的な述べ方については、ここでは省略するが、蟻本や検索をすれば情報は手に入るはず。
 色のことを思い出してみる。ある頂点vについて「色xの辺の距離をyに変えたときに、根からの距離を求めよ。」という問いに答える必要があるが、オンラインで答えるには若干の技術が必要になる(公式解説などはこれ)。ここでは、先にすべてのクエリの情報を読み込んでしまって、その上で各クエリの答えを求めることを考えてみる。まず、各頂点に「この頂点はi番目のクエリに関わり、そのクエリは色xの辺の距離をyにしたときのことを聞いている。」という記録をしておく。そして根からdfsをして、mapなどのデータ構造などで、「今見ている頂点をvとして、vに着くまでに辿った各色の辺の距離の総和と本数」を管理しておく。vに来たら、保存していたクエリについて、mapのデータを参照しながら適切な計算を行う(現在の距離の総和から、色xの距離の総和を引いて、y\times(色xの本数)を足す)。vの子uに行くときは辺(v,u)の情報をmapに追加し、uから帰ってきたら辺(v,u)の情報を破棄すれば、全体を1つのmapで処理することができ、空間計算量がO(N+Q)で済むようになる。時間計算量はO((N+Q)\log{N})である。

実装

Submission #6307254 - AtCoder Beginner Contest 133

  • LCAはいざというときのために準備しておく。それ以外の実装も量はあるが、適正帯には難しくないと思う。dfsに従って情報を入れたり捨てたりするのがポイント。
  • 構造体を書くと安心感がある。

CPSCO Session2-G:MSTX

クラスカル法あたりの考え方をちゃんとわかっているかを問われている気がしてよかった。

問題

G - MSTX

考察・解法

 最小全域木だしクラスカル法っぽく考えたい。まずa_i = 0のとき、つまりc=1の辺から優先的に使うことを考えてみる。このとき、もしc=0の辺を使うことがあるとしたら、そのような辺はxがどのような値でも最小全域木に必ず用いられる辺であることが言える。このような辺の集合をmustとする。mustに属する辺はあらかじめ繋いでおいたグラフから初めて、その他の辺の使い方がxの値によってどう変わるかを観察しよう。
 x=a_iのとき、重みがa_i以下であるc=0の辺を最小全域木に用いるかをクラスカル法で判定する。そして、そのような辺がなくなった後のグラフの連結成分の数をs_iとすると、x=a_iのときに最小全域木に使われるc=1の辺の本数はs_i-1本であることがわかる。なぜなら、ここからクラスカル法によってc=1の辺をチェックした後に繋がれる可能性のある辺はmustに属する辺だけで、これらはあらかじめ繋いでおくことにしたからである。
 a_iを昇順にsortしておけば、これを素直にシミュレーションすることができ、時間計算量O(M\log{M} + Q\log{Q})ですべてのクエリに解答できる。

実装

Submission #6249727 - CPSCO2019 Session2
クラスカル法を2回回すのがやや面倒?

AGC032-D:Rotation Sort

やっぱりAGCの問題は綺麗で良いなあ...。

解法

 Rotation操作はややこしいので、言い換えを考える。よく眺めると、右シフトは「好きな数を今の位置より右側の好きな位置に移す」と言い換えられる。左シフトも同様なので、結局

  1. 「コストAを払い、好きな数を今の位置より右側の好きな位置に移す」
  2. 「コストBを払い、好きな数を今の位置より左側の好きな位置に移す」

とい2つの操作を考えればよい。この操作ができるとき、ソートに必要なコストの最小値を求めることが求められている。

 さて、sortするのに必要な最小コスト(または操作回数)を求める場合、dpを考えると有効な場合がある。特に、小さい数字からどの(相対的な)位置に置くか?ということを決めていくdpを考えるとうまくいきそうな気がしてくる。例えば、1\sim i-1までは昇順に並んでいるとすれば、iをどの位置に置くべきかはi-1との位置関係だけを見れば十分になるというのは都合が良いだろう。従って、dpの状態として「1からiまでは昇順に並んでいる」ということを持つことにする。もちろんこれだけでは不十分である。なぜ不十分かというと、iより大きい数も含めたときに、全体としてどれくらい揃っているかということも重要だからである。ここでどういう情報を持つとよいかは難しいが、筆者は「iより手前の位置にあって、iより大きい数がj個ある」という情報を持った。まとめると

  • dp_{i,j}:1からiまでの数は昇順に並んでいて、iより左側にあってiより大きい数がj個あるような順列にするときの、操作コストの最小値」

としてdpを行うことにした。
 遷移を考えよう。まず、各数に行う操作は「左に動かす」「右に動かす」「動かさない」でいずれかを1回のみでよいのは明らかだろう。さらに、dpの遷移の際にはi-1までは昇順に並んでいるとしているので、以下のように考えてよい。

  1. i-1iより左側にあるときにiに行う操作は「左に動かす」か「動かさない」
  2. i-1iより右側にあるときにiに行う操作は「右に動かす」

つまり、i-1iの位置関係が管理できれば遷移が可能になる。そこで、l_i:元の順列\{p_i\}に関して、iより左側にありiより大きい数の個数 とする。すると、i-1からiへの遷移について、j \leq l_iのときは1に該当し、そうでないときは2に該当することがわかる。よって、以下のような遷移式が書ける。

  1. dp_{i,j} = \min(dp_{i,j},dp_{i-1,j}+B) (1 \leq j \leq l_i)
  2. dp_{i,l_i} = \min(dp_{i,l_i},dp_{i-1,j}) (1 \leq j \leq l_i)
  3. dp_{i,j-1} = \min(dp_{i,j-1},dp_{i-1,j}+A) (l_i \lt j \leq N)

初期値はdp_{0.0} = 0で他は\infty、答えはdp_{N,0}となる。

実装

Submission #6232045 - AtCoder Grand Contest 032
実装はこの問題に取り組むレベルの人なら特に難しいところはないはず。