cafelier@SRM

ACM-ICPC 2012 Tokyo Regional 問題F, I

その他 | 23:42 |

ACM-ICPC 2012 アジア地区予選 の問題FとIを解いてみたよ。

F

• 「物体xと物体yの重さの差はwグラムです」という形式の報告と「物体xと物体yの重さの差はいくつ？」という形式の質問がたくさん来ます。質問にそのたびに答えを返しなさい。
  • x+5=y, y+10=z みたいなのが報告済みなら「xとzの差は？」に15と答えないといけません。
  • わからないときは "UNKNOWN" と答えれてよい。

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

typedef int Node, Weight;

struct UnionFind
{
   vector< pair<Node, Weight> > uf; // <parent, offset_from_parent>

   UnionFind(int N)
   {
      for(int i=0; i<N; ++i)
         uf.push_back(make_pair(i, 0));
   }

   // Returns <root, offset_from_root> while compressing the path.
   pair<Node, Weight> Find(int a)
   {
      if(uf[a].first != a) {
         pair<Node, Weight> p = Find(uf[a].first);
         uf[a] = make_pair(p.first, uf[a].second+p.second);
      }
      return uf[a];
   }

   void Union(int a, int b, Weight b_minus_a) // [a] + b_minus_a = [b]
   {
      pair<Node, Weight> aa = Find(a); // [aa.first] + aa.second = [a]
      pair<Node, Weight> bb = Find(b); // [bb.first] + bb.second = [b]
      // Then, [bb.first] + (bb.second - b_minus_a - aa.second) = [aa.first]
      if( aa.first != bb.first )
         uf[aa.first] = make_pair(bb.first, bb.second - b_minus_a - aa.second);
   }
};

int main()
{
   for(int N,Q; cin>>N>>Q,N|Q; )
   {
      UnionFind uf(N);
      while( Q --> 0 ) {
         char cmd; int a,b; cin>>cmd>>a>>b; --a,--b;
         if(cmd == '!') {
            int w; cin>>w;
            uf.Union(a,b,w);
         } else {
            pair<Node, Weight> aa = uf.Find(a), bb = uf.Find(b);
            if(aa.first != bb.first)
               cout << "UNKNOWN" << endl;
            else
               cout << (bb.second - aa.second) << endl;
         }
      }
   }
}

• UNKNOWNかそうでないかは、報告された関係で繋がっているかどうかでわかるので、同値類分類、いわゆる Union-Find データ構造で解けます。
• で、KNOWN の時に具体的な差の値を返さないといけないんですが、こういう類いの"差"の情報はUnion-Findのedgeに乗せてやることができます。
  • 大抵の人は Union-Find は同値類関係を判定するだけの分類処理としてライブラリ化していると思うので、それを果たしてちゃんと拡張できるかどうか、的な問題

union-findの枝に情報を載せるんじゃなくて、各物体の「仮の」重さを決めておいて、factの報告が来て矛盾していたら、依存関係の小さい方の「仮の」重さを調整する、みたいな方法もありです（Union-Findのバランス木を使ってO(n log n)にする方法と実質的に同じです。）

I

• 単語の列を決まった幅の紙面にレイアウトしたい。単語間空白の最大幅ができるだけ小さくなるように改行位置を決定せよ。

