競プロ参戦記 #63 Second Sum | ABC 140

ABC に参加して、ぎりぎりのE完でした。

AtCoder Beginner Contest 140

• この連載記事では、着手した問題の考察を自分なりに書いていきます。
  • 前回: 競プロ参戦記 #62 League | ABC 139
• 問題の詳細は問題一覧を参照してください。
  • 問題一覧: https://atcoder.jp/contests/abc140/tasks

A - Password

問題概要: 1 以上 N 以下の整数を3つ並べたものは何通りあるか。

A: 考察

1つ目、2つ目、3つ目がそれぞれ N 通りあるので、全体では N^3 通りです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7385531

B - Buffet

問題概要: N 個の料理をある順番で1つずつ食べた。i 番目に食べたのは料理 A(i) である。料理 i を食べると満足度 B(i) を得る。料理 i の直後に料理 i+1 を食べると、追加で満足度 C(i) を得る。得られた満足度を求めよ。

B: 考察

基本的には問題文に書いてある通りの実装になりますが、追加の満足度の計算に少し言い換えが必要です。

「料理 x の直後に料理 x+1 を食べると～得る」は「いま食べる料理が x+1 で、直前に食べた料理が x なら～得る」と言い換えられます。ここで、

• いま食べる料理 = 料理 A(i) = x+1
• 直前に食べた料理 = 料理 A(i-1) = x

なので、条件は「i≥2 かつ A(i) = A(i-1) + 1」です。

直前に食べた料理を A(i-1) で参照する代わりに変数に記録してもよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7385205

ところで無意識に「直後に食べると～」を「直前に食べた料理は～」に言い換えてしまいましたが、料理を食べる順番は事前に指定されているので、直後に食べる料理 A(i+1) (i+1≤N) を使った方がシンプルだったかもしれません。

C - Maximal Value

問題概要: 長さ N-1 の整数列 B が与えられる。以下の条件を満たす長さ N の整数列 A が存在する。A の総和の最大値を求めよ。

条件: すべての i (1≤i≤N-1) について B(i) ≥ max(A(i), A(i + 1))

C: 考察

例えば N=3 のとき、以下の2つの条件が与えられています。

    B(1) ≥ max(A(1), A(2))
    B(2) ≥ max(A(2), A(3))

x ≥ max(y, z) は x ≥ y かつ x ≥ z と同値なので、以下の4つの条件に言い換えられます。

    B(1) ≥ A(1)
    B(1) ≥ A(2)

    B(2) ≥ A(2)
    B(2) ≥ A(3)

いま知りたいのは A の条件なので、A(i) に関して整理します。(左右をひっくり返して改行を入れるだけです。)

    A(1) ≤ B(1)

    A(2) ≤ B(1)
    A(2) ≤ B(2)

    A(3) ≤ B(2)

x ≤ y かつ x ≤ z は x ≤ min(y, z) と同値なので、A(2) に関する条件はまとめられます。

    A(2) ≤ min(B(1), B(2))

こうして各 A(i) の最大値が求まりました。

    A(1) ≤ B(1)
    A(2) ≤ min(B(1), B(2))
    A(3) ≤ B(2)

最初と最後が特別であることに注意して一般化します。

    A(1) ≤ B(1)
    A(i) ≤ min(B(i-1), B(i)) (i∈{2, ..., N-1})
    A(N) ≤ B(N-1)

後は最大値の和を計算すればOK。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7384146

D - Face Produces Unhappiness

問題概要: N 人が一列に並んでいて、東西どちらかを向いている。人は「自分の目の前に人がいて、その人が自分と同じ方向を向いている」とき幸福であり、そうでなければ不幸である。以下の操作を最大 K 回まで行った後、幸福な人の人数の最大値を求めよ。

操作: 区間 [L, R] (L ≤ R) に含まれる人の列を180度回転する。

D: 考察

180度回転とは、以下のようにぐるんと一回転する操作です。範囲内の人を左右反転してから向きを反転する操作ともいえます。

    位置関係

          L       R
    ... ← A B C D E   ...

    ...   E D B C A → ...

    向き

    ... L L R R R ...

    ... L L L R R ...

人が幸福かどうかは、自分からみた目の前にいる人の相対的な向きによって決まるので、自分と目の前の人がいっしょに回転するとき、幸福か否かは変化しません。そのため、 1回の操作で増やせる幸福度は最大 +2 です。

左端の人が左を向いていると仮定します。(そうでないときは左右を逆に考えれば同様の考察ができるはず。)

全員が同じ方向を向いているときは、幸福度が上限 N-1 を達成しているので、追加の操作は不要です。

    L ... L

左を向いている人と右に向いている人が左右に分離しているときは、右を向いている人たちを回転して向きをそろえることで幸福度 N-1 にできます。

    L ... L R ... R
    L ... L L ... L
            ^^^^^^^

