Atcoder Regular Contest #024 参戦記

久々に時間の都合がついたので参加。他の大会も含め、参加できる回数は減ってきていますが、それでも参加できるときは参加したい。

A:くっつける靴を全探索するなどしても間に合いますが、靴のサイズが10以上40以下なので、左側の各サイズの個数を数えておき、右側で出てきた分だけ数えるというのが組みやすく早いでしょうか。

B:シミュレーションでは間に合わないようだったので、とりあえず実験。基本的に変化するのは"同じ色のT本の木が連続している区間"で、これが$\lfloor\frac{T-1}{2}\rfloor$回後に「もう変化しない」状況になります。そこで、Tのうち、最大値を求めればOK、ということになります。但し、最初から全ての木が同じ色の場合は無限に変化を続けてしまいます。という事で組んでみたところ入出力例と少しずれる。どうやら「○回後」ではなく「○回目」という事だったらしいので、回数をずらして出力しました。

C:時間内に組んだソースは、つまらないミスをしていて部分点しか取れませんでしたが、終わってから少々検討して直したところ普通に満点が取れました。
問題文はちょっと要旨がつかみにくいので、整理すると「$N$文字の文字列$S$に対し、第$t$文字目から始まる連続$K$文字の部分文字列を$S_t$とする。非負整数$i,j$($i<j$,$j-i\ge K$)に対し、$S_i$と$S_j$が同じ文字からなる(順番は異なっても良い)ことはあり得るか判定せよ。」となります。過去の情報オリンピックで「マヤ語文献の読解」として似た問題が出ています。
尺取り法で各部分列に対し、文字の頻度分析を行います。これによって、全ての部分文字列の頻度分析が$O(N)$で行われます。この結果を$O(Nlog N)$程度でソートし、無駄が無いように比較すれば(ここで失敗していました)満点になります。
なお、以下の解答例はコンテスト後修正してACを取ったものです。

oo△-,57位,245点でした。問題はこちら。

ARC#015とABC#001に思うこと

ARC#015のB,Cと、ABC#001の全問の出題を担当していました。遅ればせながら、出題意図などを紹介します。解説はchokudaiさんが良いものを作ってくれているので、そちらをご覧ください。また、この記事はAtcoder社の公式の記事ではなく、あくまでAtcoderを応援する一人のWriterの心情です。この記事に書いていることについて、Atcoder社になにか言うのはお控え下さい。

Atcoder Regular Contest #011

ARC、今回、A〜Cの問題原案を作らせていただきました。楽しんでいただけたならば幸いです。http://arc011.contest.atcoder.jp/

Writer想定解法：AとBはやるだけです。Bは結構面倒かもしれませんが。Cは文字列を比較してグラフ作ってからのDijkstraで間に合う想定で作りました。

今回のB問題、C問題の原案(私作成)の原案は「不思議の国の論理学」(ルイス・キャロル著, 柳瀬 尚紀訳,2005, ちくま学芸文庫)を元にしています。興味のある方はご一読ください。 

今回のA問題は、「頭の体操」シリーズの煙草の問題。煙草の吸殻3本から煙草1本を作る男が17本の煙草を持ってる時に何本吸えるか、という問題を元にしています。私が文具が好きであることから、鉛筆に変えてみました。

以下、Writer解です。ソースやアルゴリズムが下手なのはご容赦ください。