2010-05-29

UAPC 2010

00:03 |

http://rose.u-aizu.ac.jp/onlinejudge/cvolume.jsp?contestID=UAPC2010

途中から参戦。

Aを解いて、Bで躓いて、Cの問題が理解できなくて、諦めて食事して、戻ってDを解いて、Gを解くのにサイコロを作って、提出しようと思ったらもう試合終了していた
へぇー問題英語なんだーと思って頑張って読んでたけど、日本語で読めることに翌日気づいた
というわけで風船２個＞＜

A. Citation Format

解けた。AC

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define all(c)  (c).begin(),(c).end()

typedef pair<int,int> ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

int main(){
  while(1) {
    int n; cin >> n; if (n==0) break;
    vector<int> page(n);
    rep(i,n) cin >> page[i]; sort(all(page));
    vector<ii> r; int last=page[0]-2;
    rep(i,n){
      if(page[i]==last+1){
        (r.end()-1)->second++;
      } else {
        r.pb(ii(page[i],page[i]));
      }
      last=page[i];
    }
    REP(i,r){
      if(i>0) cout << " ";
      ii p=r[i]; if(car(p)==cdr(p)) cout << car(p);
      else cout << car(p) << "-" << cdr(p);
    }
    cout << endl;
  }
  return 0;
}

B. Old Bridges

Greedyに解けるはずだと思って書いたコードがダメダメで、
DPで書いたやつがローカルでは動くけど
TLE
MLE
諦めて食事休憩。弁当屋に行ってくる

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()

#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

vector<ii> ax; //mx,am
vector<int> sum;
int n,g;
map<int,bool> mm;

int sub(int mask){
  int n=__builtin_popcount(mask);
  if(n==0) return true;
  if(found(mm,mask)) return mm[mask];
  for(int i=0,m=1;m<=g;i++,m<<=1) {
    if(mask&m) {
      int m2 = mask-m;
      int am=ax[i].first, mx=ax[i].second;
      if (sum[m2] + am > mx) continue;
      if(m2) {
        bool b = sub(m2); if (b) return mm[mask]=true;
      } else {
        return mm[mask]=true;
      }
    }
  }
  return mm[mask]=false;
}

int main(){
  while(cin>>n){ // 25
    if(n==0)break;
    int amz=0;
    ax.clear(); mm.clear();
    rep(i,n){
      int am,mx; cin>>am>>mx; amz+=am;
      ax.pb( ii(am,mx) );
    }
    sort(all(ax));

    sum.resize(1<<n);
    g=(1<<n)-1;
    for(int i=g;i>=0;--i){
      sum[i]=0;
      for(int m=1,j=0;j<n;j++,m<<=1){
        if(i&m) sum[i]+=ax[i].second;
      }
    }
    
    cout << (sub(g)? "Yes" : "No") << endl;
  }
  return 0;
}

C. Accelerated Railgun

弁当タイムの後で復帰
英語版では問題Cで町一番のESPerが壁を作る時の中心点が明示されていないので解きようがない。町一番君がどこにでも行けるんだったら、発射直後に原点に向くように反射させればよさげだから変な問題だなあと

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()

#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

int main(){
  while(1){
    double D; cin >> D; if(D==0) break;
    double px,py,vx,vy; cin >> px >> py >> vx >> vy;
    double p_ = hypot(px,py), v_ = hypot(vx,vy);
    if (p_<=D) {
      printf("%10.8f\n", p_);
    } else {
      printf("impossible\n");
    }
  }
  return 0;
}

そんなわけないよね
諦め

D. Distorted Love

実装するだけっぽい
できた。AC

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()

#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class button {
 public:
  int x0,y0,x1,y1;
  string name;
  button(int x0,int y0,int x1,int y1,string name) :
      x0(x0),y0(y0),x1(x1),y1(y1),name(name) {
  }
  bool within(int x,int y){
    return (x0<=x && x<=x1 && y0<=y && y<=y1);
  }
      
};

int main(){
  while(1){
    int n; cin >> n; if (n==0) break;
    int w, h; cin >> w >> h;
    vector<string> name(n);
    vector<vector<button> > btn(n,vector<button>());
    map<string,int> pages;
    rep(i,n){
      cin >> name[i]; pages[ name[i] ] = i;
      int nb; cin >> nb; // btn[i].resize(nb);
      rep(j,nb){
        int x0,y0,x1,y1; string nm; cin >> x0 >> y0 >> x1 >> y1 >> nm;
        btn[i].pb( button(x0,y0,x1,y1,nm) );
      }
    }
    //cout << pages << endl;

    vector<int> history;
    history.pb(0); int hix=0;
    
    int m; cin >> m;
    int ix=0;
    rep(j,m){
      string op; cin >> op;
      if (op == "click"){
        int x, y; cin >> x >> y;
        int btns = sz(btn[ix]), nx=-1;
        rep(k,btns){
          if (btn[ix][k].within(x,y)) {
            string nm = btn[ix][k].name;
            if(found(pages,nm)) {
              nx = pages[nm];
              break;
            }
          }
        }
        if (nx>=0) {
          for(int i=sz(history)-1,c=hix+1;i>=c;i--){
            history.erase(history.begin()+i);
          }
          history.pb(ix=nx); hix++;
        }
      } else if (op=="show") {
        cout << name[ix] << endl;
      } else if (op=="back") {
        if (hix-1 >= 0) {
          ix = history[--hix];
        }
      } else if (op=="forward") {
        if (hix+1 < history.size()) {
          ix = history[++hix];
        }
      }
    }
  }
  return 0;
}

E. Huge Family

開いてない

F. Ben Toh

開いてない

G. Rolling Dice

