ICPC 2011 模擬地区予選

今日チャレンジしました。
時間は考えずにまったりやった。最後のほうは英語読みたくない病が発症した。
全体としては実装ゲーというよりは発想ゲーで好みな感じの問題が多かった。
参加はしてませんが、主催の方々お疲れ様でした。

A : In nity Maze

自分の場所と方角で100 * 100 * 4通りしか状態がないので、いつかはループに入る。
ループ見つけて末尾をごにょごにょするだけ。

typedef long long ll;

#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

using namespace std;

const int _dx[] = { 0, 1, 0,-1};
const int _dy[] = {-1, 0, 1, 0};
int dir[256];

enum DIR{
  NORTH = 0,
  EAST  = 1,
  SOUTH = 2,
  WEST  = 3
};

string g[100];
int memo[100][100][4];
int h, w;
ll l;
string dir2str = "NESW";


bool cango(int x, int y, int d){
  int xx = x + _dx[d];
  int yy = y + _dy[d];

  return ISIN(xx, yy, w, h) && g[yy][xx] == '.';
}

int main(){
  dir['N'] = NORTH;
  dir['E'] = EAST;
  dir['S'] = SOUTH;
  dir['W'] = WEST;

  while(cin >> h >> w >> l, h + w + l){
    int sx, sy, sd;

    REP(i,h) cin >> g[i];

    REP(i,h) REP(j,w){
      if(g[i][j] != '.' && g[i][j] != '#'){
        sx = j; sy = i; sd = dir[g[i][j]];
        g[i][j] = '.';
      }
      REP(k, 4) memo[i][j][k] = -1;
    }

    for(ll turn = 0; turn < l; turn++){
      REP(k, 4){
        if(cango(sx, sy, sd)) break;
        sd = (sd + 1) % 4;
      }

      sx += _dx[sd];
      sy += _dy[sd];

      if(memo[sy][sx][sd] == -1){
        memo[sy][sx][sd] = turn + 1;
      }else{
        int cycle = (turn + 1) - memo[sy][sx][sd];
        ll tmp = (l - (turn + 1)) % cycle +  memo[sy][sx][sd];

        REP(i,h) REP(j,w) REP(k,4){
          if(memo[i][j][k] == tmp){
            sx = j; sy = i; sd = k;
            goto end;
          }
        }
      end:;
        break;
      }
    }

    cout << sy + 1 << " " << sx + 1 << " " << dir2str[sd] << endl;
  }

  return 0;
}

B : Buttery

たぶん一番簡単な問題かなー。
デート情報をビットで持っておくと、論理積が0かどうかでデートが被るかがわかる。
あとはDP。実装ものすごい楽でよかった。

const int MAX = 21 - 6 + 1;
long long memo[1 << MAX];
int l[100];
int mask[100];

int main(){
  while(int n = getInt()){
    long long ans = 0;

    memset(memo, 0, sizeof(memo));

    REP(i,n){
      int m = getInt();
      l[i] = getInt();
      mask[i] = 0;

      REP(k,m){
        int s = getInt();
        int e = getInt();

        for(int j = s; j < e; j++){
          mask[i] |= (1 << (j - 6));
        }
      }
    }

    REP(i, (1 << MAX)){
      ans = max(ans, memo[i]);
      REP(j, n) if((i & mask[j]) == 0){
        memo[ i | mask[j] ] = max( memo[ i | mask[j] ], memo[i] + l[j] );
      }
    }

    cout << ans << endl;
  }

  return 0;
}

C : Chinese Classics

なんかTwitter見てた感じ物議をかもしていたっぽい。
読んでみるとたしかに曖昧な部分が。
まあ曖昧さが(多分)2通り程度なので、両方試せばいいかーくらいのノリ。
最初はゴリ押しでやっていたがあまりうまく行かない感じだったので、
読む順番をグラフ状に表す実装に方針転換した。

vector<vector<int> > next;
vector<vector<int> > pnext;
vector<string> str;

