Regionals 2010 :: Europe - Central

Live Archive

LiveArchive
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=395
解説
http://cepc10.ii.uni.wroc.pl/solutions.html

4973 - Ardenia

4974 - Beasts

4975 - Casting Spells

問題

文字列が与えられるので、その部分文字列で、ww^Rww^Rを満たすもので最大の長さを求めよ。

解法

条件を満たすものは部分文字列は全体で回文になっている。
それぞれのiで回文半径をManacherのアルゴリズムで求める。
その後は以下のようにする。

    int ans = 0;
    set<int> se;
    priority_queue<pii> discard;
    REP(i, n) {
      while(!discard.empty()) {
        pii p = discard.top();
        if (-p.first < i) {
          se.erase(se.find(p.second));
          discard.pop();
        } else break;
      }
      set<int>::iterator it = se.lower_bound(i-r[i]/2);
      if (it != se.end()) {
        int j = *it;
        ans = max(ans, (i-j)*4);
      }
      se.insert(i);
      discard.push(pii(-i-r[i], i));
    }

各iに対して、[i-r[i]/2,i-1]に含まれ、j+r[j]>=iを満たすようなjを求める。
この4*(i-j)がそのiに対する最大の解となる。

4976 - Defense Lines

問題

数列が与えられる。
１つの部分連続列を取り除いて出来る新しい数列の、増加部分連続列の長さの最大を求めよ。

解法

starting[i]とending[i]を、それぞれiで始まるような最長増加部分連続列の長さ、iで終わるような最長増加部分連続列の長さとする。
数列をv[i]とする。
それぞれのiに対して、kending[j]を満たすとき、(v[j],ending[j])はとっておく意味が全くないことである。
このようなものはsetに入れないようにし、このようなものが生じたらsetから消すようにする。
このとき、v[i]に対してsetの中でv[k]

4977 - Enter The Dragon

問題

湖の数nと、m日間どの湖に雨が降ったかの情報（どこにも降らないならなら0）が与えられる。
最初湖には水が満たされている。
満たされた状態の湖に雨が降ると溢れてしまう。
龍は晴れの日に１つの湖の水を飲み干すことが出来る。
m日間、湖を溢れさせないようにすることが出来るならYESと、龍が晴れの日にそれぞれどの湖を飲み干せばよいかを出力し、
出来無いならNOを出力せよ。

解法

満たされた状態で雨が降るような湖があるとき、その間の晴れの日で龍はその湖の水を飲み干さなければならない。
さらに、日にちを前からなめたとき、まだ龍がどの湖を飲み干すか決まっていない晴れの日の中で、一番早い晴れの日で飲むようにすればいいことが分かる。
これはsetとlower_boundを使えば出来る。
setには晴れの日の日にちを入れる。
飲み干すこと決めたらその日をsetから取り除く。

4978 - Fields and Farmers

問題

n個の点が与えられる。
図のように、その点集合に対する領域を作ることを考える。
n個の点集合の部分集合で、n個の点集合が作る領域と同じになるようなものの数を求めよ。

解法

領域の境界は、軸に平行か斜め45度になる。
よってx,y,x+y,x-yそれぞれのminとmaxが領域を決めることが分かる。
この8つの値をキーと呼ぶことにする。
すなわち問題は、部分集合の中で、キーが全体の集合と変わらないものの数を求めることになる。
包徐原理が使える。
単純に考えると、計算量がO(2^8*10^6)になってしまう。
そこで、
A[S]=キー集合Sの各要素とそれ自身の座標が等しいような点の個数
という2^8の配列を作ることにより、O(2^8*2^8)にすることができる。

4979 - Game

問題

5×5の盤面で3目並べをした結果の盤面が与えられるので、どちらが勝ったか、もしくは引き分けかを判定せよ。
両者とも３目並べている場合と両者とも３目並べていない場合に引き分けとなる。

解法

やるだけ。

4980 - Hanging Hats

4981 - Insults

問題

aeとioをinsultとする。w1とw2がinsultならば、w1w2、aw1e、iw1oもinsultである。
入力がinsultであるか判定し、insultであるなら同じ長さで辞書順で次のinsultを出力せよ。
ただし、その長さで辞書順最後のinsultなら出力はULTIMATEとする。

解法

まずinsultかどうかの判定は、括弧の対応が正しいかを判定するときのようにスタックを使えば出来る。
解説の通り、辞書順で次のinsultを見つけるために順番に試すべきprefixがわかる。
そのprefixでinsultに出来るなら、a...ae...eを出来るだけ使ったあとinsultになるようにしたものが答えとなる。
これをO(n)でやるために、文字列を後ろから見ていって文字をstackに入れながら（その時点で対応が無い文字がstackに残る）次のinsultを作れるかどうか調べる。
はじめinsultを作れるか調べるときstackをコピーしていたのでTLEになったが、１つのstackだけ使うようにしたら通った。

4982 - Justice for All