AtCoder Beginner Contest 140 D～F問題メモ

AtCoder Beginner Contest 140

D - Face Produces Unhappiness

• 東西一列に $N$ 人が並ぶ
• 各人の向いている方向は長さ $N$ の文字列 $S$ によって与えられる
  • 西から $i$ 番目の人は、$S$ の $i$ 番目が L なら西を、R なら東を向いている
• 以下の操作を $K$ 回まで行える
  • 好きな $1 \le l \le r \le N$ を選び、西から $l,l+1,...,r$ 番目の人を180度回転させる
• 各人は「目の前の人が自分と同じ方向を向いている」なら幸福である
• 操作後の幸福な人数の最大値を求めよ
  • 左右端で目の前に人がいない人は数えない
• $1 \le N,K \le 10^5$

オセロの石を使った問題でもそうだが、状態が2値で、同じ色/方向の連続が重要な問題において、「区間を反転させる」操作は「境界を最大2つ無くす」操作として捉えられる。

今回の問題も、$S$ を同じ文字の連続毎に区切って

                LLLRRRRLLRLRR
                ↓
                LLL RRRR LL R L RR
Are you happy?  xoo ooox xo x x ox

Happiness is Mandatory. Citizen, are you happy? 
                ooo oooo oo o o oo

グループをまたいで幸福な人の数に影響し合ったりしないので、独立に考えてよい。各グループ、先頭以外の全員が、そのグループにおける幸福な人となる。

なので、グループに1人ずつ幸福で無い人がいるので、この時に幸福な人の数は $N-グループ数$ となる。

これを増やすには、グループ数を減らすことがいいし、逆にどこでグループを減らしても変わらない。

1回操作を行う毎に、最大2つまでグループ数を減らせる。（当然だが）1つより少なくはできない。

LLLRRRRLL R L RR
↓ ~~~~
LLLLLLLLL R L RR

よって、$N-\max(1, 初期のグループ数 - 2K)$ が答えとなる。

E - Second Sum

• $\{1,2,3,...,N\}$ の順列 $\{P_1,P_2,...,P_N\}$ が与えられる
• 全ての長さ2以上の区間について、その中で2番目に大きい数を求め、その総和を答えよ
• つまり、区間 $[L,R]$ で2番目に大きい数を $X_{L,R}$ として、$\displaystyle \sum^{N-1}_{L=1}\sum^{N}_{R=L+1}X_{L,R}$ を答えよ
• $2 \le N \le 10^5$

C++ のsetを使うことが想定解の問題は、Pythonではそれに値するデータ構造が無く、自力実装しても遅いため、なかなか厳しい。

• set - cpprefjp C++日本語リファレンス

setとは要素を昇順に保ったまま追加・削除を行えるデータ構造で、「ある値を追加するとしたらその直前の値は何か」も $O(\log{N})$ で求められる。

Pythonでは、bisectで二分探索により何番目に追加できるかは求められるものの、値を挿入するには $O(N)$ かかる。

一応、ごり押しで一度に2要素を管理するセグ木を工夫すれば、PyPyで通ったので、その解法をメモ。

まず、答えを求めるのに必要な情報を考える。

区間を主軸に考えるよりも、各 $P_i$ に注目して「その数が何組の $L,R$ で $X_{L,R}$ になるか」を考える。

自分より左/右に2つ以上、自分より大きな数があると、もうその数はXになり得ない。 「自分より左に1個、右に0個」と「左に0個、右に1個」に分けるとよさそう。

それには、「左にある自分より大きい数のindex」「右にある自分より大きい数のindex」を得たい。

直近のindexだけではそれを越えた範囲がわからないので、直近と、その次の2つまでのindexが分かればよい。

8  2  7  3  ④  5  6  1
|<----|<----｜
            ｜->|-->|

   ~~~~     ~~         左に1個、右に0個の時に、左右端になり得る範囲
     2  ×  1

         ~~~~~  ~~     左に0個、右に1個の時に、左右端になり得る範囲
            2 × 1

2x1 + 2x1 = 4 が、4がXになる区間の数

それ以上左/右に大きい数が無い時は、1つ範囲外のindex（-1 と 8）で埋めておく。これは後の計算で楽になる。

          i   0  1  2  3  4  5  6  7
              8  2  7  3  4  5  6  1
