Codeforces が開催する競技プログラミングのオンライン大会に参加したので、日記半分・解説半分に書いていきます。1年ぶり2度目ぐらいのリアルタイム参戦です。

A. Single Wildcard Pattern Matching

問題：文字列S,Tが与えられる。Sには最大1個の*が含まれる。この*を何らかの文字列で置き換えて、Tと同じ文字列にできるか？

たしか Rust は標準ライブラリに正規表現がなかったので、真面目に文字列処理をする。

S=abc*def で T=abcxxxdef みたいな例を考えると、S の * より前の部分が T の先頭に一致し、 * の後が T の末尾にすればOK、といえます。ただし T が短すぎる例外ケースに注意です。

筆者の提出：

B. Pair of Toys

問題：1, ..., N から重複なく2つ選んだ組み合わせで、和が K になるようなものの個数を求めよ

解説：組み合わせ (K - x, x) (ただし K-x < x) としてありえる x の範囲を計算します。がんばって計算する。

ちなみにユニットテストが通って嬉しくなって、main 関数が空のまま提出するというぽかをしました。

C. Bracket Subsequence

問題：うまく対応が取れているカッコ列Sが与えられる。Sからいくつかの文字を削って、長さがちょうどKに等しい、うまく対応が取れているカッコ列にせよ

「うまく対応がとれているカッコ列」とは () や ()() や (())()(()) のようなもの。こういう言語をディック言語(Wikipedia)というらしいです。

明らかにツリー構造なので、部分木を探索すればいけそうな気がします。つまり、あるツリーから、「長さ」の和が K になるように、重なりのない部分ツリーをいくつか選択できるか？

カッコ列は形式的には次のように定められます。 () はカッコ列です。A がカッコ列なら (A) もカッコ列。A, B がカッコ列なら AB もカッコ列。それ以外はカッコ列ではありません。

こうしてみると、長さ N のカッコ列から長さ N-2, N-4, ..., N-2n (>=2 ) の部分列がかならず取れます。なので、貪欲的に左から長さ K 以下のカッコ列を1つ見つけていくのを繰り返せばOKです。

Rust 力が低くてツリー構造を作れなかったので、がんばって配列でカッコの対応を記録することにしました。つまり、各文字に、深さと対応する左右の括弧の位置をもたせていく。これは普通にループでできます。

D. Array Restoration

問題：長さNの数列がある。1からQの各整数qにつき、数列のある区間の要素をqで埋めた。これにより数列の要素はすべて変更された。この時点での数列をAとする。次に、数列のいくつかの要素に0を設定した。この時点での数列をBとする。数列Bが与えられるので、前述の数列Aとしてありえる数列を1つ求めよ。

本番中には解けませんでした。AtCoder で似たような問題を見た気がするけど思い出せない。

例えば Q=3, B=(1,0,2,3) なら、A=(1,1,2,3) または A=(1,2,2,3) が正解。

例えば Q=3, B=(2,0,3,1) なら、0 の位置は 2,3 だけでなく 1 でもいい。q=2 の時点で (2,1,1,1) 、q=3 で (2,1,3,1) というのはありうるから。

このあたりから大きい数字は小さい数字より「上に」塗り重ねられている感じがしてくるので、逆に大きい数字を「剥がして」いけばAが構成可能かどうか分かりそうです。

具体的には、qをQから1に動かして、「値がqである要素からなる、1つの連続した区間を見つけて、数列から削除する」ということを繰り返していく。構成可能なら最終的に空になるし、逆も真のはずです。

この過程で0の値も埋められます。qの区間の両隣の0はqに書き換えてしまってOKです。

計算時間的には「配列からある区間を削除する」という操作が重たいので若干の工夫がいります。連結リストを使うことにしました。配列の各要素に「両隣」へのインデックスをもたせておき、区間を削除するときに、区間の両隣のリンクを更新して削除区間がスキップされるようにします。ちなみに本番ではここがバグっててWAになった模様。

提出 (コンテスト終了後)：

おわりに

解説は、おそらくもっといいやり方があるので、余裕があったら他の参加者のコードや解説を見て参考にします。

開催時間が厳しい (日本標準時 23:35 ~ 翌 01:35) けどときどき参加していくつもりです。レートは 3 上がりました。