これは「最大値の最小化にぶんたんさく」というルビを振って二分探索で解いてもいいんですがとりあえず O(n) 解。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int solve(const int W, const vector<int>& x)
{
   const int N = x.size();

   // xsum[k] := Σ x[0..k)
   vector<int> xsum(1, 0);
   for(int k=0; k<N; ++k)
      xsum.push_back(xsum.back()+x[k]);

   // DP高速化のための準備
   int line_start = 0;
   vector<int> next_smaller(N, 0);
   stack<int> no_next_smaller; no_next_smaller.push(0); // (番兵)

   // dp[k] := 単語 x[k] が行頭に来るように x[0..k) を最適配置した場合のそこまでの最適解
   vector<int> dp(N); dp[1] = W;
   for(int k=2; k<N; ++k)
   {
      // line_start := 直前の行の行頭になり得る一番最初の単語
      while(xsum[k]-xsum[line_start]+(k-line_start-1) > W)
         ++line_start;

      dp[k] = W;
      for(int ls=line_start; ls+1<k;) {
         // s := x[ls..k) を一行に配置したときの、その行の最大連続空白
         int s = (W-(xsum[k]-xsum[ls])-1)/(k-ls-1) + 1;

         // DP表の更新
         dp[k] = min(dp[k], max(dp[ls],s));
         if(dp[ls] <= s) {
            // lsを増やすとsは広義単調増加するので、
            // これ以上回してもdp[k]が更新されることはない。おしまい
            break;
         } else {
            // ここに来るとき、dp[line_start..ls) >= dp[ls] > s である。
            // さて、x[ls..k) より x[ls..k+1) の方が一行に配置したときの空白"s"は小さい。
            // なので、次周で dp[k+1] を埋めるときも max(dp[ls],s) の値を支配するのは
            // dp[ls] の方なので、dp[line_start..ls) のゾーンは見る必要がない
            line_start = ls;

            // lsを増やすとsは広義単調増加するので、
            // dp[ls]が小さくなるとこまで行かないとdp[k]は更新されない。じゃんぷ
            if( !(ls=next_smaller[ls]) )
               break; // なかった
         }
      }

      // next_smaller の更新
      for(; dp[no_next_smaller.top()]>dp[k]; no_next_smaller.pop())
         next_smaller[no_next_smaller.top()] = k;
      no_next_smaller.push(k);
   }

   // 最終行が単語 x[k] から始まる場合
   int best = W;
   for(int k=0; k<N; ++k)
      if( xsum[N]-xsum[k]+(N-k-1) <= W ) {
         int s = (k+1==N ? 0 : 1);
         best = min(best, max(dp[k], s));
      }
   return best;
}

int main()
{
   for(int W, N; cin>>W>>N, W|N; ) {
      vector<int> x(N);
      for(int i=0; i<N; ++i)
         cin >> x[i];
      cout << solve(W, x) << endl;
   }
}

next_smallerなしでもなんとかなる気もするんですが、はてさて。

まあでも、そんなに頑張らなくても二分探索＋しゃくとり法で O(|x| log W) で解けます。

#include <iostream>
#include <vector>
using namespace std;

bool is_possible(const int W, const vector<int>& x, const int MaxSpace)
{
   // CanStartLine[k] := 単語 x[k] から後ろを空白幅MaxSpace以下でレイアウトできますか
   vector<bool> CanStartLine(x.size());

   int CanStartCnt = 0;
   int TightWidth = -1,        TightNextStart = x.size();
   int LooseWidth = -MaxSpace, LooseNextStart = x.size();

   for(int k=x.size()-1; k>=0; --k) {

      // LooseNextStart := (x[k]+MaxSpace+...+MaxSpace+x[e] >= W になる最小の e+1)
      // LooseWidth     := その時の x[k]+MaxSpace+...+MaxSpace+x[e]

      LooseWidth += x[k] + MaxSpace;
      while( W <= LooseWidth - (x[LooseNextStart-1]+MaxSpace) ) {
         LooseWidth  -= x[--LooseNextStart] + MaxSpace;
         CanStartCnt += (CanStartLine[LooseNextStart] ? 1 : 0);
      }

      // TightNextStart := (x[k]+1+...+1+x[e] > W となる最小の e+1)
      // TightWidth     := その時の x[k]+1+...+1+x[e]

      TightWidth += x[k] + 1;
      while( W < TightWidth - (x[TightNextStart-1]+1) ) {
         TightWidth  -= x[--TightNextStart] + 1;
         CanStartCnt -= (CanStartLine[TightNextStart] ? 1 : 0);
      }

      // x[k] が最初の１単語だとすると、
      // 次の行の先頭に来れる単語は [LooseNextStart, TightNextStart) のどれか＆どれでも。
      // CanStartCnt := その範囲にある CanStartLine の true の個数。

      CanStartLine[k] = TightWidth<=W || CanStartCnt>0;
   }

   return CanStartLine[0];
}

