スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

立命館合宿 2012 Day1

2012/03/13 14:00 ~ 17:00

この記事では解いたコードだけ載せます。
コードはすべて後で解きなおしたもの。

参加記録は別に書くかも。

Tag : プログラミング

A. K Cards (AOJ 1084)
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int n,k,card[100];

int calc(){
int res=0;
rep(i,n-k+1){
int tmp=1;
for(int j=i;j<i+k;j++) tmp*=card[j];
res=max(res,tmp);
}
return res;
}

int main(){
for(;scanf("%d%d",&n,&k),n;){
rep(i,n) scanf("%d",card+i);

int c1=calc(),c2=0;
rep(i,n) rep(j,i) {
swap(card[i],card[j]);
c2=max(c2,calc());
swap(card[i],card[j]);
}
if(c2>=c1) printf("%d\n",c2-c1); else puts("NO GAME");
}

return 0;
}


B. Spellcasters (AOJ 1085)
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
for(int n,sum;scanf("%d%d",&n,&sum),n;){
int a[20000];
rep(i,n) scanf("%d",a+i);

sort(a,a+n);

int ans=0;
rep(i,n) ans+=n-(upper_bound(a+i+1,a+n,sum-a[i])-a);
printf("%d\n",ans);
}

return 0;
}


C. Live Schedule (AOJ 1086)
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
for(int n_city,n_day,hiro_max,dup_max;scanf("%d%d%d%d",&n_city,&n_day,&hiro_max,&dup_max),n_city;){
int profit[15][30],hiro[15][30];
rep(i,n_city) rep(j,n_day) scanf("%d",profit[i]+j);
rep(i,n_city) rep(j,n_day) scanf("%d",hiro[i]+j);

// dp[t+1][i][j] := t 日目において疲労が i ですでに j 回の複数ライブをこなしているときの最大利益
int dp[31][51][16]={};
rep(t,n_day){
rep(i,hiro_max+1) rep(j,dup_max+1) {
// ライブをしないとき
dp[t+1][i][j]=max(dp[t+1][i][j],dp[t][i][j]);

// 一つの町でのみライブをするとき
rep(p,n_city){
if(profit[p][t]>0 && i+hiro[p][t]<=hiro_max)
dp[t+1][i+hiro[p][t]][j]=max(dp[t+1][i+hiro[p][t]][j],dp[t][i][j]+profit[p][t]);
}

// 複数の町 ( 区間 ) でライブをするとき
rep(r,n_city) rep(l,r) {
bool ok=true;
for(int p=l;p<=r;p++) if(profit[p][t]==0) ok=false;
if(!ok) continue;

int profit_sum=0,hiro_sum=0;
for(int p=l;p<=r;p++){
profit_sum+=profit[p][t];
hiro_sum+=hiro[p][t];
}

if(i+hiro_sum<=hiro_max && j+1<=dup_max)
dp[t+1][i+hiro_sum][j+1]=max(dp[t+1][i+hiro_sum][j+1],dp[t][i][j]+profit_sum);
}
}
}

int ans=0;
rep(i,hiro_max+1) rep(j,dup_max+1) ans=max(ans,dp[n_day][i][j]);
printf("%d\n",ans);
}

return 0;
}


D. Dimensional Analysis (AOJ 1087)
#include<map>
#include<cctype>
#include<string>
#include<vector>
#include<iostream>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

void operator*=(vector<int> &a,const vector<int> &b){ rep(i,a.size()) a[i]+=b[i]; }
void operator/=(vector<int> &a,const vector<int> &b){ rep(i,a.size()) a[i]-=b[i]; }

map< string,vector<int> > f,g; // f : 組立量の名前 -> 基本量の列, g : 変数の名前 -> 基本量の列
map< vector<int>,string > f_inv;

int idx;
string s;
bool error;

vector<int> expr();

