ABC469参加記

前回の参加記(ABC468回)

はじめに

こんにちは。ShoboiNamaeです。

最近は甲子園をずっと見ています。智辯和歌山頑張れ。

結果サマリ

• ABC469

• WCPC参加人数: 6人

• 各問題の最速解答者(ペナルティ無し):

今週の出題

A問題

$N - K + 1$ を出力する問題でした。

この式を導く方法はいろいろありますが、 $K$ 両目の前には $K - 1$ 両あることと、 $K$ 両目の後に $N - K$ 両あることから、後ろから見た場合 $N - K + 1$ 両目になるというのはどうでしょうか。

類題

• ABC454 A - Closed interval: 区間内の整数の個数を答える問題です。
• ABC417 A - A Substring: 出力する文字列の始点と終点をどこにするか考える必要があります。 substr() を使うのが楽です。

B問題

それぞれの椅子に対して条件を満たすか判定する問題でした。

公式解説では番兵が紹介されていました。

番兵というのは端に記号などを追加して処理を簡単にする方法のことです。そのままやってしまうと端にある椅子だけ例外処理をしないといけませんが、 S = "x" + S + "x"; とすることで全ての処理を共通化できます。ただし、これをしてしまうと添え字がずれることに注意が必要です。添え字のループは $1$ から $N$ になります。

C問題

$k = 1, 2, \cdots , N$ について順番に答えを求めます。

まず重要な考察として、 $k$ が増えると食べられるお菓子の個数は単調に増加します。 $k = m$ のとき食べられるお菓子の個数は $k = m - 1$ のときよりも（少なくとも $1$ つ）多いです。これを利用して解きます。

まず、列の何番目まで食べることができたかを記録する right という変数をおきます。初期値は $0$ にします。その後、

1. k に関するループの始まりです。
2. right = min(right + 1, N) をします。
3. right == N || S[right - 1] == 'x' ならば right の値を出力して k を進め、 1. に戻ります。
4. そうでないなら 2. に戻ります。

この方針をそのまま実装したコードがこちらです。(C++)

ちなみに

公式解説はもっとスマートに解いています。

実は、食べられるお菓子はぴったり $k$ 番目の’x’までです。よって、‘x’ の位置を調べるとこの問題を解くことができます。

具体的には $N$ 要素の配列を $N$ で初期化し、 "$( k \text{番目の'x'の添え字} ) + 1$" を配列の $k - 1$ 番目に入れます。（ 配列・文字列の添え字は $0$-indexed ）最後はその配列を出力するだけです。

聞いたら納得するけど、何を食べたらこんな解法思いつくんですかね？ 煮つけ…？

D問題

公式解説の方がきれいに解けると思いますが、今回は自分のコンテスト中に出した解法の解説をします。

前置き

入力が

5 3
1 2
3 4
1 4

の時を考えてみると、条件を満たす $(x, y)$ の組は $(1, 3), (1, 4), (2, 4)$ の $3$ 組です。

入力が

5 2
1 2
1 3

の時、条件を満たす $(x, y)$ の組は $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3)$ の $5$ 組です。

入力が

5 2
1 2
1 2

の時、条件を満たす $(x, y)$ の組は $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)$ の $7$ 組です。

というような調子で入力に対する答えを手作業で求めていくと、最も組の総数が多くなるのは $A_i, B_i$ がそれぞれすべて同じ時のような気がしてきました。その時の組の総数は $(N - 1) + (N - 2) = 2N - 3$ 通りであり、 $N$ が最大のケースでも $4 \times 10^5 - 3$ 程度です。

組数の上限がその程度であれば、条件を満たす組をすべてsetに入れたり、queueに入れたりしてもメモリ超過しないです。また、私の解法で行った、毎回候補を全部queueに入れて更新する方法が、ワイルドカードを使って工夫することで実行時間内に間に合います。

解法

queueに候補を入れ、毎回全ての候補を見て候補を更新していきます。簡単のため、queueに入れる候補となる組（pair）は first $\le$ second にします。

そして、 $A_i, B_i$ より十分に大きい数をワイルドカード（どの数にもなることを表す）定数WILDとして宣言しておきます。大きくするのはWILDをできるだけ組のsecond側にするためです。また、候補を入れるqueueは事前に $($ WILD $,$ WILD $)$ を入れておきます。

$A_i, B_i$ の添え字 $i$ をfor文で回し、次の手順で処理を行います。

1. 候補のqueueの要素数を変数szに入れます。
2. sz回のループを始めます。
   1. まず、候補のqueueの先頭の組のfirstをf、secondをsという変数に代入します。その後、先頭はpopします。
   2. f == WILDならば候補のqueueに $(A_i,$ WILD $), (B_i,$ WILD $), (A_i, B_i)$ を入れます（初回の処理）。
      • f == WILDのとき、f $\le$ sよりs == WILDでもあります。つまり、候補 $($ f $,$ s $)$ はどちらの要素もワイルドカードなので、ここから出る候補は上記の3つになります。
   3. s == WILDのとき、f == $A_i$ または f == $B_i$ ならば、候補のqueueに $($ f $,$ WILD $)$ を入れます（ワイルドカードの継続）。そうでないなら $($ f $, A_i), ($ f $, B_i)$ を入れます（ワイルドカードの終了）。
   4. fもsもワイルドカードではないとき、f,sに $A_i$, $B_i$ と同じ値があれば候補のqueueに $($ f $,$ s $)$ を追加します（候補継続）。
      • f,sに $A_i$, $B_i$ と同じ値がなかった時は候補のqueueに何も追加されないので、候補は棄却されたことになります。

