Codeforces Round #427 D. Palindromic characteristics
自然数kについて、k-palindromeを次の用に再帰的に定義する。
- 長さ1の文字は1-palindromeである。
- 文字列がk-palindrome ⇔ 文字列が回文になっている、かつ文字列の左半分(つまり右半分も)が(k-1)-palindromeである。
ただし、文字列の左半分とは長さ=[文字列の長さ/2]のプレフィックスのことである。
文字列sが与えられるので、次の長さ|s|の数列を作成せよ。
(sの部分文字列の中で1-palindromeの数, sの部分文字列の中で2-palindromeの数, ...)
定義どおりk-palindromeのkを再帰的に求める。文字列が回文でかつ、半分に割ってdfsした結果がk-1であれば、その文字列はk-palindromeになる。この結果をmemo[left][right]というテーブルでメモ化する。つまり、文字列の[left, right)に当たる部分文字列のkを入れていく。この時、回文判定をO(N)でやってしまうと、全体でO(N^3)かかり間に合わない。そこで、sとsの反転をつなげた文字列のローリングハッシュを作成しておき、回文判定をO(1)で行えるようにしておく。すると全体計算量がO(N^2)になり間に合う。
Codeforces Round #427 C. Star sky
最大100x100の領域に、n個の星が(x[i], y[i])に初期の明るさs[i]で配置されている。星の明るさの最大値はcであり、時間ごとに1づつ増えていき、cに到達すると次の時間に0に戻り、また1づつ増えていく、を繰り返す。この時、q個のクエリ (t[i], x1[i], y1[i], x2[i], y2[i]) 「時刻t[i]に於ける左上が(x1[i], y1[i]), 右下が(x2[i], y2[i])の長方形領域の星の明るさの合計値を求めよ」に応答せよ。
星をmod (c+1)で分類し、c+1個の2次元累積和を作成しておく。すると初期明るさv(0<=v<=c)の星の数がそれぞれO(1)で計算できる。この星は時刻t[i]の時点で(t[i] + v) % (c+1) であるので、結局クエリがO(c)で回答できる。全体ではO(qc)。
Codeforces Round #427 B. The number on the board
ある長い数字n(最大10万桁)について、すべての桁の合計はk以上であり、幾つかの桁が書き換えられた数字(桁数は同じ)が与えられる。最小で何桁書き換えられたとかんがえられるか?
与えられた書き換え済みの数字についてまずは桁の合計を計算する。これがk未満であれば、幾つかの桁を書き換えてkにする。この時、0の桁の数~9の桁の数をカウントし、0から順番に貪欲に書き換えていく。O(log n)。
Codeforces Round #427 A. Key races
2人がタイピングゲームをする。キーの送受信のレイテンシ及び一つのキーを押す時間と、課題の文字列の長さが与えられるのでどちらが勝つか判定せよ。
「レイテンシ * 2 + キーを押す時間 * 文字列の長さ」で比較するだけ。
C: 茶碗と豆 - AtCoder Regular Contest 038
位置iにある石を移動させるゲームを行う。位置iの石は左に1からC[i]の範囲で好きなだけ動かすことができる位置0にある石はそれ以上移動させることができない。先攻と後攻どちらが勝つか。
まずは位置iに石が1個ある時のGrundy数を愚直に計算する。位置0にある時、先攻の負けなのでGrundy数は0。あとは左から順にGrundy数を計算する。例えばgrundy数が{0, 1, 2} のとき、C[3]=2 ならば、一手勧めたときにあり得るGrundy数集合は{1, 2} であるから、この集合に含まれない最小の非負整数なので結局Grundy数は0になる。
さて、これを愚直に計算すると、石の数が1個の時Grundy数の1回の計算にO(N)の計算量が必要になる。そこで、インデックスがGrundy数を表し、そのGrundy数が最後に現れた石の位置を値に持つようなRMQを考える。すると、例えば[0, x)のminがi - C[i] 以上である時、すなわちGrundy数が [0, x) の範囲において、そのGrundy数が最後に現れたIndexが全てi - C[i] 以上である時、iにある石はいずれも [0, x)の範囲のGunrdy数を取ることが可能である。そこで、このようなxの上限を二分探索する。ただし、まだ1回も現れてないGrundy数の値は-1とする。すると、xがGrundy数になる。
このRMQをSegment Tree等で実装すると一回のGrundy数の計算がO(logN)になり、全体の計算量はO(N logN)になりまにあう。
E: Jigsaw - AtCoder Grand Contest 017
+字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か?
まず分かることは+と┴みたいなのは交互に来る必要があることがわかる。そこで、+の左の高さ(問題文でいうC)と┴の右の高さ(問題文でいうA)などが一致する、ということをグラフで表現する。高さと上に来る or 下に来るということを頂点として表し、n+ またはn-という頂点を作る。図形はそれぞれの形状に応じてn±とm±を結ぶエッジになる。また、下に来る頂点同士は常に接続可能なので連結にしておく。(図形でいうと┴を並べることに相当する) これらのことをUnionFindで確認し、全体が連結でない場合は不可能と判定する。
また、全体が連結であった場合でもある頂点に対して、右から接続する図形と左から接続する図形の数が合わない場合は不可能である。ただこの場合どちらかは┴型の図形なので、この図形よりも+型の図形の方が少ない、という判定のみでよい。
以上の条件ですべてNGと判定されなかった場合は可能と返す。O(N) (UnionFindを定数関数をみなすとだが)。
要は与えられた有向グラフがEulerグラフになっているかどうかの判定なんだとおもうけど、一般的なアルゴリズムでは計算量が間に合わない。そこで上のような方法を取る。
E: Awkward Response - AtCoder Regular Contest 078
公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。
n≤N かつ str(n)≤str(N)を満たす
n>N かつ str(n)>str(N) を満たす
この時、最大64回の質問でNを特定せよ。
まず分かるのはnにSuffix 000000... をつけておくと n>=N は必ず満たされるので文字列比較のみになり2分探索でnのあるprefixとNが一致するように特定することができる。ここではN<=10^9がわかっているので、10Nから100Nの範囲で探す。
その後、prefixの桁数を特定すればそれが答えである。Nが10の累乗の場合でない場合は、10^10, 10^9,...などと比較していくと、一番目の条件が一致した段階でちょうど桁数になっている。Nが10の累乗でない、というおのは探索したnの最上位の桁が1より大きい時と見ればよい。
Nが10の累乗の可能性があるとき、こちらは逆に9999999... と言った数字と比較する。すると2番目の条件で判定できる。O(logN)。