vector<int> variable(){
string a;
while(idx<s.length() && isalpha(s[idx])) a+=s[idx++];
return g[a];
}

vector<int> factor(){
if(idx<s.length() && s[idx]=='('){
idx++;
vector<int> a=expr();
idx++;
return a;
}
else return variable();
}

vector<int> term(){
vector<int> a=factor();
while(idx<s.length() && (s[idx]=='*' || s[idx]=='/')){
char op=s[idx++];
vector<int> b=factor();
if(op=='*') a*=b;
else a/=b;
}
return a;
}

vector<int> expr(){
vector<int> a=term();
while(idx<s.length() && (s[idx]=='+' || s[idx]=='-')){
idx++;
vector<int> b=term();
if(a!=b){ error=true; break; }
}
return a;
}

string parse(string formula){
idx=0;
s=formula;
error=false;

vector<int> res=expr();
if(error) return "error";
if(f_inv.count(res)==0) return "undefined";
return f_inv[res];
}

int main(){
for(int n,m,p;cin>>n>>m>>p,n;){
f.clear();
g.clear();
f_inv.clear();

rep(i,m){
string s; cin>>s;
vector<int> a(n);
rep(j,n) cin>>a[j];
f[s]=a;
f_inv[a]=s;
}

string formula; cin>>formula;
rep(i,p){
string s,t; cin>>s>>t;
g[s]=f[t];
}

cout<<parse(formula)<<endl;
}

return 0;
}

map で上書きしていたので、同じ次元をもつ名前が複数来るケースにも対応できていてラッキーだった。

E. School Excursion (AOJ 1088)
#include<map>
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int V_MAX=6000;
const int CAPA_INF=1<<29;
const int COST_INF=1<<29;

template<class T,class U>
struct edge{
int v,rev;
T capa;
U cost;
T flow;
};

template<class T,class U>
void add_directed_edge(vector< edge<T,U> > *G,int u,int v,T capa,U cost){
G[u].push_back((edge<T,U>){v,G[v].size() ,capa, cost,0});
G[v].push_back((edge<T,U>){u,G[u].size()-1, 0,-cost,0});
}

template<class T,class U>
pair<T,U> augment(int n,vector< edge<T,U> > *G,int s,int t,U *pot){
static int pre[V_MAX];
static U d[V_MAX];
rep(u,n) d[u]=(u==s?0:COST_INF);

// Dijkstra
bool ok=false;
priority_queue< pair<U,int> > Q; Q.push(make_pair(0,s));
while(!Q.empty()){
int u=Q.top().second;
U cost=-Q.top().first; Q.pop();

if(cost<d[u]) continue;
if(u==t) ok=true;

rep(i,G[u].size()){
edge<T,U> &e=G[u][i];
U cost2=cost+e.cost+pot[u]-pot[e.v];
if(e.capa-e.flow>0 && cost2<d[e.v]){
d[e.v]=cost2;
pre[e.v]=e.rev;
Q.push(make_pair(-cost2,e.v));
}
}
}

if(!ok) return make_pair(0,0);

T water=CAPA_INF;
for(int v=t;v!=s;){
edge<T,U> &e1=G[v][pre[v]];
edge<T,U> &e2=G[e1.v][e1.rev];
water=min(water,e2.capa-e2.flow);
v=e1.v;
}

U cost=0;
for(int v=t;v!=s;){
edge<T,U> &e1=G[v][pre[v]];
edge<T,U> &e2=G[e1.v][e1.rev];
e1.flow-=water;
e2.flow+=water;
cost+=water*e2.cost;
v=e1.v;
}

rep(u,n) pot[u]+=d[u];

return make_pair(water,cost);
}

template<class T,class U>
pair<T,U> primal_dual(int n,vector< edge<T,U> > *G,int s,int t){
static U pot[V_MAX];
rep(u,n) pot[u]=0;

T ans1=0;
U ans2=0;
while(1){
pair<T,U> tmp=augment(n,G,s,t,pot);
if(tmp.first==0) break;
ans1+=tmp.first;
ans2+=tmp.second;
}
return make_pair(ans1,ans2);
}