------------------------------------
左1st index  -1  0  0  2  2  2  2  6  (x_i)
左2nd index  -1 -1 -1  0  0  0  0  5  (w_i)

右1st index   8  2  8  4  5  6  8  8  (y_i)
左2nd index   8  3  8  5  6  8  8  8  (z_i)

こうすると、各 $i$ につき、$P_i \times ((x_i - w_i)(y_i-i) + (i-x_i)(z_i-y_i))$ を求め、合計すると答えとなる。

左,右のそれぞれから、直近2要素のindexを管理するセグメント木を構築する。

説明のため数字を変更して、$P$ を $\{0,1,2,...,N-1\}$ の順列とし、添え字も $\{P_0,P_1,...,P_{N-1}\}$ とする。

左のindexを求めるなら、全要素 [-1, -1] で初期化し、$P_0$ から順に以下を処理する。

• 既に左に出てきた $(P_i+1)～N-1$ の要素のindexの内、最大の2つを得る(get(Pi+1, N))
• $P_i$ 番目の要素に対して $i$ で最大値を更新する(update(Pi, i))

P = {2,0,3,1}

          [0,4)
          [-1,-1]
        ／       ＼
   [0,2)           [2,4)
   [-1,-1]         [-1,-1]
  ／   ＼         ／   ＼
[0,1)   [1,2)   [2,3)   [3,4)
[-1,-1] [-1,-1] [-1,-1] [-1,-1]


i=0, Pi=2
get(3,4) = [-1, -1]
update(2,0)

          [ 0,-1]
        ／       ＼
   [-1,-1]         [ 0,-1]
  ／   ＼         ／   ＼
[-1,-1] [-1,-1] [ 0,-1] [-1,-1]

i=1, Pi=0
get(1,4) = [0,-1]
update(0,1)

          [ 1, 0]
        ／       ＼
   [ 1,-1]         [ 0,-1]
  ／   ＼         ／   ＼
[ 1,-1] [-1,-1] [ 0,-1] [-1,-1]

i=2, Pi=3
get(4,4) = [-1,-1]
update(3,2)

          [ 2, 1]
        ／       ＼
   [ 1,-1]         [ 2, 0]
  ／   ＼         ／   ＼
[ 1,-1] [-1,-1] [ 0,-1] [2,-1]

i=3, Pi=1
get(2,4) = [ 2, 0]
update(1,3)

          [ 3, 2]
        ／       ＼
   [ 3, 1]         [ 2, 0]
  ／   ＼         ／   ＼
[ 1,-1] [ 3,-1] [ 0,-1] [2,-1]

こうやってget()で順に得た2つの数が、それぞれ左の1st,2nd indexとなっている。

          i   0  1  2  3
              2  0  3  1
------------------------
左1st index  -1  0 -1  2
左2nd index  -1 -1 -1  0

同じことを右から、今度は最小の2要素を保ちつつ求めると、右側の自分より大きい数のindexがわかる。

C++ のstd::setを用いる問題は、たとえば この問題（ネタバレ注意）なんかもそうだが、setを使えないPythonでは「次に見るべきindexを保持して、何らかの順番で処理する上でスキップできるとわかったindexは張り替える」ことで、高速に実装できるケースがある。

各 $i$ につき、「暫定、自分より大きな左/右にある直近の数のindex」をリストで保持すると、2つ目の自分より大きな数のindexは、リストを2回辿ればよい。

    i   0  1  2  3  4  5  6  7
        8  2  7  3  4  5  6  1
------------------------------
左1st  -1  0  0  2  2  2  2  6
              ↖___／

4にとって、左1st indexは2, 左2nd indexは0

ただし、よく見るとたとえば $P_i=1$ にとっては正しく成り立っていない。 これは上記の左1stリストが最終更新済みのものだからで、実際は $P_i$ の小さい方から順に更新しながら求めていくことで、正しく求まるようになる。

左と右を同時に求める。
まず、リストをすぐ左/右のindexで初期化する。
範囲外の値に対応するため、便宜的に末尾に-1/8を2つずつ付け足しておく

  i   0  1  2  3  4  5  6  7   (8  9 = -1)
  P   8  2  7  3  4  5  6  1
------------------------------------
  L  -1  0  1  2  3  4  5  6   -1 -1
  R   1  2  3  4  5  6  7  8    8  8

