久々に時間の都合がついたので参加。他の大会も含め、参加できる回数は減ってきていますが、それでも参加できるときは参加したい。
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点でした。問題はこちら。
[A,AC (C言語)]
[B,AC (C言語)]
[C,AC (C言語)]
0 件のコメント:
コメントを投稿