問題一覧 > 通常問題

No.2759 Take Pictures, Elements?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 : matcharate12matcharate12 / テスター : 👑 binapbinap aplysiaSheepaplysiaSheep
1 ProblemId : 7056 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-17 11:43:59
Story
今日は修学旅行。ラテ君は何やら高級そうな古い一眼レフのカメラを持ってきました。
しかしこのカメラはかなり撮影範囲が狭いです。ですが青春をつくり出すために、親友は絶対に写したいです。
面倒ですが、親友一人一人を撮影するためには労力を惜しまないので、頑張って撮影することにしました。

問題文

$N$ 個の箱 $A$ があり、左から $i$ 番目の箱を箱 $i$ と呼び、箱 $i$ の中身の要素を $A_i$ と呼ぶことにします。またこれらの箱のうちいずれか $1$ つを参照する機械があり、今機械は箱 $1$ を指しています。
この機械は(あるなら)右隣、もしくは(あるなら)左隣に機械を移動することができます。また機械には箱の中身を撮影する機構が備えられています。

厳密には、ラテ君は次のいずれかの操作を独立に行うことができます。

  • $1\le i\le N$ に対し、次のうちのいずれか一つを選び、操作を行うかどうか決める。行うならコスト $1$ かかり、行わない場合コストはかからない。
    • $2\le i\le N$ のとき、箱 $i-1$ に移動する。
    • $1\le i\le N-1$ のとき、箱 $i+1$ に移動する。
  • 機械が箱 $x$ を参照しているとき、箱 $x$ の要素を撮影する。このときコストはかからない。

    • 今から上の操作を繰り返し行うことで $Q$ 個の要素 $B_1,B_2,\dots,B_Q$ を、機械を用いて撮影したいと思っています(本問題の制約上、機械を移動させることですべての要素を撮影できることが保証されます)。
    ただし $1$ 回操作をした後、その機械の参照位置は引き継がれるものとします。詳しくは入出力例をご覧ください。

    $B_1,B_2,\dots,B_Q$ をこの順で撮影するために、要するコストの和として考えられる最小値はいくつになりますか？

    入力・制約

    $N\ Q$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_Q$

    • $1\le N\le 10^3$
    • $1\le Q\le 10^3$
    • $1\le A_i,B_j\le 10^9$
    • すべての $1\le j\le Q$ に対して $B_j=A_k$ なる $k$ が(少なくとも一つ)存在する
    • 入力はすべて整数

    出力

    答えを出力してください。

    サンプル

    サンプル1
    入力
    5 4
3 7 1 9 2
1 2 3 7
    出力
    9

    • $1$ を映すために箱 $1$ から $2$ 回だけ右に動かし、撮影します。要するコストは $2$ であり、現在の参照位置は箱 $3$ です。
    • $2$ を映すために箱 $3$ から $2$ 回だけ右に動かし、撮影します。要するコストは $2$ であり、現在の参照位置は箱 $5$ です。
    • $3$ を映すために箱 $5$ から $4$ 回だけ左に動かし、撮影します。要するコストは $4$ であり、現在の参照位置は箱 $1$ です。
    • $7$ を映すために箱 $1$ から $1$ 回だけ右に動かし、撮影します。要するコストは $1$ です。
    この操作を行うとき、コストの和は $2+2+4+1=9$ となります。和が $8$ 以下になるように操作をすることはできません。

    サンプル2
    入力
    3 5
7 1 10
7 7 7 7 7
    出力
    0

    移動を全くせずとも、すべての要素を撮影できる場合があります。

    サンプル3
    入力
    3 2
1 1 2
2 1
    出力
    3
    $A_i,B_i$ ともに必ずしも相異なるとは限らないことに注意してください。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。