ABC468参加記

前回の参加記(ABC467回)

はじめに

こんにちは。nsubaruです。

上振れ青パフォで+104！入水しました！！！！🩵🩵🩵🩵

[入水した図]

初の青パフォでしかも1890パフォ、初の6完でしかも1時間切り、上振れに上振れました！

前回のABCで負けてレートが1124だったので今回もまだ水色にはなれないだろうなって感じで始まったのですが、トントン拍子に問題を解くことができ、終わってみれば6完という結果になりました！

結果サマリ

ABC468
WCPC参加人数: 7人
各問題の最速解答者(ペナルティ無し):

問題	参加者名	タイム	言語
A	nsubaru	0:36	Java
B	ShoboiNamae	5:10	C++
C	ShoboiNamae	9:02	C++
D	ShoboiNamae	39:25	C++
E	nsubaru	32:41	Java
F	nsubaru	54:37	Java
G	-	-	-

今週の出題

ABC468-A

問題ページ: A問題

問題文を表示

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

$A_i \lt A_{i+1} > A_{i+2}$ を満たす $1$ 以上 $N-2$ 以下の整数 $i$ の個数を求めてください。

制約

$3\le N\le 100$
$1\le A_i\le 100$
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。

ICPC2022の国内予選と同じ問題ですね。極大値のカウントということで、配列用のライブラリに用意していました！ ArrayUtils.localMaxCnt() 関数を用いることで一瞬です！

ABC468-B

問題ページ: B問題

問題文を表示

問題文

整数 $M,D$ と、 G, . からなる長さ $M$ の文字列 $S$ が与えられます。

$M$ 個のマスが左右に一列に並んでおり、左から順にそれぞれ $1$ から $M$ までの番号がついています。

いくつかのマスにはガードマンが立っています。具体的には、 $S_i=$ G ならばマス $i$ にはガードマンが立っており、 $S_i=$ . ならばマス $i$ には誰も立っていません。

ガードマンが立っているマスからの距離が $D$ 以下であるマスはガードマンによって監視されます。すなわち、あるマス $i$ が存在して $S_i=$ G かつ $|x-i|\le D$ を満たすマス $x$ はガードマンによって監視されます。

$M$ 個のマスのうち、監視されていないマスの個数を求めてください。

制約

$0\le D \lt M \le 100$
$D,M$ は整数
$S_i$ は G と . からなる長さ $M$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$M$ $D$
$S$

出力

答えを出力せよ。

B問題にしてはめんどくさいなという印象。まあでも難易度的には順当かなという感じです。

G の前と後ろ $D$ 以内のところを # で埋めて、最後に . の数をカウントすることで解けました。

ABC468-C

問題ページ: C問題

問題文を表示

問題文

整数 $N$ と $(1,2,\ldots,N)$ を並び替えた整数列 $P=(P_1,P_2,\ldots, P_N),Q=(Q_1,Q_2,\ldots,Q_N)$ が与えられます。

$(1,2,\ldots,N)$ を並び替えた整数列であって辞書順で $P$ より大きく $Q$ より小さいものがいくつあるか求めてください。

整数列の辞書順とは？

整数列 $S = (S_1,S_2,\ldots,S_{|S|})$ が整数列 $T = (T_1,T_2,\ldots,T_{|T|})$ より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、 $|S|, |T|$ はそれぞれ $S, T$ の長さを表します。

$|S| \lt |T|$ かつ $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$ 。
ある整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ が存在して、下記の $2$ つがともに成り立つ。