struct train{
int t1,t2,cost; // 出発時刻, 到着時刻, 運賃
};

int main(){
for(int n;scanf("%d",&n),n;){
vector<train> T[99];
rep(i,n-1){
int m; scanf("%d",&m);
T[i].resize(m);
rep(j,m) scanf("%d%d%d",&T[i][j].t1,&T[i][j].t2,&T[i][j].cost);
}
int n_class; scanf("%d",&n_class);

int V=0;
map<int,int> f[100][2]; // [駅の番号][ふつうの頂点か頂点流量制限用か][時刻] -> 頂点番号
map<int,int>::iterator it,jt;
rep(i,n-1) rep(j,T[i].size()) {
int t1=T[i][j].t1,t2=T[i][j].t2;
if(f[ i ][0].count(t1)==0) f[ i ][0][t1]=V++;
if(f[i+1][0].count(t2)==0) f[i+1][0][t2]=V++;
if(f[i+1][1].count(t2)==0) f[i+1][1][t2]=V++;
}

int s=V++;
int t=V++;
static vector< edge<int,int> > G[V_MAX];
rep(u,V) G[u].clear();

// build graph
// 特殊な辺 ( source, sink )
add_directed_edge(G,s,f[0][0].begin()->second,n_class,0);
add_directed_edge(G,f[n-1][0].rbegin()->second,t,n_class,0);
// 特殊な辺
rep(i,n){
// 電車待ちを表す辺
for(it=f[i][0].begin();it!=f[i][0].end();++it){
jt=it;
++jt;
if(jt!=f[i][0].end()){
add_directed_edge(G,it->second,jt->second,n_class,0);
}
}
// 分裂させた頂点間に張る辺
for(it=f[i][1].begin();it!=f[i][1].end();++it){
int t=it->first;
add_directed_edge(G,it->second,f[i][0][t],1,0);
}
}
// ふつうの辺 ( 電車に相当 )
rep(i,n-1) rep(j,T[i].size()) {
add_directed_edge(G,f[i][0][T[i][j].t1],f[i+1][1][T[i][j].t2],1,T[i][j].cost);
}

pair<int,int> ans=primal_dual(V,G,s,t);
printf("%d %d\n",ans.first,ans.second);
}

return 0;
}

最小費用流は自分のライブラリから引用したので、実装量はそれほど多くない。
グラフを作る部分が複雑で、ちゃんと整理してから書かないと混乱する。

F. Strawberry Cake (AOJ 1089)
#include<cmath>
#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double EPS=1e-8;
const double PI=acos(-1);

template<class T>
struct point{
T x,y;
point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
};

template<class T>
point<T> operator*(T c,const point<T> &a){ return (point<T>){c*a.x,c*a.y}; }

template<class T>
struct line:vector< point<T> >{
line(){}
line(const point<T> &a,const point<T> &b){ push_back(a), push_back(b); }
};

template<class T>
struct polygon:vector< point<T> >{
polygon(){}
polygon(int n):vector< point<T> >(n){}
};

template<class T>
T cross(const point<T> &a,const point<T> &b){ return a.x*b.y-a.y*b.x; }

point<double> rot(const point<double> &a,double theta){
return (point<double>){a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)};
}

enum {CCW=1,CW=-1,ON=0};
int ccw(const point<double> &a,const point<double> &b,const point<double> &c){
double rdir=cross(b-a,c-a);
if(rdir> EPS) return CCW;
if(rdir<-EPS) return CW;
return ON;
}

template<class T>
T area2(const polygon<T> &G){
int n=G.size();
T a=0;
rep(i,n) a+=cross(G[i],G[(i+1)%n]);
return abs(a);
}

