ICPC地区予選問題

AOJに入ったようなので解きました

実装重視が多くて大変でした。
ということで激ムズみたいなのはあまりないので、どう時間配分するかが本番では肝っぽい。
とは言ってもまだ２問ほど解けてないですが(実装重そうすぎて放置している)。
あとAOJは本番より制限時間とかメモリの制限がキツイのが地味に痛い。

AOJ 1315: Gift from the Goddess of Programming

問題読みにくいけど、やるだけ。
愚直に書くと最悪ケースが怪しい気もしたけど、0.0秒だったのでそんなことは無かったぜ。

inline int timeOf(int h, int m){
  return h * 60 + m;
}

int main(){
  while(int n = getInt()){
    vector<int> ans(1000, 0);
    vector<int> in(1000, -1);

    REP(i, n){
      int M, D;
      int h, m;
      char s[2];
      int id;

      scanf("%02d/%02d %02d:%02d %s %03d",
            &M, &D, &h, &m, s, &id);

      if(s[0] == 'I'){
        in[id] = timeOf(h, m);
      }else{
        int t = timeOf(h, m);
        if(id == 0){
          for(int j = 1; j < 1000; j++){
            if(in[j] != -1){
              ans[j] += t - max(in[j], in[0]);
            }
          }
        }else{
          if(in[0] != -1){
            ans[id] += t - max(in[id], in[0]);
          }
        }
        in[id] = -1;
      }
    }

    printf("%d\n", *max_element(ans.begin() + 1, ans.end()));
  }
  return 0;
}

AOJ 1316: The Sorcerer's Donut

3D幾何に見せかけたやるだけ問題。
全探索してmapで個数数えていけばよい。

char d[20][30];

