#097https://beta.atcoder.jp/contests/arc097/tasks/arc097_c問題概要1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たときその色のボールが番号の小さい順に左から並んでいる状態にしたい。この状態を達成するための最小操作回数を求めよ。左から順番にボールを確定させていくことを考える。左に置けるのは黒1か白1のどちらかである。ここで仮に黒1を置いた場合、その次に置けるのは黒2か白1である。このように次に使えるボールは常に「黒・白それぞれの使ってないボールの中で最も若い番号のもの」ということになる。よって以下のような状態数N*NのDPが立つ。白のボールを番号wまで置いたときの最小操作回数このDPの遷移は上で述べた通り2通り(次にb+1を置くかw+1を置くか)しかない。よってあとはこの遷移のための最小操作回数が高速にわかればこの問題が解けることになる。ここでその最小操作回数は「これから置くボールより初期位置が左にあって、かつまだ使われていないボールの数」に等しい。これは実は前計算しておくとO(1)で求まる。w)の状態から次に黒(b+1)を置くとき、まだ使われていないボールというのは黒の(b+2)以上か白の(w+1)以上のボールである。これを満たすボールが自分より左に何個あるかがわかればよく、これは色ごとに累積和を取っておけばO(1)で参照することができる。色がcで番号がi以上のボールが、左からj番目までに何個出現するかこれはO(N2)で求められる。あとはO(N2)でDPを回しつつ遷移の際にこの累積和テーブルを参照して更新を行っていくと答えが求まる。数直線の原点上に人が2人いる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。