A～BB, B～AA, AAA～(空文字), BBB～(空文字) と編集可能とする。

文字列SとTが与えられたときに、クエリS[a, b] T[c, d]が同値かどうか答えよ。

ただし、文字列が同値とは編集を繰り返して別の文字列にたどり着くことと定義する。

同値類の問題なので代表元を見つければよい。簡単なのはAだけで表される最短文字列。つまり全部Aにして、AAA～(空文字)を使って最短にしてしまえばよい。

ちなみにそういう同値類は空文字、A, AAの3種類しかない。

S[a, b] T[c, d]のような部分文字列がその3種類のいずれかを判定する必要があるが、

これはつまり区間[a, b]や区間[c, d」のAとBの数がカウントできれば、(A+B*2) mod 3が同値類になり、これの一致を見れば良い。

なのでBのところだけ1、あとは0であるような配列のRange sum queryをSegtree or BITで実装すると、クエリの応答がO(log(N))になり間に合う。

2017-04-09

AtCoder Regular Contest 071 D 井井井 / ###

arc071.contest.atcoder.jp

x軸に平行な直線がm本、y軸に平行な直線n本、あり、それぞれのy座標、x座標はy[i], x[j] である。これらの交点を使って任意の長方形を作る。そういう長方形の面積の総和を求めよ。

x軸とy軸で独立して考える。x[i]からx[i - 1]の間の領域が長方形の面積として使われる回数は、その領域が含まれる長さすべてで、左右の頂点の数を書ければよく、 i * (n - i) 通り。なので、(x[i] - x[i - 1]) * i * (n - i) の総和を求める。

y軸も同様にして総和を求め、x軸の和とかけると答え。

2017-04-09

AtCoder Regular Contest 071 F Infinite Sequence

arc071.contest.atcoder.jp

{1,…,n} からなる無限長の列 a₁,a₂,… のうち、次の条件を満たしているものは何通りあるでしょうか？

第 n 項から先はすべて同じ数である。つまり、n≤i,j ならば a_i=a_j を満たす。

どの正の整数 i に対しても、第 i 項の直後に並ぶ a_i 個の項はすべて同じ数である。つまり、 i<j<k≤i+a_i ならば a_j=a_k を満たす。

本番解けず。dp[k] = {k桁目から数字が連続する時の組み合わせ} を考える。

本番ではここでN桁目で残りk桁同じ場合、みたいなのを考えて解けなかった。

最初の2桁A Bに注目する。

A=1のとき、B以降はdp[k - 1]通り。
A≠1のとき、B≠1のとき、ABBBBB.... となる。(n-1)^2通り
A≠1のとき、B≡1のとき、A111(A個1が並ぶ)111XXXXX となる。

最後の場合は、更に次の場合に分ける。

A≧k - 1のとき A11111111... となる (k桁目以降は全部同じ数字) (N - k + 2)通り
A≦k - 2のとき A1111(A個1が並ぶ) ときて、その後はdp[k-A-1] 通り。

最後のは要はdp[1]からdp[k - 3]の和になる。これをsum[k-3]とかくと次の漸化式がたち解ける。

dp[k] = dp[k - 1] + (N - 1)^2 + sum[k-3] + (N - k + 2)

sum[k]は累積和でO(N)、dpの計算もO(N)であり、答えはdp[N]となる。

ここで注意だが、dp[1]=Nはよいのだが、dp[2]の場合、ケース「A≧k - 1」でAが1も許される。そのため一番最初のケースとダブルカウントになるためsum[k-3]のところは-1に置き換える必要がある。これを気づかなくてeditorialの漸化式がなかなか合わなかった。

2017-04-08

Google Code Jam 2017 Qualification Round(予選) が明日の朝8時から開催されます

code.google.com

予選ある程度プログラムが書ける人なら結構簡単で、しかも一日以上開催されてるのでぜひ参加してみましょう。具体的なスケジュールは以下ですが、デフォルトだとUTCで表示されてるので、右上のLocal Timeをクリックして現地時間で見てみると良いです。

ちなみに日本は2017/04/08の朝8時からスタートです。

code.google.com

2017-04-08

Yukicoder 502 階乗を計算するだけ

No.502 階乗を計算するだけ - yukicoder

n (0≦n≦10^18) のとき、n! (mod 10^9 + 7) を計算せよという問題。

普通にやるとn!の計算はO(n)かかる。nがmodの値(=10^9+7)以上のときは恒等的に0であるが、それでもO(10^9)で間に合わない。ちょっとしたテクニックとして、nがmodに近いときはウィルソンの定理 (p - 1)! ≡ -1 を使うと多少早くなるのだが、それでもオーダーが一桁減るか減らないかでどうしようもない。

結局解けなかったので解説を見ると、10^6 ごとの計算結果を10^3個保存しておき、途中から計算を始めるらしい(要は埋め込み)。処理計算量を空間計算量に置き換えるテクはよくあるんだがすっかり忘れてた。