int dx[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
int dy[8] = {-1,-1,-1, 0, 0, 1, 1, 1};

int main(){
  int h, w;

  while(scanf("%d%d", &h, &w), h + w){
    tr1::unordered_map<string, int> m;

    REP(i,h) scanf("%s", d[i]);

    REP(i,h) REP(j,w){
      REP(k,8){
        int x = j;
        int y = i;
        string tmp = "";

        do{
          tmp += d[y][x];
          x = (x + w + dx[k]) % w;
          y = (y + h + dy[k]) % h;
          m[tmp]++;
        }while(i != y || j != x);
      }
    }

    string ans = "";

    FOR(it, m) if(it->second > 1){
      const string &s = it->first;

      if(s.size() > ans.size()) ans = s;
      else if(s.size() == ans.size() && s < ans) ans = s;
    }

    if(ans.size() > 1) puts(ans.c_str());
    else puts("0");
  }

  return 0;
}

AOJ 1317: Weaker than Planned

基本的に全探索。
文字数多いものから決めると速い。

const int NONE = 0;

struct table{
  vector<char> t;
  table() : t(26, NONE) {}

  bool addRule(char a, char b){
    if(t[a - 'A'] != NONE && t[a - 'A'] != b) return false;
    if(t[b - 'A'] != NONE && t[b - 'A'] != a) return false;

    t[a - 'A'] = b;
    t[b - 'A'] = a;
    return true;
  }
};

inline bool operator < (const table &lhs, const table &rhs){
  return lhs.t < rhs.t;
}

pair<bool, table> merge(const table &a, const table &b){
  table t;
  bool  o = true;

  REP(i, 26){
    if(a.t[i] == b.t[i]){
      t.t[i] = a.t[i];
    }else{
      if(a.t[i] == NONE)
        t.t[i] = b.t[i];
      else if(b.t[i] == NONE)
        t.t[i] = a.t[i];
      else{
        o = false;
        break;
      }
    }
  }

  return make_pair(o, t);
}

bool ok[20][40];
vector<vector<table> > t;
vector<int> anseq(40);
vector<int> ans;
vector<set<table> > memo;

int n, m;

void dfs(int pos, int flag, table tbl){
  if(pos == m){
    if(ans.size()) throw 0;
    ans = anseq;
  }else{
    if(memo[pos].find(tbl) != memo[pos].end())
      return;
    memo[pos].insert(tbl);

    REP(i,n) if(ok[i][pos] && (flag & (1 << i)) == 0){
      pair<bool, table> ret = merge(tbl, t[i][pos]);
      if(ret.first){
        anseq[pos] = i;
        dfs(pos + 1, (flag | (1 << i)), ret.second);
      }
    }
  }
}

struct cmp{
  bool operator () (const string &lhs, const string &rhs){
    return lhs.size() > rhs.size();
  }
};

int main(){
  while(cin >> n, n){
    vector<string> word(n);
    vector<string> oseq;
    vector<string> seq;
    REP(i, n) cin >> word[i];

    while(true){
      string tmp; cin >> tmp;
      if(tmp.find(".") != string::npos){
        tmp = tmp.substr(0, tmp.size() - 1);
        seq.push_back(tmp);
        break;
      }
      seq.push_back(tmp);
    }

    oseq = seq; // save original sequence

    sort(seq.begin(), seq.end());
    seq.erase(unique(seq.begin(), seq.end()), seq.end());

    sort(seq.begin(), seq.end(), cmp());

    m = seq.size();
    t = vector<vector<table> >(n, vector<table>(m));

    REP(i,n) REP(j,m){
      if(word[i].size() == seq[j].size()){
        int len = word[i].size();
        bool tmp = true;

        REP(k, len){
          char a = word[i][k];
          char b = seq[j][k];

          if(!t[i][j].addRule(a, b)){
            tmp = false;
            break;
          }
        }
        ok[i][j] = tmp;
      }else{
        ok[i][j] = false;
      }
    }

    ans = vector<int>();
    memo = vector<set<table> >(m);

    try{
      dfs(0, 0, table());

      REP(i, oseq.size()){
        REP(j, m){
          if(oseq[i] == seq[j]){
            cout << word[ans[j]];
            break;
          }
        }
        if(i == oseq.size() - 1)
          cout << "." << endl;
        else
          cout << " ";
      }
    }catch(int e){
      cout << "-." << endl;
    }

  }
  return 0;
}

AOJ 1318: Long Distance Taxi

みるからにダイクストラするだけ。

template<class T>
class IdMaker{
public:
  std::map<T,int> _m;
  int getId(const T &v){
    if(_m.find(v) == _m.end()){
      int next = _m.size();
      return _m[v] = next;
    }
    return _m[v];
  }
  int size() { return _m.size(); }
};

int main(){
  int n, m, cap;

  ios_base::sync_with_stdio(false);

  while(cin >> n >> m >> cap, n + m + cap){
    IdMaker<string> idm;
    vector<vector<pair<int, int> > > edge(2 * n);
    string buff;
    int src, dst;

    cin >> buff; src = idm.getId(buff);
    cin >> buff; dst = idm.getId(buff);

    REP(i,n){
      string a, b;
      int l;
      cin >> a >> b >> l;

      int aa = idm.getId(a);
      int bb = idm.getId(b);

      edge[aa].push_back(make_pair(bb, l));
      edge[bb].push_back(make_pair(aa, l));
    }

    edge.resize(idm.size());

    vector<bool> gas(edge.size(), false);

    REP(i,m){
      cin >> buff;
      gas[idm.getId(buff)] = true;
    }

    cap *= 10;
    vector<vector<int> > memo(edge.size(), vector<int>(cap + 1, INT_MAX));
    typedef boost::tuple<int, int, int> data;
    const int distance = 0;
    const int liter    = 1;
    const int pos      = 2;
    priority_queue<data, vector<data>, greater<data> > pq;
    pq.push(make_tuple(0, cap, src));

    while(pq.size()){
      data d = pq.top(); pq.pop();

      int dd = d.get<distance>();
      int lt = d.get<liter>();
      int pp = d.get<pos>();

      if(memo[pp][lt] < dd) continue;
      memo[pp][lt] = dd;

      if(pp == dst){
        cout << dd << endl;
        pq.push(make_tuple(0, 0, 0)); // dammy
        break;
      }

      REP(i, edge[pp].size()){
        int next = edge[pp][i].first;
        int len  = edge[pp][i].second;
        int llt  = lt - len;

        if(llt >= 0){
          if(gas[next]) llt = cap;
          if(memo[next][llt] > dd + len){
            memo[next][llt] = dd + len;
            pq.push(make_tuple(dd + len, llt, next));
          }
        }
      }
    }

    if(pq.empty()){
      cout << "-1" << endl;
    }
  }

  return 0;
}

AOJ 1319: Driving an Icosahedral Rover

多分書いてあることを愚直に実装すれば通るけどやりたくない。

AOJ 1320: City Merger

どこかで見た問題だったのでその時のソースひっぱってきた。
だってこれ先週くらいに解いたし・・・
前処理で、別の文字列に含まれている文字列は消しておく。
全組み合わせに対して、かぶっている文字数をカウントしておいて、あとは全パターン試す。
ただしnext_permutationで全探索してたら間に合わなかったのでDPに。

int N;
vector<vector<int> > S;
vector<int> V;
int memo[14][1 << 14];

int solve(int last, int flag){
  if(flag == (1 << N) - 1) return 0;
  if(memo[last][flag] != -1) return memo[last][flag];

  int ret = 1000000;
  REP(i,N) if((flag & (1 << i)) == 0){
    ret = min(ret, V[i] - (V[last] - S[last][i]) +
              solve(i, (flag | (1 << i))));
  }

  return memo[last][flag] = ret;
}

int sss(vector<string> &v){
 loop:
  REP(i,v.size()){
    REP(j,v.size()) if(i != j){
      if(string::npos != v[i].find(v[j])){
        v.erase(v.begin() + j);
        goto loop;
      }
    }
  }

  int n = v.size();
  vector<vector<int> > same(n, vector<int>(n));

  REP(i,n) REP(j,n){
    for(int ii = 0; ii <= v[i].size(); ii++){
      bool ok = true;
      for(int jj = 0; ii + jj < v[i].size() && jj < v[j].size(); jj++){
        if(v[i][ii + jj] != v[j][jj]){
          ok = false;
          break;
        }
      }
      if(ok){
        same[i][j] = ii;
        break;
      }
    }
  }

  int ans = INT_MAX;

  N = n;
  S = same;
  V = vector<int>(n); REP(i,n) V[i] = v[i].size();
  memset(memo, -1, sizeof(memo));

  REP(i,n){
    ans = min(ans, V[i] + solve(i, (1 << i)));
  }

  return ans;
}

int main(){
  int n;
  while(cin >> n, n){
    vector<string> s(n);
    REP(i,n) cin >> s[i];
    cout << sss(s) << endl;
  }
  return 0;
}

AOJ 1321: Captain Q's Treasure

なんかグラフにして解けそうな気もするけど、思い浮かばなかった。
仕方ないのでメモ化しつつ全探索する感じに。
AOJの制限時間的には結構ぎりぎりになるがなんとか通るっぽい。

int h, w;
char g[20][20];
vector<int> xs;
vector<int> ys;
int n;
int cnt;

tr1::unordered_map<long long, int> memo[15][15];

inline long long gen(){
  long long ret = 0ll;

  REP(i, n){
    long long item = g[ys[i]][xs[i]] - '0';
    ret |= (item << (i * 4));
  }

  return ret;
}

inline bool ok(int y){
  if(y < 2) return true;
  REP(i, n){
    if(ys[i] < y - 1 && g[ys[i]][xs[i]] != '0'){
      return false;
    }
    if(ys[i] >= y - 1) return true;
  }
  return true;
}

void print(){
  REP(i,h){
    puts(g[i]);
  }
}

inline void paint(int y, int x){
  REP(i,3) REP(j,3){
    int xx = x + j - 1;
    int yy = y + i - 1;
    if(ISIN(xx, yy, w, h) && isdigit(g[yy][xx])) g[yy][xx]--;
  }
}

inline void unpaint(int y, int x){
  REP(i,3) REP(j,3){
    int xx = x + j - 1;
    int yy = y + i - 1;
    if(ISIN(xx, yy, w, h) && isdigit(g[yy][xx])) g[yy][xx]++;
  }
}

const int MAX = 10000;

int solve(int y, int x, long long flag){
  if(y == h){
    return flag == 0ll ? 0 : MAX;
  }

  if(x == 0 && !ok(y)){
    return MAX;
  }

  if(g[y][x] == '.'){
    if(x == w - 1) return solve(y + 1, 0, flag);
    return solve(y, x + 1, flag);
  }

  {
    tr1::unordered_map<long long, int>::iterator it = memo[y][x].find(flag);
    if(it != memo[y][x].end()) return it->second;
  }

  int ret = MAX;

  bool canput = true;
  int nx = (x == w - 1 ? 0 : x + 1);
  int ny = (x == w - 1 ? y + 1 : y);

  ret = min(ret, solve(ny, nx, flag));

  REP(i, 3) REP(j, 3){
    int xx = x + j - 1;
    int yy = y + i - 1;

    if(ISIN(xx, yy, w, h) && isdigit(g[yy][xx]) && g[yy][xx] == '0')
      canput = false;
  }

  if(canput){
    paint(y, x);
    cnt++;
    ret = min(ret, 1 + solve(ny, nx, gen()));
    cnt--;
    unpaint(y, x);
  }

  // printf("solve(%d, %d, %lld): cnt = %d, ret = %d, canput = %d\n", y, x, flag, cnt, ret, canput);
  // print(); puts("");

  return memo[y][x][flag] = ret;
}

int main(){
  while(scanf("%d%d", &h, &w), h + w){
    REP(i,h) scanf("%s", g[i]);

    bool update = true;
    int tmp = 0;

    while(update){
      update = false;
      REP(i,h) REP(j, w) if(isdigit(g[i][j])){
        int c = 0;
        REP(ii, 3) REP(jj, 3){
          int yy = i + ii - 1;
          int xx = j + jj - 1;
          if(ISIN(xx, yy, w, h) && g[i][j] != '.'){
            c++;
          }
        }

        if(g[i][j] - '0' == c){
          REP(ii, 3) REP(jj, 3){
            int yy = i + ii - 1;
            int xx = j + jj - 1;
            if(ISIN(xx, yy, w, h) && g[i][j] != '.'){
              paint(yy, xx);
              update = true;
              tmp++;
            }
          }
        }
      }
    }

    xs = vector<int>();
    ys = vector<int>();
    REP(i,h) REP(j,w){
      if(isdigit(g[i][j])){
        xs.push_back(j);
        ys.push_back(i);
      }

      if(g[i][j] == '*'){
        bool valid = false;
        REP(ii, 3) REP(jj, 3){
          int yy = i + ii - 1;
          int xx = j + jj - 1;

          if(ISIN(xx, yy, w, h) && isdigit(g[yy][xx]))
            valid = true;
        }
        if(!valid) g[i][j] = '.';
      }
    }

    n = xs.size();

    REP(i,h) REP(j,w) memo[i][j].clear();

    // print();
    printf("%d\n", tmp + solve(0, 0, gen()));
  }
  return 0;
}

AOJ 1322: ASCII Expression

これも書いてあることを愚直にやれば通ると思うが、やる気があんまりしない。

AOJ 1323: Encircling Circles

むずかしめの幾何を初めてノーヒントで解けた。
解となる図形は

• 1つの円を軸として、大きい円を回したような円
• 2つの円に引っかかってる状態の大きい円の一部

を連結したような図形になる(2つの円しか集合にない時を考えるとわかりやすい)。
ここまで分かるとあとは実際に連結部分の座標を計算して、半径*中心角を足していくだけ。

typedef complex<double> P;

const double EPS = 1e-10;
const double PI  = 3.1415926535;

class Circle{
public:
  P p;
  double r;

  Circle(){}
  Circle(P c, double rr) : p(c), r(rr) {}
};

pair<P, P> crossPoint(const Circle &c1, const Circle &c2){
  double d  = std::abs(c1.p - c2.p);
  double rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  double rs = sqrt(c1.r * c1.r - rc * rc);
  P diff = (c2.p - c1.p) / d;
  return make_pair(c1.p + diff * P(rc, rs), c1.p + diff * P(rc, -rs));
}

bool isCross(const Circle &c1, const Circle &c2){
  if(abs(c1.p - c2.p) < c1.r + c2.r + EPS)
    if(abs(c1.p - c2.p) + EPS > max(c1.r, c2.r) - min(c1.r, c2.r))
      return true;
  return false;
}

bool containAll(const Circle &c, const vector<Circle> &cs){
  REP(i, cs.size()){
    if(c.r + EPS < std::abs(c.p - cs[i].p) + cs[i].r)
      return false;
  }
  return true;
}

struct Data{
  P cc;
  P ec;
  int id;

  Data (P c, P e, int i) :
    cc(c), ec(e), id(i) {}
};

struct cmp{
  P center;

  cmp(P c) : center(c){}

  bool operator() (const Data &lhs, const Data &rhs){
    return arg(lhs.ec - center) < arg(rhs.ec - center);
  }
};

int main(){
  int n, r;

  while(scanf("%d%d", &n, &r), n + r){
    vector<Circle> cs(n);
    bool imp = false;

    REP(i,n){
      int x, y, rr;
      scanf("%d%d%d", &x, &y, &rr);
      cs[i] = Circle(P(x, y), rr);
      if(r < rr) imp = true;
    }

    if(imp){
      printf("%.10f\n", 0.0);
      continue;
    }

    if(n == 1){
      printf("%.10f\n", 2 * (2 * r - cs[0].r) * PI);
    }else{
      vector<Data> data;

      REP(i,n){
        REP(j, i){
          double ri = r - cs[i].r;
          double rj = r - cs[j].r;
          Circle c1 = Circle(cs[i].p, ri);
          Circle c2 = Circle(cs[j].p, rj);

          if(isCross(c1, c2)){
            pair<P, P> ret = crossPoint(c1, c2);

            if(containAll(Circle(ret.first,  r), cs)){
              P p1 = (ret.first - cs[i].p); p1 *= r / abs(p1); p1 += ret.first;
              P p2 = (ret.first - cs[j].p); p2 *= r / abs(p2); p2 += ret.first;
              data.push_back(Data(ret.first, p1, i));
              data.push_back(Data(ret.first, p2, j));
            }

            if(containAll(Circle(ret.second, r), cs)){
              P p1 = (ret.second - cs[i].p); p1 *= r / abs(p1); p1 += ret.second;
              P p2 = (ret.second - cs[j].p); p2 *= r / abs(p2); p2 += ret.second;

              data.push_back(Data(ret.second, p1, i));
              data.push_back(Data(ret.second, p2, j));
            }
          }
        }
      }

      if(data.empty()){
        bool ok = false;
        REP(i,n) if(containAll(cs[i], cs)){
          ok = true;
          printf("%.10f\n", 2 * (2 * r - cs[i].r) * PI);
          break;
        }

        if(!ok) printf("%.10f\n", 0.0);
        continue;
      }

      double ans = 0.0;
      sort(data.begin(), data.end(), cmp(data[0].cc));

      REP(i, data.size()){
        int j = i + 1 == data.size() ? 0 : i + 1;

        if(data[i].id != data[j].id){
          double ag = std::abs(arg((data[i].ec - data[i].cc) / (data[j].ec - data[j].cc)));
          ans += r * ag;
        }else{
          int id = data[i].id;
          double ag = std::abs(arg((data[i].ec - cs[id].p) / (data[j].ec - cs[id].p)));
          double rr = std::abs(r + (r - cs[id].r));
          ans += rr * ag;
        }
      }

      printf("%.10f\n", ans);
    }
  }

  return 0;
}

AOJ 1324: Round Trip

帰りのルートは逆向きに辺を張ることで、行き帰りともに0からN-1へのパスに出来る。
同じ高さがない場合には、この状態で場所のペアーに対してダイクストラをすればいい。
が、今回は同じ高さがあるので同じ高さ内で行ったところを覚えておかないと行けない・・・ような気がする(証明はよく分からない)。
同じ高さの街は高々10個という制限があるので50*50*(2^10)程度なので間に合う。
なぜか2^10についてはメモらなくても通ってしまった。実は必要ないのか、入力が弱いのかは謎。

int go[50][50];
int re[50][50];

int d[50];
int e[50];

bool memo[50][50];

int main(){
  while(true){
    int n = getInt();
    int m = getInt();

    if(n + m == 0) break;

    d[0] = d[n - 1] = 0;
    e[0] = 0; e[n - 1] = 1000;

    REP(i, n - 2){
      d[i + 1] = getInt();
      e[i + 1] = getInt();
    }

    REP(i,n) REP(j,n){
      memo[i][j] = false;
      go[i][j] = re[i][j] = 0;
    }

    REP(i, m){
      int a = getInt() - 1;
      int b = getInt() - 1;
      int c = getInt();

      if(e[a] >= e[b])
        re[b][a] = c;
      if(e[a] <= e[b])
        go[a][b] = c;
    }

    typedef boost::tuple<int, int, int, long long> data;
    const int COST = 0;
    const int POS_GO = 1;
    const int POS_RE = 2;
    const int FLAG   = 3;

    priority_queue<data, vector<data>, greater<data> > pq;
    bool ok = false;

    pq.push(make_tuple(0, 0, 0, 1));

    while(pq.size()){
      data dt = pq.top(); pq.pop();
      int cost  = dt.get<COST>();
      int posgo = dt.get<POS_GO>();
      int posre = dt.get<POS_RE>();
      long long flag = dt.get<FLAG>();

      if(memo[posgo][posre]) continue;
      memo[posgo][posre] = true;

      if(posgo == n - 1 && posre == n - 1){
        ok = true;
        printf("%d\n", cost);
        break;
      }

      REP(i,n){
        bool gof = go[posgo][i] != 0;
        bool ref = re[posre][i] != 0;
        int cc = cost;
        long long ff = (flag | (1ll << i));

        if((flag & (1ll << i)) == 0){
          cc += d[i];
        }

        if(gof && !memo[i][posre])
          pq.push(make_tuple(cc + go[posgo][i], i, posre, ff));
        if(ref && !memo[posgo][i])
          pq.push(make_tuple(cc + re[posre][i], posgo, i, ff));
        if(gof && ref && !memo[i][i])
          pq.push(make_tuple(cost + d[i] + go[posgo][i] +
                             re[posre][i], i, i, ff));
      }
    }

    if(!ok) puts("-1");
  }
  return 0;
}