i=7, Pi=1
左1st = L[7]    = 6
左2nd = L[L[7]] = 5
右1st = R[7]    = 8
右2nd = R[R[7]] = 8

Piの小さい順に処理しているため、次のループ以降に処理される数字にとっては、
・Piより右の要素にとって、Piはもはや大きい要素では無くなる = Lにおいてスキップしてよい
・Piより左の要素にとって、Piはもはや大きい要素では無くなる = Rにおいてスキップしてよい

これを表現するため、
  L[R[7]] = L[7]
  R[L[7]] = R[7]  で更新する

  L  -1  0  1  2  3  4  5  6   ⑥ -1
  R   1  2  3  4  5  6 ⑧  8    8  8

以下、同様に処理する

i=1, Pi=2
左1st = L[1]    = 0
左2nd = L[L[1]] = -1
右1st = R[1]    = 2
右2nd = R[R[1]] = 3
  L  -1  0 ⓪  2  3  4  5  6    6 -1
  R  ②  2  3  4  5  6  8  8    8  8

i=3, Pi=3
左1st = L[3]    = 2
左2nd = L[L[1]] = 0
右1st = R[1]    = 4
右2nd = R[R[1]] = 5
  L  -1  0  0  2 ②  4  5  6    6 -1
  R   2  2 ④  4  5  6  8  8    8  8

...

これで左右の1st,2nd indexが求まる。

F - Many Slimes

• スライムが1匹いる
• スライムには「体力」があり、時刻 $0$ の体力を好きな整数値に決められる
• 時刻 $1$ から1秒ごとにスライムは増殖する
  • 各スライムは、自分の体力値未満の、好きな体力値を持つスライムを1秒ごとに1匹、生み出せる
  • 他のスライムに生み出されたスライムも、次の1秒以降、増殖する
  • 生み出す側のスライムの体力は、それによって増えたり減ったりしない
• 今から $N$ 秒後、スライムは $2^N$ 匹になる
• 長さ $2^N$ の整数の集合 $S$ が与えられる
• 増殖させるスライムの体力を上手く決めることで、$N$ 秒後のスライムの体力の集合を $S$ に一致させられるか、判定せよ
• $1 \le N \le 18$

$S$ で最大の要素を、最初のスライムにする。

何らかの基準を決めて貪欲に、体力の大きい順に割り振っていって最後まで矛盾無く決まるか調べることを考える。

N=3
t   0   1   2   3
   ○→○→○→○
    |   `----→○
    |----→○→○
    `--------→○
    
S = {4, 3, 3, 3, 2, 2, 2, 1}
↓
t   0   1   2   3
   ４→３→２→１
    |   `----→２
    |----→３→２
    `--------→３

早めに生まれた子にはそれから沢山の子を生んでもらわにゃならんので、体力は大きく保った方が良さそうだが、単純に時刻で埋めていくと、同じ数字が多くある時に矛盾する。

S = {4, 3, 3, 3, 2, 2, 2, 1}
t   0   1   2   3
   ４→３→３→○
    |   `----→○
    |----→３→○
    `--------→○

体力の大きなスライムは、より体力の大きなスライムからしか生まれないので、親が大きい方から当てはめていく？ しかし、それでは今度は下の方に同じ数字が沢山ある時に矛盾する。

S = {4, 3, 2, 2, 1, 1, 1, 1}
t   0   1   2   3
   ４→３→○→○
    |   `----→○
    |----→２→○
    `--------→２
↓
   ４→３→１→１
    |   `----→１
    |----→２→１
    `--------→２

時刻が早い方から割り当てていく考え方で基本はよくて、ただし同じ体力のスライムの更新はまとめて同時に行うようにする。

スライム毎に「次にそのスライムが子を生める時刻」を優先付きキューに入れる。

体力が大きいスライムから順に○への割り当てを確定していく（時刻が重要であって、同時刻ならどの○か、というのは特に区別しなくて良い）。

同じ体力のスライムが何匹いるかはあらかじめ数えておき、優先キューへ突っ込むのは、同体力のスライムの割り当てを全て確定し終えた後とする。

どこかの体力のスライムで、優先キューにそのスライムを生めるスライムが残ってない、という状況になれば不可能。最後まで行けば可能。