void print(int i){
  // cout << i + 1 << " " << str[i] << endl;
  cout << i + 1 << endl;
  REP(j, next[i].size()) print(next[i][j]);
  REP(j, pnext[i].size()) print(pnext[i][j]);
}

int main(){
  while(int n = getInt()){
    map<string, int> label;
    str = vector<string>(n);
    next = vector<vector<int> >(n);
    pnext = vector<vector<int> >(n);

    REP(i,n) cin >> str[i];

    int prev = -1;
    int start = -1;
    REP(i,n){
      if(str[i] == "-"){
        if(prev == -1){
          start = i;
        }else{
          pnext[prev].push_back(i);
        }
        prev = i;
      }else{
        if(str[i][str[i].size() - 1] == 'v')
          next[i + 1].push_back(i);

        if(str[i].size() > 1){
          char buff[32]; int id;
          sscanf(str[i].c_str(), "%[a-z]%d", buff, &id);
          if(id == 1){
            if(str[i][str[i].size() - 1] != 'v'){
              if(prev == -1){
                start = i;
              }else{
                pnext[prev].push_back(i);
              }
              prev = i;
            }

            if(label.count(buff)){
              next[i].push_back(label[buff]);
              label.erase(label.find(buff));
            }
          }else{
            if(label.count(buff)){
              next[i].push_back(label[buff]);
            }
            label[buff] = i;
          }
        }
      }
    }

    print(start);
    // cout << endl;
  }
  return 0;
}

D : Revenge of Champernowne Constant

過去問にChampernowne Constant的なのがあったのでそのリベンジですね、わかります。
あの過去問には手こずった・・・。
解き方はおそらく矛盾がないように分割が何通りかあって、分割毎に現れる位置を計算して、その最小値を取るのだと思われる。
ものすごい実装ゲーを感じたので諦めた。

E : Full Text Search

なんかグラフ上でDPとかそんな感じかなー。
もしくはフローになおせるか。
よく分からん。
読んだ時には力尽きてたので諦め。

F : Mysterious Maze

A問題のアレンジ。
自分の位置と方向についてダイクストラ
コストは曲がる命令の位置。
多分最初に前処理で任意の方向に行くための曲がる回数を計算しておかないとTLEと思われる。

#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

using namespace std;

const int _dx[] = { 0, 1, 0,-1};
const int _dy[] = {-1, 0, 1, 0};

enum DIR{
  NORTH = 0,
  EAST  = 1,
  SOUTH = 2,
  WEST  = 3
};

string s;
string g[1000];
int memo[1000][1000][4];
int nextdir[1000010][4];
int w, h, n;

bool cango(int x, int y, int d){
  int xx = x + _dx[d];
  int yy = y + _dy[d];

  return ISIN(xx, yy, w, h) && g[yy][xx] == '.';
}

struct data{
  int x;
  int y;
  int d;
  int cnt;

  data(int a, int b, int c, int e) : x(a), y(b), d(c), cnt(e) {}
};

bool operator < (const data &lhs, const data &rhs){
  return lhs.cnt > rhs.cnt;
}

int main(){
  while(true){
    h = getInt();
    w = getInt();
    n = getInt();

    int sx, sy, sd = NORTH;
    int gx, gy;

    if(h + w + n == 0) break;

    cin >> s;

    REP(i,h){
      cin >> g[i];

      REP(j,w){
        if(g[i][j] == 'S'){
          sx = j; sy = i; g[i][j] = '.';
        }else if(g[i][j] == 'G'){
          gx = j; gy = i; g[i][j] = '.';
        }
      }
    }

    memset(memo, -1, sizeof(memo));

    for(int i = n - 1; i >= 0; i--){
      REP(j,4) nextdir[i][j] = n + 2;

      nextdir[i][s[i] == 'L' ? 3 : 1] = i + 1;
      nextdir[i][0] = i;
      if(i != n - 1){
        REP(j,4){
          int k = (j + (s[i] == 'L' ? 3 : 1)) % 4;
          nextdir[i][k] = min(nextdir[i][k], nextdir[i + 1][j]);
        }
      }
    }

    bool ans = false;
    priority_queue<data> pq;
    pq.push(data(sx, sy, sd, 0));

    while(pq.size()){
      data dt = pq.top(); pq.pop();
      int x = dt.x;
      int y = dt.y;
      int d = dt.d;
      int cnt = dt.cnt;

      if(memo[y][x][d] != -1) continue;
      memo[y][x][d] = cnt;

      if(cnt != n){
        REP(i,4) if(nextdir[cnt][i] != n + 2){
          int dd = (d + i) % 4;
          if(memo[y][x][dd] == -1) pq.push(data(x, y, dd, nextdir[cnt][i]));
        }
      }

      while(cango(x, y, d)){
        x += _dx[d]; y += _dy[d];
        if(gx == x && gy == y){ ans = true; goto end; }
        if(cnt != n){
          int nextd = (d + (s[cnt] == 'L' ? 3 : 1)) % 4;
          if(memo[y][x][nextd] == -1){
            pq.push(data(x, y, nextd, cnt + 1));
          }
        }
      }
    }

  end:;
    puts(ans ? "Yes" : "No");
  }

  return 0;
}