int solve(const int W, const vector<int>& x)
{
   // 許す最大空白幅を二分探索
   int L=0, R=W; // (L,R]
   while( R-L>1 )
      (is_possible(W, x, (L+R)/2) ? R : L) = (L+R)/2;
   return R;
}

int main()
{
   for(int W, N; cin>>W>>N, W|N; ) {
      vector<int> x(N);
      for(int i=0; i<N; ++i)
         cin >> x[i];
      cout << solve(W, x) << endl;
   }
}

しゃくとりの替わりに累積和上の二分探索やBITなどなどでもう一個 O(log W) を掛けても間に合うようです。

別解。計算量的に謎だけどジャッジデータは余裕で通る。

#include <iostream>
#include <vector>
using namespace std;

bool is_possible(const int W, const vector<int>& x, const int MaxSpace)
{
   // x[i] が置かれることがあり得る column の全リスト
   vector< pair<int,int> > range; // 重なりのない閉区間のリストとして保持
   bool CanStartLine = true;      // ただし [0,0] だけ特別扱いする

   for(int i=0; i+1<x.size(); ++i) {
      // x[i+1] の可能性をさぐる
      vector< pair<int,int> > range2;
      bool CanStartLine2 = false;
      for(int k=(CanStartLine ? -1 : 0); k<(int)range.size(); ++k)
      {
         int L = (k==-1 ? 0 : range[k].first);
         int R = (k==-1 ? 0 : range[k].second);

         // x[i] で行を終えることが可能なら x[i+1] は行頭に来れる
         if( L<=W-x[i] && W-x[i]<=R )
            CanStartLine2 = true;

         // x[i]が[L,R]に置かれるなら次の単語は[L+x[i]+1, R+x[i]+MaxSpace]である
         L += x[i] + 1;
         R += x[i] + MaxSpace;
         R = min(R, W-x[i+1]); // でもあんまり右には置けないよ
         if( L <= R )
            range2.push_back(make_pair(L,R));
      }

      // rangeがLでソート済みならrange2もそうであることに注意。
      // range2に突っ込まれた区間をできるだけマージする
      CanStartLine = CanStartLine2;
      range.clear();
      for(int k=0,e; k<range2.size(); k=e)
      {
         int L = range2[k].first;
         int R = range2[k].second;
         for(e=k+1; e<range2.size(); ++e)
            if(range2[e].first <= R+1)
               R = max(R, range2[e].second);
            else
               break;
         range.push_back(make_pair(L,R));
      }
   }

   // どこでもいいけど最後の単語がどっかに置ける可能性があるならOK
   return (CanStartLine || !range.empty());
}

int solve(const int W, const vector<int>& x)
{
   // 許す最大空白幅を二分探索
   int L=0, R=W; // (L,R]
   while( R-L>1 )
      (is_possible(W, x, (L+R)/2) ? R : L) = (L+R)/2;
   return R;
}

int main()
{
   for(int W, N; cin>>W>>N, W|N; ) {
      vector<int> x(N);
      for(int i=0; i<N; ++i)
         cin >> x[i];
      cout << solve(W, x) << endl;
   }
}

先頭行から割と素直に単語を配置していく感じですが、MaxSpace=1 の時は配置が一意に決まりますし、MaxSpace>1 の時は行の後ろの方にいくにつれ可能な区間の幅が伸びていくことを考えると、区間のdisjointなリスト range の長さは高々 √W にしかならないので、O(|x|・√W・log W) には少なくともなっていて、実際にはもっと低く抑えられる気がしています。