S = {4, 3, 3, 3, 2, 2, 2, 2}

s = 4
t   0   1   2   3    優先キュー(時刻)
   ４→○→○→○    [0]
    |   `----→○
    |----→○→○
    `--------→○
s = 3 x 3
t   0   1   2   3    [1]  1匹目を生んだ直後
   ４→３→○→○    [2]  2匹目を生んだ直後
    |   `----→○    [ ]  3匹目を生んだら、時刻的にもう生めないので除外
    |----→３→○    [1, 2]  体力3のスライムが子を埋める時刻をまとめて入れる
    `--------→３    
s = 2 x 4
t   0   1   2   3    [2, 2]  1匹目を生んだ直後
   ４→３→２→○    [2]     2匹目を生んだ直後
    |   `----→２    [ ]     3匹目を生んだ直後
    |----→３→２    [ ]     4匹目は生めない！不可能
    `--------→３

まず、スライムの家系図は自己相似形(?)になる。

例えば下図で、時刻0のスライムから生まれた子たちの $t=3$ までの親子関係と、時刻1に生まれたスライムが $t=4$ までに生む子たちの親子関係は同じ構造となる。

t   0   1   2   3
   ○→○→○→○
    |   `----→○
    |----→○→○
    `--------→○
  ↓1秒後
   ○→●→●→●→●
    |   |   `----→●
    |   |----→●→●
    |   `--------→●
    |----→○→○→○
    |       `----→○
    |--------→○→○
    `------------→○

これを踏まえて、「体力の大きい順に、その時に生める最も早い時刻に割り当てる」のが良いことを言う。

「体力の大きなスライムをより早い時間に生めるのに、生まなかった場合でも、矛盾無く割り当てできた」とする。

S = {5, 4, 3, 3, 2, 2, 2, 1}

   ５→③→２→１
    |   `----→２
    |----→④→３
    `--------→２

この時、「④以下の構造」と「③以下のうち、④以下の構造と一致する部分」を、矛盾無く入れ替えられる方法が存在する。

   ５→④→３→１  「④→３」
    |   `----→２  「③→２」を入れ替え
    |----→③→２
    `--------→２

もし、こんな割り当てだと、入れ替えると矛盾が発生するが、

   ５→③→２→１      ５→④→１→１
    |   `----→２  →   |   `----→２
    |----→④→１       |----→③→２
    `--------→２       `--------→２

④から子の方面に辿って、あるスライムで、③で同じ箇所に相当するスライムの体力が等しいか大きくなったら、そこで入れ替えるのを止めるとよい。

           ↓2と1を比較して、2の方が大きいので、それ以下の入れ替えは停止
   ５→③→❷→１      ５→④→２→１
    |   `----→２  →   |   `----→２
    |----→④→❶       |----→③→１
    `--------→２       `--------→２

各箇所が、成立の状態を保ったまま入れ替えられることを整理する。

• 「a→③→b→❷→c」と「d→④→e→❶→f」を入れ替えて
• 「a→④→e→❷→c」と「d→③→b→❶→f」とする
• ❷,❶は、入れ替えを打ち切る場所を指す
• a～fは任意の、問題に矛盾しない数とする
• 実際の部分木は複数に枝分かれするが、それぞれ個別に考えても成立すれば、全体でも成立する

• 「a→③」→「a→④」
  • そもそも「より早く生めるのに生まなかった場合」なので、これが成立するような箇所についての話である
• 「d→④」→「d→③」
  • 数字が減っているので大丈夫
• 「④→e→❶」→「③→b→❶」
• 「③→b→❷」→「④→e→❷」
  • 「③→b」「④→e」の部分はもとから成立していた
  • 「b→❶」となる部分は、打切条件と、入れ替え前の関係より $b \gt ❷ \ge ❶$
  • 「e→❷」となる部分は、打切条件と、入れ替え前の関係より $e \gt b \gt ❷$
• ❷以下、❶以下
  • もとから成立していた

全ての箇所で、成立を保ったまま入れ替えが可能であると言える。

「体力の高いスライムから、割り当て可能な最も早い時刻に割り当てる」という方針に当てはまらないで成功する割り当てが存在しても、必ず当てはまるような割り当てに変換することが出来るので、この方針に従って割り当てていって不可能なら、不可能と判定してよい。