$(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
$S_i$ が $T_i$ より（数として）小さい。

制約

$1\le N\le 10$
$P,Q$ は $(1,2,\ldots,N)$ を並び替えた整数列
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$

出力

答えを出力せよ。

最初に制約が目に入ったときに、これは $\mathcal{O}(N!)$ だなと分かりました。

そして、問題を見ると $1 \dots N$ までの整数列の並び替えとあるので、これは順列全列挙だなとなりました。

ここで使えるのが、next_permutation と呼ばれる関数で、数列を辞書順で次の順列に変換させるという関数です。これを用いることで、数列 $P$ が数列 $Q$ と一致するまでループを回し続けその回数をカウントすることで解けました。

C++やPythonでは標準である関数ですが、Javaでは無いので自作する必要があります。

ABC468-D

問題ページ: D問題

問題文を表示

問題文

以下の条件を満たす英小文字からなる文字列を良い文字列とします。

$1$ 文字以下を書き換えることで回文にすることができる。

例えば a、iwai、abcdcza などは良い文字列ですが、abcd、atcoder などは良い文字列ではありません。特に、回文も良い文字列であることに注意してください。

英小文字からなる文字列 $S$ が与えられます。

$S$ の空でない部分文字列（連続な部分列）であって良い文字列であるものの個数を求めてください。

$2$ つの部分文字列は、 $S$ から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。

部分文字列とは

$S$ の部分文字列とは、 $S$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上削除して得られる文字列のことをいいます。例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

$S$ は英小文字からなる長さ $1$ 以上 $10^4$ 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

答えを出力せよ。

文字列系の問題でめんどくさそうだなという印象で、問題を読んで2秒でとばしました。最近はこういった問題を飛ばす判断が結構当たっていて、競技者として本当に強くなってきたなという印象。

E問題を解いた後、約10分で解くことができました。

制約的に $N$ が $10^4$ なのでまあ $\mathcal{O}(N^2)$ が行けるだろうと思いました。

まず、定数倍速くするのと処理を簡単にするために、最初に　Manacher のアルゴリズムを用いて、各点を中心とする最大回文長を偶数長、奇数長ともに求めます。回文を見つけたらその両端の文字は絶対に異なるので、その文字を書き換えて回文にすることができます。そこからさらに両端の文字が同じ限り良い文字列なのでそれも忘れないように求めます。

もちろん Manacher を用いずともある点を中心とする良い文字列の最大長を求めるという方法でも解くことができます。

ABC468-E

問題ページ: E問題

問題文を表示

問題文

正整数 $N$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

$f(l,r)$ を $A_l,A_{l+1},\ldots,A_r$ の（算術）平均として定義します。

$\displaystyle \sum_{1 \le l\le r\le N} f(l,r)$ を $\text{mod }{998244353}$ で求めてください。

有理数 $\text{mod }{998244353}$ の定義

この問題の制約のもとでは、求める有理数を既約分数 $\frac{P}{Q}$ で表した時、 $Q {{}\not\equiv{}} 0 \pmod{998244353}$ となることが証明できます。よって、 $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まります。この $R$ を答えてください。

制約

$1\le N\le 5\times 10^5$
$0\le A_i \lt 998244353$
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。

今回ラップタイムで言えば一番時間のかかった問題（約23分）です。解けたからよかったものの、D問題を飛ばして取り組むにはちょっと重い問題ではありました。

ただ個人的にこういう問題は好きな部類でやることが明確です。 2重ループを回すとTLEになってしまうので、式変形して、前計算や累積和、セグ木とかを用いて1重ループにすればよいだけです。

まず、簡潔に表された数式を元の式に直します。

\sum_{1 \le l\le r\le N} f(l,r) = \sum_{1 \le l\le r\le N} \frac{1}{r-l+1} \sum_{i=l}^r A_i

この式に着目すると、まず一番右側のΣは累積和配列を用いることで、 $\mathcal{O}(1)$ で計算が可能です。ただし、それだけだとまだ不十分で、 $l, r$ のループに $\mathcal{O}(N^2)$ かかってしまいます。

つぎに、 $\frac{1}{r-l+1}$ の項に着目すると $r$ と $l$ が異なってもその差が同じであれば、まとめることができます。つまり、平均を求める区間（項数）を1から順にNまでループしていくことで、区間が同じになる要素の和を $\mathcal{O}(1)$ で求めることができれば行けそうだなと分かります。

最後に、区間が2の要素の和を考えます。 $(A_0 + A_1) + (A_1 + A_2) + ... + (A_{N-1} + A_N)$ であることから。 $A_0$ と $A_N$ つまり、両端の要素だけ1回しか加算されていないことが分かります。この係数部分にだけ着目すると、

\begin{array}{ccccccccc} A_1 & A_2 & A_3 & A_4 & A_5 & A_6 & A_7 & A_8 & A_9 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ 1 & 2 & 3 & 3 & 3 & 3 & 3 & 2 & 1 \\ 1 & 2 & 3 & 4 & 4 & 4 & 3 & 2 & 1 \\ 1 & 2 & 3 & 4 & 5 & 4 & 3 & 2 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array}

となっていくので、真ん中の部分だけどんどん増やしていくようにすれば区間が同じになる要素の和を $\mathcal{O}(1)$ で求めることができます。

これは単純に累積和配列のみを用いればよいのですが、遅延セグ木やRangeBITなど、実装を彷徨ってしまったため時間が少しかかってしまいました。

ABC468-F

問題ページ: F問題