G : Number Sorting

これは面白い問題だった。
はじめに辞書順ソートしておくのはいいとして、それからどうするか・・・。
dp[i] := 最後がiで終わるような集合の個数
とすると、最後がiで終わるのは、空に自分を付け足すかor自分より小さいのが最後に来てるのに付け足すか のいずれかなので、
dp[i] = 1 + Σdp[j] (j < i)
のように計算できる。
これだと計算量が100000 * 100000くらい。間に合わない。
BITを使うと確か総和求められたなぁ→蟻本カンニング
これで100000 * log100000くらいなので間に合う。

string to_str(int a){ stringstream ss; ss << a; return ss.str(); }

int mod;

template<class T>
class BIT{
  vector<T> data;
  size_t n;
public:
  BIT(size_t nn) : data(vector<int>(nn + 1)), n(nn) {}

  T sum(int i){
    T s = (T)0;
    i++;
    while(i > 0){
      s += data[i]; s %= mod;
      i -= i & -i;
    }
    return s;
  }

  void add(int i, T x){
    i++;
    while(i <= (int)n){
      data[i] += x; data[i] %= mod;
      i += i & -i;
    }
  }
};

int main(){
  while(true){
    int a = getInt();
    int b = getInt();
    int p = getInt(); mod = p;

    if(a + b + p == 0) break;

    vector<string> v(b - a + 1);
    vector<int> num(b - a + 1);
    BIT<int> bit(b - a + 2);

    REP(i, b - a + 1) v[i] = to_str(a + i);
    sort(v.begin(), v.end());
    REP(i, b - a + 1) num[i] = atoi(v[i].c_str());

    bit.add(0, 1);
    REP(i, b - a + 1){
      bit.add(num[i] - a + 1, bit.sum(num[i] - a));
    }

    cout << (p + bit.sum(b - a + 1) - 1) % p << endl;
  }
  return 0;
}

H : Sky Jump

力尽きた、読んでない。

I : Mobile Network

多項式のフローだと・・・!?
でも次数ごとに見ていけば良いだけのような・・・→でもそれより上の次数が余ってる場合には無限に流せる。
本当に合ってるか不安だったけど実装したら通った。
正直入力のパースと出力の整形が一番難しかった。

struct Edge{
  int cap; // capacity
  int to;
  int rev; // reverse edge id
  int id;
  Edge(){}
  Edge(int c, int t, int r, int i) :
    cap(c), to(t), rev(r), id(i){}
};

template<class E> // Edge type
class Graph{
public:
  typedef std::vector<std::vector<E> > G;

private:
  G g;

public:
  Graph(int n) : g(G(n)) {}

  void addEdge(int from, int to, int cap, int id){
    g[from].push_back(E(cap, to, g[to].size(), id));
    g[to].push_back(E(cap, from, g[from].size() - 1, id));
  }

  G &getRowGraph(){
    return g;
  }
};

template<class E>
class Dinic{
  typedef typename Graph<E>::G G;
  G &g;
  std::size_t n; // size of graph