左を向いている人たち、右を向いている人たち、左を向いている人たち、という並びがあるなら、右を向いている人たちを回転することで幸福度 +2 できます。

    L ... L R ... R L ??...
    L ... L L ... L L ??...
            ^^^^^^^

したがって、1回の操作で必ず、

• 幸福度を N-1 にできる
• 幸福度を +2 できる

のどちらかを達成できます。

結局、最初の幸福度を h とすると、最大の幸福度は min(h + 2 * K, N - 1) と表せます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7394186

E - Second Sum

問題概要: 1 以上 N 以下の整数の順列 P が与えられる。長さ2以上の区間 [L, R] (1 ≤ L < R ≤ N) に対して、区間内に含まれる P の要素で2番目に大きいものを X(L, R) とおく。X(L, R) の総和を求めよ。

制約: N≤10^5

E: 考察

副問題

「2番目に大きい」という条件は厄介なので、ひとまず「一番大きい」に置き換えた問題を考えます。

• 長さ2以上の区間 [L, R] について、区間に含まれる P の最大の要素を Y(L, R) とおく。Y(L, R) の総和を求めよ。

区間は O(N^2) 通りあるので全列挙できません。代わりに、Y(L, R) の値で区間を分類することにします。

すなわち、Y(L, R) = y であるような区間 [L, R] が m 個あるとき、総和を m * y 増やす、という操作を行います。y は O(N) 通りなので、m を高速に求められれば間に合いそうです。

Y(L, R) = y の値が分かったとします。y は順列に含まれる値なので、y = P(i) となる i を逆算できます。区間の最大値が y なので、区間は i を含むはずです。つまり L ≤ i ≤ R がいえます。

y が最大値であるということは、y より大きい値は区間に含まれていないはずです。y = P(i) より右に、y より大きい値 x = P(j) があるとすると、R < j でなければいけません。大きい値がなければ R ≤ N です。左も同様。

例えば N=5, P=(3, 1, 4, 2, 5), y=4 では、以下の4つの区間があります。L が2通り (1, 2) で R も2通り (3, 4) です。

    y = 4, i = 3

    i | 1 2 3 4 5
    P | 3 1 4 2 5
    --+----------
        [   ]
        [     ]
          [ ]
          [   ]

そういうわけで、各 y = P(i) について、左右にある y より大きい要素を探して L, R の場合の数を求め、区間を数えて総和に計上する、という手続きで解けそうです。

しかし、y より大きい要素を線形探索で探すのでは O(N^2) になってしまって間に合わないので、さらに一工夫いります。

「値が y より大きい」「位置が i より左」という2つの条件で高速に検索できるデータ構造があればよいですが、思いつきません。

やや天下り的ですが、 y を大きい順に処理する ことにすると、「値が y より大きい」要素の集合を持ちながらループを回せます。

はじめに集合 S = {} を用意しておき、y = P(i) の処理が終わるたびに S に i を追加することにします。すると、S は y より値が大きい要素のインデックスの集合です。「値が y より大きい」「位置が i より左」である要素の検索は、集合 S から i より小さい最大の要素を探すことで実現できます。

また、S = {0, N+1} で初期化しておく (= 番兵を使う) と「y より大きい値が左/右側にないとき」といったケースの場合分けを省略できます。

主問題

「一番大きい」を「2番目に大きい」に変えても同様です。

X(L, R) = P(i) を大きい順に列挙します。値が P(i) より大きい要素のインデックスの集合 S を持っています。

P(i) が2番目に大きいような区間は、i を含んでいて、さらに P(i) より大きい値をちょうど1個含んでいればよいです。

集合 S から i に近い要素を左右に2個ずつ探して、(左から順に) w, x, y, z が見つかったとします。区間 [L, R] は以下の2種類があります。

• w < L ≤ x かつ i ≤ R < y (左側にある大きい要素を含む)
• x < L ≤ i かつ y ≤ R < z (右側にある大きい要素を含む)

    w ... x ... i ... y ... z
      [[[[[     ]]]]]
            [[[[[     ]]]]]

このようにして、副問題と同様に解けます。

実装

本番では 番兵 を使うことを思いつかなくて、実装で苦しみました。

• 「左側に大きい要素がないとき、1個あるとき、2個あるとき」
• 「右側に大きい要素がないとき、1個あるとき、2個あるとき」
• 左右

という場合分けをして各ケースの計算を合わせる作業、つらい……

さらにいうとインデックスの集合だけ持てばいいことにも気づかなくて、「値が大きい2つの要素」を乗せたセグメントツリーでごり押ししています。ぎりぎりになったのはこれのせい。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7403671

その後、集合 (BTreeSet) を使って綺麗に書き直した んですが、BTreeMap::range が AtCoder のバージョンでは使えなかったのでボツです。

結局、セグメントツリーのインデックスの持ち方を改善することで落ち着きました:

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc140/submissions/7438073