template<class T>
point<double> get_intersect(const line<T> &L1,const line<T> &L2){
double a1=cross(L1[1]-L1[0],L2[1]-L2[0]);
double a2=cross(L1[1]-L1[0],L1[1]-L2[0]);
if(abs(a1)<EPS) return L1[0]; // L1 == L2
return L2[0]+a2/a1*(L2[1]-L2[0]);
}

template<class T>
polygon<double> convex_cut(const polygon<T> &G,const line<T> &L){
int n=G.size();
polygon<double> H;
rep(i,n){
int d1=ccw(L[0],L[1],G[i]);
int d2=ccw(L[0],L[1],G[(i+1)%n]);
if(d1!=CW) H.push_back(G[i]);
if(d1==CCW && d2==CW || d1==CW && d2==CCW){
H.push_back(get_intersect(L,line<T>(G[i],G[(i+1)%n])));
}
}
return H;
}

int main(){
const point<double> O={0,0},P={1,0};

for(int n;scanf("%d",&n),n;){
polygon<double> G(n);
rep(i,n) scanf("%lf%lf",&G[i].x,&G[i].y);

double A2=area2(G);
line<double> L0(O,P);

double lo=0,hi=PI;
if(area2(convex_cut(G,L0))>A2/2) lo=-PI, hi=0;
rep(_,50){
double mi=(lo+hi)/2;
line<double> L(O,rot(P,mi));
if(area2(convex_cut(G,L))<A2/2) lo=mi; else hi=mi;
}

point<double> ans=rot(P,(lo+hi)/2);
printf("%.15f %.15f\n",2*ans.x,2*ans.y);
}

return 0;
}

角度について二分探索した。
数式でかっちりやる方法があるという噂だけど、どうするのかわからない。

二直線の交点・凸多角形と半平面の交差は、Spaghetti Source を参考にして自分が使いやすいように整形した。

G. Sports Days (AOJ 1090)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

struct edge{ int v,cost; };

// 拡張したグラフにおける頂点
struct Xnode{
int u,t; // コーンの番号, pttn の何文字目までマッチしたか
bool operator<(const Xnode &X)const{ return u<X.u || u==X.u && t<X.t; }
};

// 拡張したグラフにおける辺
struct Xedge{
Xnode X;
int cost;
};

int n,color[100],K,len;
vector<edge> G[100]; // 元のグラフ
char pttn[11];

bool input(){
scanf("%d",&n);
if(n==0) return false;
rep(u,n){
G[u].clear();
scanf("%d",color+u);
}
int m; scanf("%d",&m);
rep(i,m){
int u,v,cost; scanf("%d%d%d",&u,&v,&cost); u--; v--;
G[u].push_back((edge){v,cost});
}
scanf("%d%s",&K,pttn);
len=strlen(pttn);
return true;
}

vector<Xedge> XG[100][10],XG_rev[101][10]; // 拡張したグラフ, XG の逆グラフ
void build_XG(){
rep(u,n+1) rep(t,max(len,2)) {
XG[u][t].clear();
XG_rev[u][t].clear();
}

rep(u,n) rep(t,len) rep(i,G[u].size()) {
int v=G[u][i].v,cost=G[u][i].cost;

char tmp[12]={};
strncpy(tmp,pttn,t);
tmp[t]=color[v]+'0';
int t_next;
for(t_next=t+1;strncmp(pttn,tmp+(t+1)-t_next,t_next);t_next--);

if(t_next<len){
XG[u][t].push_back((Xedge){(Xnode){v,t_next},cost});
XG_rev[v][t_next].push_back((Xedge){(Xnode){u,t},cost});
}
}
// XG_rev の始点たち ( XG の終点たち ) を一つにまとめる
rep(t,len) XG_rev[n][0].push_back((Xedge){(Xnode){n-1,t},0});
}

