2010-05-29
UAPC 2010
| 
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
#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