問題文を表示

問題文

正整数 $N$ と $(1,2,\ldots,N)$ の並び替え $P=(P_1,P_2,\ldots,P_N)$ が与えられます。

変数 $x,y,c$ があります。はじめ $x=y=c=0$ です。

あなたは $k=1,2,\ldots,N$ の順に以下の操作のいずれかを行います：

操作 $1$ ： $x \lt P_k$ ならば $c$ を $1$ 増やす。その後、 $x$ を $\max(x,P_k)$ に置き換える。
操作 $2$ ： $y \lt P_k$ ならば $c$ を $1$ 増やす。その後、 $y$ を $\max(y,P_k)$ に置き換える。

最終的な $c$ の値の最大値を求めてください。

制約

$1\le N\le 5\times 10^5$
$P$ は $(1,2,\ldots,N)$ の並び替え
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

出力

答えを出力せよ。

D,Eを順当に解くことができたため、残り1時間近くを残してF問題を始めることができました。

問題は簡単に言うと、2つの操作を行って変数 $c$ の値を最大化しようというものです。

操作1,2はどちらも同じ操作で対象となる変数が異なるというだけです。それぞれの操作で変数の更新が行えたら $c$ の値を増やすことができます。

まず単純にこの操作が1だけの時を考えます。この場合は簡単で、前から更新を行っていきその回数が答えになります。このとき更新を行う際に不要だった要素、つまり変数を更新できなかった要素は一切不要だと分かります。

そこで操作1で更新に不要だった要素を集め、そこでLIS（最長増加部分列）を解くことで、操作2で更新できる回数が分かります。

と、このように案外単純な問題で解くのに約10分しかかかりませんでした。

ABC468-G

問題ページ: G問題

問題文を表示

問題文

整数 $N$ と o と x からなる長さ $N$ の文字列 $S$ が与えられます。

以下の条件を満たす $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ の個数を $998244353$ で割ったあまりを求めてください。

$k=1,2,\ldots,N$ に対し、以下の $2$ つは同値となる。
$S_k=$ o
$P$ が $(1,2,\ldots,k)$ の順列を連続部分列として含む

制約

$1\le N\le 2000$
$S_i$ は o と x からなる長さ $N$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$N$
$S$

出力

答えを出力せよ。

F問題を解いて、約1時間。既にこの時点で黄パフォが出て水色が確実になり速く終わってくれと思いながらこの問題を考えていました。コンテスト後にACができたので、もっとちゃんとやっていれば奇跡の全完ができたという後悔はありますが、またいつか機会があれば最後まで全力で頑張ろうと思います。

さて、また順列の問題です。ここ最近のG問題の中では550点で青diffだったので、結構簡単目な問題でした。問題はややこしいですが、要するに $S_i =$ x なら $P$ に $1 \dots i$ の順列が連続の部分列として含まれないが、 $S_j =$ o なら $P$ に $1 \dots j$ までの順列が連続の部分列として含まれる、というものです。

まず前提として、 $S_1 =$ x という状況と $S_N =$ x という状況はあり得ないため早期判定を行います。

つぎに oxxoxxo という文字列について考えます。 4文字目に o があるので、 $1 \dots 4$ の順列は含まれます。またこの時点でこの4文字の間には他の数字が入ってはいけないので、ここを一つの塊とみなし、条件を満たす並び方の個数を保持します。次に5文字目以降を見るとき、前の4文字は1つの塊とみなしたので、この4文字をまとめて o と扱えます。そして次の o までを新たな塊とみなすと、この新しい塊の並び方は、前の塊の並べ方に、前の塊を o とみなした時の並べ方をかけたものになります。そのように考えると、 o で始まり o で終わる並べ方を長さごとに前列挙しておけば解くことが出来そうです。

この前計算の一般項を求める方法として、小さいケースで next_permutation を用いて全探索を行いその数を求めてOEISで検索し、数列の一般項を特定することで解けます。

oeis.org

最後に

終わってみれば、今回は結構簡単目な回だったのかなと思います。（黄diff以上が無いという意味で）

最近は結構FやGにもチャレンジして精進を行っていたので、その甲斐もあり上振れできたのかなと思います。上振れ力はあっても圧倒的に演習が不足していてE問題を確実に通せる実力はまだまだなので、すぐに水に落ちそうでひやひやです。ただ、今回6完という成功体験ができたおかげで今後はFを解くという心理的ハードルを下げられたのかなと思います。

とりあえず、緑に落ちたくないので、また今週も精進します。