bool vis[101][10]; // XG において始点 (0, t0) から辿り着ける Xnode の集合
bool dfs(int u,int t){
vis[u][t]=true;
rep(i,XG[u][t].size()){
const Xedge &e=XG[u][t][i];
int v=e.X.u,t_next=e.X.t;
if(!vis[v][t_next]) dfs(v,t_next);
}
}

bool vis_rev[101][10]; // XG において終点たち (n-1, t) (0 < t < len) から辿り着ける Xnode の集合
bool dfs_rev(int v,int t){
vis_rev[v][t]=true;
rep(i,XG_rev[v][t].size()){
const Xedge &e=XG_rev[v][t][i];
int u=e.X.u,t_prev=e.X.t;
if(!vis_rev[u][t_prev]) dfs_rev(u,t_prev);
}
}

// Bellman-Ford による誤判定を防ぐために必要のない Xnode を XG から削除する
void delete_Xnodes(){
rep(u,n+1) rep(t,len) vis[u][t]=vis_rev[u][t]=false;

int t0=(pttn[0]==color[0]+'0'?1:0);
dfs(0,t0);
dfs_rev(n,0);

rep(u,n) rep(t,len) {
if(!vis[u][t] || !vis_rev[u][t]){
XG[u][t].clear();
}
else{
rep(i,XG[u][t].size()){
const Xedge &e=XG[u][t][i];
int v=e.X.u,t_next=e.X.t;
if(!vis[v][t_next] || !vis_rev[v][t_next]){
XG[u][t].erase(XG[u][t].begin()+i);
i--;
}
}
}
}
}

int pot[101][10];
// Bellman-Ford 法を用いてポテンシャルを計算
bool calc_potential(){
rep(u,n+1) rep(t,len) pot[u][t]=0;

rep(c,n*len){
rep(u,n+1) rep(t,len) rep(i,XG[u][t].size()) {
const Xedge &e=XG[u][t][i];
int v=e.X.u,t_next=e.X.t,cost=e.cost;
if(pot[u][t]+cost<pot[v][t_next]){
pot[v][t_next]=pot[u][t]+cost;
if(c==n*len-1){
puts("-1");
return false;
}
}
}
}
return true;
}

void Kth_shortest_path(){
int nd[100][10]={},d[100][10][10];
int t0=(pttn[0]==color[0]+'0'?1:0);

priority_queue< pair<int,Xnode> > Q;
Q.push(make_pair(0,(Xnode){0,t0}));
while(!Q.empty()){
int d_now=-Q.top().first;
int u=Q.top().second.u,t=Q.top().second.t; Q.pop();

if(nd[u][t]==K) continue;
d[u][t][nd[u][t]++]=d_now;

rep(i,XG[u][t].size()){
const Xedge &e=XG[u][t][i];
int v=e.X.u,t_next=e.X.t,cost=e.cost;
if(nd[v][t_next]<K){
int d_next=d_now+cost+pot[u][t]-pot[v][t_next];
Q.push(make_pair(-d_next,(Xnode){v,t_next}));
}
}
}

vector<int> ans;
rep(t,len) rep(i,nd[n-1][t]) ans.push_back(d[n-1][t][i]-pot[0][t0]+pot[n-1][t]);
sort(ans.begin(),ans.end());

int n_ans=min((int)ans.size(),K),ans_sum=0;
rep(i,n_ans) ans_sum+=ans[i];
printf("%d %d\n",n_ans,ans_sum);
}

int main(){
while(input()){
build_XG();
delete_Xnodes();
if(!calc_potential()) continue;
Kth_shortest_path();
}
return 0;
}

解説どおりの解法。
10 WA したあたりで心が折れて、ランダム生成したテストケースで simezi_tan さんのコードとの diff を取らせてもらってデバッグしました。
結局、初期化ミスで WA になっていただけで、本処理は正しく書けていた・・・

( simezi_tan さんのブログにトラックバックしようとしたけどやり方がわからない )
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。