Codeforces Round #504 参加記録

Dashboard - Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) - Codeforces

今回はプレテスト4完…でしたがシステスでDが落ちてしまい結果3完。初めてこどふぉでレートを下げてしまいました…

f:id:betrue12:20180818180908p:plain

A〜Dを振り返っていきます。

A. Single Wildcard Pattern Matching

Problem - A - Codeforces

文字列 $s, t$ が与えられ、 $s$ にはワイルドカードとして0個または1個の * が含まれています。* を0文字以上の文字列に置き換えることで $s$ と $t$ を一致させられますか、という問題。

* がない場合は簡単で、2つの文字列が同じかどうかを見ればよいです。

* がある場合は * で区切って、前から後ろからそれぞれ一致するか見ればよい…のですが、サンプル4のように前と後ろが被ってしまう場合に注意。私は文字列の長さをチェックすることで対処しました。

ACコード：Submission #41687469 - Codeforces

Rubyの String#split を使うと、 * が文字列の最初や最後にあった時に2つに分けてくれないので、前後に適当な記号を付けています。これが原因で1RE…

余談ですが、正規表現を作ると実装が楽なのでは？と思って書いてみましたがTLEでした…

B. Pair of Toys

Problem - B - Codeforces

1から $n$ までの整数から異なるものを2つ選んで和を $k$ にする選び方は何通りありますか、という問題。

使える数の上限が決まっているので、和を $k$ にするペアのうち大きいほうに着目しましょう。大きい方の数を $B$ とすると、 $B$ は以下のような制約を持ちます。

問題文より、 $B \le n$
1以上の数との和が $k$ であるため、 $B \le k-1$
和が $k$ となるようなもう一方の数より大きいため $B \gt k-B$ 、つまり $B \gt \frac{k}{2}$

以上の条件を満たす整数の数は、上限と下限をそれぞれ考えることにより

$\min(n, k-1) - (\lfloor\frac{k}{2}\rfloor+1) + 1$

となります。ただし計算結果が0以下の場合は0です。

本番ACコード：Submission #41690883 - Codeforces
整理したコード：Submission #41747996 - Codeforces

C. Bracket Subsequence

Problem - C - Codeforces

長さ $n$ の「正しい括弧列」が与えられるので、その部分文字列(連続でなくてもよい)であって長さ $k$ のものを1つ見つけてください、という問題。 $n, k$ はともに偶数です。

正しい括弧列を作るためには、 ( はできるだけ左に、) はできるだけ右にあるほうが嬉しいです。そのため、元の文字列の左から $\frac{k}{2}$ 個の ( を、右から $\frac{k}{2}$ 個の ) を使えば、それが答えになります。

ACコード：Submission #41693763 - Codeforces

D. Array Restoration

Problem - D - Codeforces

長さ $n$ の数列に、「ある空でない区間を選んで、その間の数を全部 $i$ にする」という操作を $i=1,...,q$ それぞれについて行います。数列の全ての要素は少なくとも1つの区間に含まれています。

問題で与えられる長さ $n$ の数列は0を含んでいる可能性があり、0は好きな数字に置き換えることができます。適切に置き換えることで、この数列を「上記の操作の最終結果としてあり得る数列」にすることができるか判定してください、という問題。YESなら置き換え結果も示す必要があります。

操作ごとに区間を選び、前より大きい数字で上書きしていくので、結果の数列は山の等高線のようになります。

f:id:betrue12:20180818174347p:plain

このとき、分断された複数の区間を同じ数字で上書きすることはできないため、

同じ数字が、自分より小さい数字（谷）で分断されているとNO

です。さらに、最後には必ず $q$ で上書きする操作で終わり、かつ全ての操作区間は空でないため、

1つも $q$ が存在しなければNO

です。ただし0がある場合は、0を $q$ に置き換えることができるため、その可能性も考える必要があります。

0の置き換え方針は以下のようにしました。

初期状態の数列に $q$ が含まれていない場合に限り、最初の0は $q$ に置き換える。
それ以外の0は、新しく谷を作らないように置き換える。例えば、数列で一番左にある場合は1、それ以外の場合は左隣と同じ値に置き換える。

この上で、「同じ数字が、自分より小さい数で分断されているか」を判断しますが…私はここで「見ている数字が、1つ左の数字より大きいとき」のみ重複チェックをしていました。この場合、1 2 3 2 3 の3のような分断は検出できますが、 1 2 3 2 4 3 の3のような分断が検出できません。

正しい実装をするにはスタックを使うと楽です。スタックの中身が常に単調増加になるように保ち、新しい要素を入れる時にはその要素より大きい要素を「使用済み」扱いにして捨てます。「使用済み」の数が再度登場した場合は、自分より小さい数で分断されていることを意味するためNOを出力します。

ACコード：Submission #41749634 - Codeforces

さいごに

Dが落ちたのは完全に考察ミスですね…

こどふぉではこれを皮切りに3夜連続でコンテストがあるので、下がったレートを取り戻したいところです。

ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。