TopCoder SRM586
250
1 次関数をいくつかくっつけた形をした関数 f(x) がある。y = f(x) の解の個数の最大値を求めよ。無限にある場合は -1 を返せ。
500
いくつかの国があり、それぞれ異なる暦を使っている（互いにちょうど整数年ずれている）。各国での各王の在位期間も与えられる。「ある国のある王の時期と、他のある国のある王の時期が重なっている」という情報がいくつか与えられる。さらにこの形のクエリがいくつか与えられるので、クエリが与えられた情報に矛盾しないか判定せよ。
適当に暦の基準をおいてそこからの各暦のずれを考えると、各情報は差がある範囲内にないことを示している。これは最短路問題に帰着でき、クエリごとにそのクエリを情報にくっつけて、最短路問題を解き、負閉路がないか判定する。
1000
文字列の重さを「各文字について、文字列中のその文字の現れの最も右の位置 - 最も左の位置を考え、その和」とする。使える文字は [A-Z] である。文字列が light であるとは、同じ長さの文字列の中で最も重さが小さいことを言う。
今、i = 0, 1, ... に対して長さ L[i] の light な文字列を作り、それを順につなげたものを考える。つなげてできる文字列の重さの最小値を求めよ。
文字列が light である条件は、「min(26, L[i]) 種類使っている」かつ「同じ文字は連続している」である。つなげた文字列を考えるときは、実は前者だけ考えればよい（後者に反したところで足を引っ張るだけなのでうれしくない）。
ここで各文字ごとに [位置][使用中の文字数][使用して前の文字列までで捨てた文字数][使用して今の文字列で捨てた文字数] をキーに DP する。（一番左の文字が出てきたら使用を開始し、使用の終了は一番右の文字を出すことに相当する）次の文字に移るときには、使用中の文字数だけのコストがかかる。次の文字列に移る時、「使用中の文字数」「使用して今の文字列で捨てた文字数」を足して min(26, L[i]) になればよい。
結果
いつも通り「あたしのいくじなし〜＞＜」
easy 落ちた＞＜
xoo 799.08 (5 位)
rating: 2973 -> 3027 target!!!
