AtCoder Beginner Contest 103

AtCoder Beginner Contest 103

A - Task Scheduling Problem

• 3個のタスクがあり、それぞれに値 $A_1,A_2,A_3$ が決められている
• 最初のタスクはコスト0で完了できる
• 2番目以降の完了には、直前のタスクとの $A_i$ の差の絶対値のコストがかかる
• 全てのタスクを完了させるためのコストの最小値は？

選ぶタスクの $A_i$ を増やしたり減らしたり行ったり来たりすると、往復する分が無駄なコストとしてかかってしまうので、小さい方から徐々に増やす（または大きい方から減らす）のがよい。

間を省略すると、$A_1,A_2,A_3$ の最大値ー最小値が答えとなる。

B - String Rotation

• 文字列 $S,T$ がある
• 文字列 $S$ を「回転させる」とは、$S$ の末尾の文字を先頭に持ってくる操作を指す
  • ABCDE → EABCD
• 文字列 $S$ を回転させて、$T$ に一致させられるか調べよ

全部試す。

C - Modulo Summation

• 正整数列 $\{a_1,a_2,...,a_N\}$ がある
• 1つの正整数 $m$ に対して、$f(m)=(m \mod{a_1})+(m \mod{a_2})+...+(m\mod{a_N})$ とする
  • $X\mod{Y}$ は、$X$を$Y$で割った余り
• 上手く $m$ を選んで $f$ が取れる最大値を求めよ

ある $a_i$ で正整数を割った余りは $0$～$a_i-1$ の間である。つまり最大は $a_i-1$ である。

全ての $a_i$ について最大値 $a_i-1$ を取れるような $m$ が存在すれば、$f$ の最大値は $(a_1-1)+(a_2-1)+...+(a_N-1)$ となる。

じゃあ、そんな $m$ は存在するのか。

最大値 $a_i-1$ を得られるのは、$a_i$ の倍数から1少ない数 $m=ka_i-1$ の時である。

$m'=a_1\times a_2 \times ... \times a_N$ のように全ての $a_i$ をかけてしまえば、$m'$ は $a_1$～$a_N$ 全ての数の倍数である。

よって、$m=m' - 1$ とすることで、全ての $a_i$ に対して、最大値の $a_i-1$ が得られる。

$m$ を実際に計算する必要は無い。

D - Islands War

• 東西1列に並んだ $N$ 個の島がある
• $N-1$ 本の橋によって、隣同士の島が結ばれている
• いくつかの島で戦争が起こり、以下のような要望が $M$ 個寄せられた
  • 島 $a$ と $b$ を、その間にあるいずれかの橋を壊して、移動できないようにしてほしい
• 全ての要望を叶えるために、壊す橋の最小数はいくつか？

１      ２      ３      ４
○＝＝＝○＝＝＝○＝＝＝○

> 1と3を移動できないように
> 2と4を移動できないように

→2と3の間にある橋を壊せば、2つの要望を叶えられる
答えは1本

必要が生じるまで橋は壊さないことにして、西から順に見ていく。

ある要望 $a_i,b_i$ について、$b_i$ まで見た時に、$a_i$ 以降のどの橋も壊されてなければ、$b_i-1$ と $b_i$ の間の橋を壊す必要がある。

        ai      bi
○＝○＝○＝○＝○＝○＝○＝○
                ↑ｺｺﾏﾃﾞﾐﾀ

        ai      bi
○＝○＝○＝○  ○＝○＝○＝○
              ↑壊す必要がある

他の要望のために既に $a_i$ 以降のいずれかの橋が壊されていれば、何もしなくてよい。

        ai      bi
○＝○＝○  ○＝○＝○＝○＝○

壊す時、$a_i$～$b_i$ の間ならどの橋でもいいのだが、出来るだけ右の橋を壊した方が、他の要望の区間を多く含めるようになる。

         a       b
○＝○＝○＝○＝○＝○＝○＝○
         ~~~~~~~~
     ~~~~~~~~~~~~~~~~
             ~~~~~~~~~~~~
          ↑  ↑
          ①  ②

$b_i$ の小さい方から見ていくので、①を含み、右端がbより右にある区間は、必ず②も含んでいる。

まず各要望について「$a_m$ と要望番号 $m$」「$b_m$ と要望番号 $m$」の計 $2M$ 個の情報をリスト化し、ソートする。

ソート時、同じ島なら $b$ の方が $a$ より前に来るようにする。（$b_1$ と $a_2$ が同じ島である2つの区間は、共有する橋を持たないため）

    a1      b1
○＝○＝○＝○＝○＝○＝○＝○
            a2      b2

「保留中リスト」と「確定済みリスト」を用意し、上記のソート済みリストを順に見ていく。

$a_i$ が出てきたら、要望番号 $i$ を保留中リストに蓄積する。

$b_i$ が出てきたら、

• 要望番号 $i$ がまだ叶えられてなければ、（確定済みリストに無ければ）
  • 橋を1つ壊す
  • 保留中リストの要望を全て確定済みリストに移す
  • 保留中リストを空にする
• 要望番号 $i$ が既に叶えられていれば
  • 何もしない

以上で、壊した橋の数が答えとなる。

もっとよい実装が解説されていた。

$(b,a)$ ペアについてソートして、「最後に壊した最も東の橋 $r$」を記録しながら西から見ていく。

$a$ が $r$ より小さければ、既に要望は叶えられている。

$a$ が $r$ より大きければ要望はまだなので、橋を壊して$r=b$ に更新する。

要望番号を管理しなくても、これで十分カウントできる。

また、$b$ が同じ要望が複数ある場合、必要なのは $a$ が最も東にある1つだけなので、その辺の重複を最初のソートリスト作る時に削除すると、後半のループが減ってなお高速になる。