Educational Codeforces Round 48 参加記録

Dashboard - Educational Codeforces Round 48 (Rated for Div. 2) - Codeforces

初めてのこどふぉ参戦！

結果はA～Dの4完で478位でした。

f:id:betrue12:20180811155629p:plain

1問ずつ振り返っていきます。

A. Death Note

英語よりも、一番下のNoteを見ると分かりやすいです。1を $a_{1}$ 個、2を $a_{2}$ 個…というのを各ページに $m$ 個区切りで書いていきます。そのとき、それぞれの数字を書く際に何回ページをめくりますか、という問題。 ただし、「ちょうど書き終わった」時にもページをめくるものとします。*1

$m$ 個書くたびにページをめくるので、累積で $x$ 個目の数字を書いた後のページは $floor[\frac{x}{m}$ ] ページ目になります。累積和を計算して、それぞれの数字を書く前と後のページ数で差を取ればよいです。

ACコード：Submission #41161044 - Codeforces

1問目から英語に手こずるという…もしサンプルが「ちょうど書き終わった」時の処理を含んでいなかったら、それに気付かずWA地獄になっていたと思います…。

B. Segment Occurrences

Problem - B - Codeforces

文字列 $s, t$ が2つ与えられ、クエリで $s$ の範囲が指定されるので、その範囲から連続部分文字列として $t$ が取れる箇所はいくつあるか、という問題。

「 $s$ の $i$ 文字目から $i+M-1$ 文字目までが $t$ と一致するか」は前計算できます。全箇所調べるのに $O(nm)$ かかりますが、 $10^{6}$ くらいなので間に合います。

この前計算の結果を使ってクエリを処理するのですが、そのままやると $O(nq)$ 。 $10^{8}$ くらいなので速い言語だとこのまま通りそう…？ですが、累積和を取っておけば高速化できます。

クエリの範囲が狭すぎる場合はちゃんと別で処理してあげないとマイナスとかになるので気をつけましょう（2敗、ひどい）

本番ACコード：Submission #41169639 - Codeforces
ちょっと書き直したコード：Submission #41196250 - Codeforces

C. Vasya And The Mushrooms

Problem - C - Codeforces

ゴリゴリ実装しましたが、どう解くのがスマートなんだろう…

まず、可能な動きのパターンを整理します。全部のマスを1回ずつ通らないといけないという制約から、動きのパターンは以下のようなものに限定されます。

f:id:betrue12:20180804110723p:plain

実際に可能な動きのパターンは全部で $n$ 通りあります。意外と少ないですが、各経路を毎回計算していると $O(n^{2})$ かかってアウトなので高速化します。

まず、横Uターンの経路の得点をそれぞれ前計算しておきます。そして、「途中まで縦ジグザグした後に、横Uターンする」時の得点を、縦ジグザグを1手ずつ進めながら計算していきます。

縦ジグザグ部分の得点は、順次足し算をしていけばよいです。そして横Uターンの得点は、「縦ジグザグを進めることで、横Uターン部分の得点はどう変化するか？」を考え、差分だけ更新していきます。

f:id:betrue12:20180804112637p:plain

縦ジグザグを進めた際に、横Uターンの得点は

既に通過した点から得られるはずだった得点が得られなくなる。
通過していない点は、通るのが先延ばしになるため、倍率が増える。*2

と変化します。それぞれの差分が分かれば、横Uターン部分の得点が計算できそうです。

まず「通過していない点は、通るのが先延ばしになるため、倍率が増える」については、通過していない点の $a_{i}$ または $b_{i}$ の合計を持っておけば、それを足すことで実現できます。最初に全部足した値を持っておいて、通過した点を順次引いていきましょう。

次に「既に通過した点から得られるはずだった得点が得られなくなる」ですが、これを正しく除くには「その時点で、その点が何倍として扱われているか」を知っている必要があります。このとき、前述の「倍率が増える」操作も考慮する必要があります。最初に横Uターンの得点を計算した時点で何倍として扱われて、そこから何回倍率が増やされたか、を管理しておけばよいです。

前計算しておけば1回1回の計算は $O(1)$ なので全体で $O(n)$ のはずなんですが…Rubyだと時間ギリギリですね…