D: Grid Coloring - AtCoder Regular Contest 080
H x Wのマス目をN色で塗り分けろ。ただし、色iのマスの数はa[i]であり、同じ色のマスは連結になるものとする。
塗り分け方は左上から真右にいって折り返しのときに一段下がって今度は左、みたいに雑巾で床掃除をするときのような感じでマスを順番に塗っていけば連結になる。あとは各色の数だけ愚直に色を塗ればよい。O(HW)。
C: 4-adjacent - AtCoder Regular Contest 080
数列a[i]が与えられる。並び替えて隣同士の積がかならず4の倍数にするようにできるか判定せよ。
数列の要素を p:4の倍数、q: 偶数であるが4の倍数でないもの、r: それ以外に分類する。 rの隣には必ずpの要素が必要である。また、qは q同士で並ぶ or pのとなりにいることが必要であるが、要はqの数が奇数であった場合のみ、pが1個必要になる。よって、r + q % 2 <= p であればYESである。ただし、qが存在しない時はrprprprみたいに並べることが可能なので、r + 1 <= p であればYES。
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)になりまにあう。