とりあえず弁当の包み紙でサイコロを作った
サイコロって右→下、の場合と下→右、の場合で面が違うのか…
サイコロの面の状態は24種類ある
- けどそれぞれに番号ふるの面倒くさそう
- あ。自動的にやらせればいいか
状態数は10x10x24=2400で、どの状態からどの状態に移るかを自動計算して、あとはダイクストラで行けそう
出来た

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(__typeof__((c).begin()) i=(c).begin(); i!=(c).end(); i++)

#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

#define INF 987654321

const int infty = INF;

template <typename T> T infsum(T a, T b){
  return (a == infty || b == infty)? infty : (a + b);
}

vector<int> dijkstra_core(vector<vector<int> > arclength, int start_v, int goal_v=-1)
{
  int N = arclength.size();
  vector<int> distance(N, infty); // inftyは適当な大きな数
  vector<int> predecessor(N, -1);

  set<int> S; S.insert(start_v);
  distance[start_v] = 0;

  rep(v,N){
    if (v == start_v) continue;
    if (arclength[start_v][v] == infty) continue;
    distance[v] = arclength[start_v][v];
    predecessor[v] = start_v;
  }
  
  while (S.size() < N) { // 各点へ
    // find v* from V¥S with distance(v*) = min{distance(v):v from V¥S}
    int d_min = infty;
    int d_min_at = -1; // v_
    rep(v,N){
      if (found(S,v)) continue;
      if (distance[v] < d_min) { d_min = distance[v]; d_min_at = v; }
    }
    int v_ = d_min_at;
    if (v_ == -1) break;
    S.insert(v_);

    rep(v,N){ // FOR ALL v from V¥S DO
      if (found(S,v)) continue;
      int d_ = infsum(distance[v_], arclength[v_][v]);
      if (d_ < distance[v]) {
        distance[v] = d_;
        predecessor[v] = v_;
      }
    }
  }

  return distance;
}

vector<int> rot(vector<int>& orig, int r){
  vector<int> d(6);
  switch(r){
    case 0:
      d[0]=orig[4], d[1]=orig[0], d[2]=orig[2], d[3]=orig[3], d[4]=orig[5], d[5]=orig[1]; break;
    case 1:
      d[0]=orig[3], d[1]=orig[1], d[2]=orig[0], d[3]=orig[5], d[4]=orig[4], d[5]=orig[2]; break;
    case 2:
      d[0]=orig[1], d[1]=orig[5], d[2]=orig[2], d[3]=orig[3], d[4]=orig[0], d[5]=orig[4]; break;
    case 3:
      d[0]=orig[2], d[1]=orig[1], d[2]=orig[5], d[3]=orig[0], d[4]=orig[4], d[5]=orig[3]; break;
  }
  return d;
}
map<vector<int>,int> mp;

int main(){
  vector<int> dice(6); rep(i,6) dice[i]=i+1;
  int id=0; mp[dice]=id++;
  rep(i,4) { //4で十分
    vector<vector<int> > m_; tr(mp,it) m_.pb(it->first);
    REP(j,m_) {
      rep(r,4) {
        vector<int> d = rot(m_[j], r);
        if (!found(mp,d)) mp[d]=id++;
      }
    }
  }
  vector<vector<int> > rmp(24); tr(mp,it) rmp[it->second] = it->first;
  vector<vector<int> > rz(24,vector<int>(4)); // rz[int][r]=int
  vector<int> unt(24);
  rep(p,24){
    vector<int> d0=rmp[p];
    unt[p] = d0[5];
    rep(r,4){
      vector<int> d1=rot(d0,r);
      rz[p][r] = mp[ d1 ];
    }
  }

  while(1){
    int h,w; cin>>h>>w; if(h==0&&w==0) break;
    vector<vector<int> > gridnum(h,vector<int>(w));
    rep(y,h) rep(x,w) cin >> gridnum[y][x];
    int sr,sc, dr,dc; cin >> sr >> sc >> dr >> dc;

    vector<vector<int> > ar(h*w*24,vector<int>(h*w*24,INF));
    rep(y,h) {
      rep(x,w) {
        int o = (y*w + x)*24;
        rep(p,24) {
          //0 : y++
          if(y<h-1){
            int d=rz[p][0];
            ar[o+p][o+w*24+d] = gridnum[y+1][x] * unt[d];
          }
          //1 : x++
          if(x<w-1){
            int d=rz[p][1];
            ar[o+p][o+24+d] = gridnum[y][x+1] * unt[d];
          }
          //2 : y--
          if(y>0){
            int d=rz[p][2];
            ar[o+p][o-w*24+d] = gridnum[y-1][x] * unt[d];
          }
          //3 : x--
          if(x>0){
            int d=rz[p][3];
            ar[o+p][o-24+d] = gridnum[y][x-1] * unt[d];
          }
        }
      }
    }

    int pmin=INF;
    int sv=(sr*w + sc)*24, dv=(dr*w + dc)*24;
    vector<int> dist = dijkstra_core(ar, sv,-1);//dv+p);

    rep(p,24){
      pmin = min(pmin, dist[dv+p]);
    }
    cout << pmin << endl;
  }
  return 0;
}

提出しようと思ったら18:12…試合は終わっていた

H. Winter Bells

開いてない

I. Mysterious Onslaught

開いてない

J. No Story

開いてない

K. Seventh Color

開いてない

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100529

		2010/05
日	月	火	水	木	金	土
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

naoya_t@topcoder

2010-05-29

UAPC 2010

A. Citation Format

B. Old Bridges

C. Accelerated Railgun

D. Distorted Love

E. Huge Family

F. Ben Toh

G. Rolling Dice

H. Winter Bells

I. Mysterious Onslaught

J. No Story

K. Seventh Color