最後に、queueに入っている候補すべてをsetに入れて重複を除きます。ここでWILDを復元します。具体的には $($ f $,$ WILD $)$ がある場合に $N - 1$ 個の組 $($ f $, i )$ をsetに入れます。（ $i$ は $1$ 以上 $N$ 以下かつfではない整数）

これで全ての条件を満たす組がsetに入れられたので、答えはsetの要素数になります。

計算量

最初の $($ WILD $,$ WILD $)$ からは $(A_i,$ WILD $), (B_i,$ WILD $), (A_i, B_i)$ の3つが候補となり、 $($ f $,$ WILD $)$ からは $($ f $, A_i), ($ f $, B_i)$ の $2$ つが候補になります。また、 $($ WILD $,$ WILD $), ($ f $,$ WILD $)$ 以外からは最大で $1$ つの候補しか出ないので候補数が増えることはないので、候補のqueueの要素数は最大で $5$ 個です。

よって、添え字 $i$ について $M$ 回ループを回しても十分高速です。

最後のsetに入れる処理も、入れる要素数が最大で $2N - 3$ 個であることから $O(N \log N)$ の計算量で済みます。

E問題

この回のABCの終了後に界隈では食塩水典型だーという声が上がっていました。

全然知らなかったのですが、確かに応用が効きそうな考え方だなと思いました。

食塩水典型とは？

確かなことは分かりませんが、濃度などを答えで二分探索するテクニックで解くときに、「濃度が $p$ 以上」という式の変形を使って問題を解く典型だと思います。

今回のE問題の記事を書くにあたって、名前のもとになったと思われる先にABC034 D - 食塩水を解いてみました。（解けなかったので解説を読みました）

食塩水はどういう問題だったかというと、

食塩水を理解したのでこれで今回の問題を解ける！と思ったのですが結局解けず、公式解説を読みました。（食塩水の問題を解いてからの方が開設の内容がよく分かったので効果はあった）

今回の問題の食塩水と違うところ

今回の問題と食塩水の明らかに違うところは、連続する区間を選ぶ必要があるというところです。

食塩水の問題は連続する区間を選ぶ必要がなかったのでソートが有効でした。しかし、今回はそれが使えません。

ところが、連続する区間を選ぶことで使えるようになることもあります。それは累積和です。ということで、今回は累積和を使います。

解法

※ここからは公式解説と同じ解法を書いています。

食塩水の問題と同じように $s_i-w_ip$ を使います。今回の $s_i$ は S[i] == ‘o’ならば $1$ 、そうでないなら $0$ です。また、 $w_i$ は常に $1$ です。

今回は連続する区間を選ぶので $\sum_i(s_i-p)$ の計算に累積和が使えます。つまり、区間 $i$ までの累積和を $P_i$ 、選んだ区間を $[r, l]$ とすると、 $\sum_i(s_i-p)=P_r-P_{l-1}$ が成り立ちます。このとき、 $0$ 以上を達成するためには $P_r$ が大きく、 $P_{l-1}$ が小さくなっていた方が嬉しいことは明らかです。

これらのことを使うと、次のようにしてこの問題を解くことができます。

1. $p$ を決めます。
2. $s_i-p$の累積和をとります。
3. $s_i-p$の累積和の累積minをとります。
4. 尺取り法を用いて各 $r$ に対する最大の $l$ を調べます。この $l$ は、区間 $[l,r]$ で $K$ 勝以上する $l$ です。
5. $r$ に関するループを回して $r$ を全探索します。そして、前の手順で調べた $r$ に対応する $l$ における累積minを $M$ とし、$P_r-M$ が $0$ 以上かどうかを調べます。

以上の $5$ つの手順が二分探索の判定部分です。この処理の計算量は $O(N)$ なので、二分探索の反復回数を $X$ として、全体の計算量は $O(NX)$ になります。二分探索の反復回数は十分少ないと考えられるので、実行制限時間内に解くことができます。

F問題以降

割愛します。

最後に

記事を書くのがかなり遅れてしまい申し訳ございません。記事を頼まれてから書き終わるまでの期間にVSCodeのUIがアップデートで変わってしまいました…（びっくりした）

遅れた分を取り戻そうと思い、問題の振り返りに解法を書きまくることで記事のボリュームをマシマシにしました。A問題を書いていた時はやる気があったので類題までついてます。ただ、遅れた分いい記事を書こうとしてさらに遅れた気も…

ここでひとつ、最後まで読んでくれた方に豆知識を授けましょう。

和歌山大学には「わだにゃん」というかわいいマスコットキャラクターがいます。みかんをかぶっている猫のようなキャラクターです。しかし、愛媛県にも「みきゃん」というかなり似たキャラクターがいます。結構似ています。

でも知ってましたか? みきゃんって犬なんですよ。

わだにゃんは猫、みきゃんは犬ということで、両者棲み分けができているのですね。

最後までお読みいただきありがとうございました。