  std::vector<int> level;
  std::vector<int> iter;

  // search length of shortest path from s
  void bfs(int s){
    std::queue<int> que;
    level = std::vector<int>(n, -1);

    level[s] = 0;
    que.push(s);

    while(!que.empty()){
      int v = que.front(); que.pop();
      for(int i = 0; i < (int)g[v].size(); i++){
        E &e = g[v][i];
        if(e.cap > 0 && level[e.to] < 0){
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
    }
  }

  // search path
  int dfs(int v, int t, int f){
    if(v == t) return f;
    for(int &i = iter[v]; i < (int)g[v].size(); i++){
      E &e = g[v][i];
      if(e.cap > 0 && level[v] < level[e.to]){
        int d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
          e.cap -= d;
          g[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

public:
  Dinic(Graph<E> &graph) : g(graph.getRowGraph()){
    n = g.size();
  }

  // Max flow of the flow from s to t.
  int solve(int s, int t){
    int flow = 0;
    while(true){
      int f;
      bfs(s);
      if(level[t] < 0) return flow;
      iter  = std::vector<int>(n, 0);
      while((f = dfs(s, t, INT_MAX)) > 0){
        flow += f;
      }
    }
  }
};

template<class E>
int dinic(Graph<E> &g, int s, int d){
  return Dinic<E>(g).solve(s, d);
}

vector<string> split(string str, char sp){
  vector<string> ret;

  while(str.find(sp) != string::npos){
    int pos = (int)str.find(sp);

    ret.push_back(str.substr(0, pos));
    str = str.substr(pos + 1);
  }
  ret.push_back(str);

  return ret;
}

int main(){
  int n, m;
  while(cin >> n >> m, n + m){
    vector<int> u(m);
    vector<int> v(m);
    vector<vector<int> > p(m, vector<int>(51));

    REP(i,m){
      string str;
      cin >> u[i] >> v[i] >> str;
      u[i]--; v[i]--;

      vector<string> tmp = split(str, '+');

      REP(j, tmp.size()){
        int a, l;
        if(tmp[j].find('x') != string::npos){
          if(tmp[j][0] == 'x'){
            if(tmp[j].find('^') != string::npos)
              sscanf(tmp[j].c_str(), "x^%d", &l);
            else
              l = 1;
            a = 1;
          }else{
            if(tmp[j].find('^') != string::npos)
              sscanf(tmp[j].c_str(), "%dx^%d", &a, &l);
            else{
              sscanf(tmp[j].c_str(), "%dx", &a);
              l = 1;
            }
          }
        }else{
          l = 0;
          sscanf(tmp[j].c_str(), "%d", &a);
        }
        // cout << tmp[j] << " : " << a << " " << l << endl;
        p[i][l] = a;
      }
    }

    vector<int> ans(51);
    vector<bool> inf(m);
    for(int i = 50; i >= 0; i--){
      Graph<Edge> g(n);

      REP(j,m){
        int cap = inf[j] ? (1 << 30) : p[j][i];

        if(cap > 0){
          g.addEdge(u[j], v[j], cap, j);
        }
      }

      ans[i] = dinic(g, 0, n - 1);

      const vector<vector<Edge> > &gg(g.getRowGraph());
      vector<int> tmp(m);
      REP(k,gg.size()){
        REP(j,gg[k].size()){
          if(gg[k][j].cap > 0){
            tmp[gg[k][j].id]++;
            if(tmp[gg[k][j].id] == 2){
              inf[gg[k][j].id] = true;
            }
          }
        }
      }
    }

    stringstream ss;
    bool flag = false;

    for(int i = 50; i >= 0; i--){
      if(ans[i] > 0){
        if(!flag){
          flag = true;
        }else{
          ss << "+";
        }

        if(i == 0 || ans[i] != 1) ss << ans[i];
        if(i > 1) ss << "x^" << i;
        if(i == 1) ss << "x";
      }
    }

    string sans = ss.str();
    if(sans.size() == 0) sans = "0";

    cout << sans << endl;
  }
  return 0;
}

J : Blue Forest

力尽きたその2、読んでない。