スポンサーサイト

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

CTPC

ICPC 地区予選の帰りの新幹線で CTPC の問題を解いた。終わらなかった分は帰ってから解いた。
ジャッジデータは公開されているので、手元でジャッジした。
old.atcoder には早く元気になってほしい。

昨年は VKPC を解いたので、来年は ( コーチとして行くことがあれば ) HBPC あたりを解くかもしれない。

Tags : プログラミング CTPC

問題文はここ

解法

A. B. C.
straightforward

D.
変更クエリがなければ、ナップサック問題の DP をやればよい。
変更クエリは少ないので、何も考えずに、毎回 DP を最初からやり直しても間に合う。

E.
完全有向グラフがハミルトン閉路を含むかどうかを判定する問題。
もちろん頂点数は少ない ( そうじゃなきゃ解けない ) ので bit DP する。

追記:解説を読むと、どうやらまるで違う問題らしい。なぜ通ったのか…

F.
幾何。
答えについて二分探索するのはいいとして、半径を固定したときに円盤たちがフィールド全体を覆っているかの判定ができればよい。
円盤たちの交点を全部列挙して、その交点のまわり数点だけを調べることにした。
嘘解法ではないけど、どれだけずらすかとかの調節が難しくてあまり好きな解法ではない。

G.
1, 7, 7^2, 7^3, …
という列は
1 + 7 + ... + 7^n < 7^(n+1)
という性質があるので、和に含めるか含めないかを表す 01 ベクトルを二進数だと思って小さい順に調べればよい。

H.
DAG の最短経路の数え上げの特殊なケース。
最短経路長を求める DP をちょっと拡張すれば同時に個数も数えられる。

I.
読解が難しい。
使う色の順番を next_permutation で全部試して、色の順番を固定したあとは、できるだけ左のものから使っていく貪欲法を書いた。

J.
このセットで一番難しかった。
「数 a から数 b に遷移するための最小手数」が求められれば、あとは Warshall-Floyd して TSP すればいい。
値の上限が 10^9 と大きいので、全部の数を頂点にして BFS とかだとダメ。

二乗の操作に注目する。
1, 2, ..., ceil(√(10^9)) とこれらを二乗した数、および入力で与えられる a[0], ..., a[n-1] のみを頂点としたグラフを作る。
a から a^2 にコスト 1 の有向辺を張る。これは二乗する操作に対応している。

+2, +3, -2, -3 の操作は一つにまとめて処理する。
グラフの頂点 a から b へコスト d(a,b) の有向辺を張りたい。
ここで、d(a,b) は +2, +3, -2, -3 の操作だけを使ったときの最小コスト。
d(a,b) の値は |a-b| mod 3 の値によって分類できて、簡単に求まる。
これだと、辺数が O(V^2) もあって MLE or TLE するので、頂点の値でソートして隣接ノード間にだけ辺を張る、とかをしたい。
でもこれだとちょっとだけダメで、何がダメかというと、たとえば頂点 a, b, c がこの順に並んでいるとして、d(a,b) + d(b,c) が d(a,c) と等しくないかもしれない。
これは d が mod 3 で変な挙動をしていることによる。
そこで、頂点集合に、各頂点の値を +1, +2, +3, -1, -2, -3 したものも加えて、辺は自分の前後 6 個の頂点に張ることにする。
こうすると mod 3 でぐちゃぐちゃしているのもまぁ多分大丈夫で、あとはこのグラフで Dijkstra すればいい。

手元で -O2 をつけて 2.8 秒かかるけど、速いジャッジサーバーならタイムリミット 1 秒に間に合うはず。

K.
ふるいで素数を列挙して、あらかじめ必要な素数階乗数を全部作っておけばいい。
クエリは表引きするなり二分探索するなり線形探索するなりなんなり。

ソースコード

A.
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
puts((a+b+c+d+max(max(a,b),max(c,d)))/5>=60?"Yes":"No");
return 0;
}

B.
#include<cstdio>
#include<cstdlib>
#include<algorithm>

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

using namespace std;

int main(){
int w,h,q; scanf("%d%d%d",&w,&h,&q);

char B[50][51]={};
rep(i,h) rep(j,w) B[i][j]='.';
while(q--){
int x,y,L; scanf("%d%d%d",&x,&y,&L);
rep(i,h) rep(j,w) {
int d=max(abs(i-y),abs(j-x));
if((d+1)%(L+1)==0) B[i][j]=(B[i][j]=='.'?'#':'.');
}
}
rep(i,h) puts(B[i]);

return 0;
}

C.
#include<cstdio>
#include<cstring>

using namespace std;

int main(){
int n; scanf("%d",&n);
while(getchar()!='\n');

int ans1=0,ans2=0;
while(n--){
char s[301]; gets(s);
int len=strlen(s);
if(1<=len && len<=140){
if(s[0]=='@') ans2++; else ans1++;
}
}

if(ans1+ans2==0) puts("Tweet:NA Reply:NA");
else printf("Tweet:%d Reply:%d\n",100*ans1/(ans1+ans2),100*ans2/(ans1+ans2));

return 0;
}

D.
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
int n,q; scanf("%d%d",&n,&q);
int w[3000],v[3000];
rep(i,n) scanf("%d%d",w+i,v+i);

int dp[10001];
rep(j,10001) dp[j]=(j==0?0:-INF);
rep(i,n) for(int j=10000;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
rep(j,10000) dp[j+1]=max(dp[j+1],dp[j]);

while(q--){
int type; scanf("%d",&type);
if(type==0){
int W; scanf("%d",&W);
printf("%d\n",dp[W]);
}
else{
int i,W,V; scanf("%d%d%d",&i,&W,&V); i--;
w[i]=W;
v[i]=V;
rep(j,10001) dp[j]=(j==0?0:-INF);
rep(i,n) for(int j=10000;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
rep(j,10000) dp[j+1]=max(dp[j+1],dp[j]);
}
}

return 0;
}

E.
#include<map>
#include<string>
#include<iostream>

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

using namespace std;

int main(){
int n; cin>>n;
map<string,int> f;
rep(i,n){
string s; cin>>s;
f[s]=i;
}

int m; cin>>m;
bool G[17][17]={};
rep(i,m){
string s,t; cin>>s>>t;
int u=f[s],v=f[t];
G[u][v]=true;
}
rep(u,n) rep(v,u) if(G[u][v]==G[v][u]) { cout<<"No"<<endl; return 0; }

static bool dp[1<<17][17];
dp[1<<0][0]=true;
rep(S,1<<n) rep(u,n) if(S>>u&1 && dp[S][u]) rep(v,n) if((S>>v&1)==0 && G[u][v]) dp[S|1<<v][v]=true;

bool ok=false;
rep(u,n) if(dp[(1<<n)-1][u] && G[u][0]) ok=true;
cout<<(ok?"Yes":"No")<<endl;

return 0;
}

F.
#include<cmath>
#include<cstdio>
#include<vector>

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

using namespace std;

const double M=100;
const double EPS=1e-8;

struct point{
double 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}; }
};

point operator*(double c,const point &p){ return (point){c*p.x,c*p.y}; }

double dot(const point &a,const point &b){ return a.x*b.x+a.y*b.y; }

double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

double abs2(const point &a){ return a.x*a.x+a.y*a.y; }

struct line{ point a,b; };

struct segment{
point a,b;
operator line()const{ return (line){a,b}; }
};

struct circle{
point c;
double r;
};

point proj(const point &p,const line &L){ return L.a+dot(p-L.a,L.b-L.a)/abs2(L.b-L.a)*(L.b-L.a); }

double dist(const point &a,const point &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

bool cover(const segment &S,const point &p){ return dist(S.a,p)+dist(p,S.b)<dist(S.a,S.b)+EPS; }

bool cover(const circle &C,const point &p){ return dist(C.c,p)<C.r+EPS; }

int get_intersect(const circle &C,const segment &S,vector<point> &res){
point h=proj(C.c,S);
double d=dist(C.c,h);
if(d>C.r+EPS) return 0;
if(d>C.r-EPS){
int cnt=0;
if(cover(S,h)) res.push_back(h), cnt++;
return cnt;
}
else{
point v=S.b-S.a;
v=(sqrt(C.r*C.r-d*d)/abs(v))*v;
int cnt=0;
if(cover(S,h+v)) res.push_back(h+v), cnt++;
if(cover(S,h-v)) res.push_back(h-v), cnt++;
return cnt;
}
}

int get_intersect(const circle &C1,const circle &C2,vector<point> &res){
double r1=C1.r,r2=C2.r;
point p1=C1.c,p2=C2.c;

double d=abs(p1-p2);
if(d<EPS && abs(r1-r2)<EPS){ // C1==C2
return -1;
}
else if(r1+r2<d-EPS || d+EPS<abs(r1-r2)){
return 0;
}
else{
double a=(r1*r1-r2*r2+d*d)/(2*d);
double h=sqrt(max(r1*r1-a*a,0.0));
point tmp1=p1+a/d*(p2-p1);
point tmp2=h/d*(p2-p1);
if(abs(tmp2)<EPS){
res.push_back(tmp1);
return 1;
}
else{
res.push_back((point){tmp1.x-tmp2.y,tmp1.y+tmp2.x});
res.push_back((point){tmp1.x+tmp2.y,tmp1.y-tmp2.x});
return 2;
}
}
}

int main(){
int w,h,n; scanf("%d%d%d",&w,&h,&n);
point p[20];
rep(i,n) scanf("%lf%lf",&p[i].x,&p[i].y);

point corner[4];
corner[0]=(point){0,0};
corner[1]=(point){w,0};
corner[2]=(point){w,h};
corner[3]=(point){0,h};
segment wall[4];
wall[0]=(segment){corner[0],corner[1]};
wall[1]=(segment){corner[1],corner[2]};
wall[2]=(segment){corner[2],corner[3]};
wall[3]=(segment){corner[3],corner[0]};

double lo=0,hi=1e4;
rep(_,40){
double mi=(lo+hi)/2,r=mi;

circle C[20];
rep(i,n) C[i]=(circle){p[i],r};

vector<point> cand(corner,corner+4);
rep(j,n) rep(i,j) { // 円と円の交点のまわり
vector<point> Q;
get_intersect(C[i],C[j],Q);
if(Q.size()==2){
point a=Q[(int)Q.size()-1];
point b=Q[(int)Q.size()-2];
cand.push_back(a+M*EPS/abs(a-b)*(a-b)); // 二交点を結んだ直線に沿ってちょっとずらした点を候補にする
cand.push_back(b+M*EPS/abs(b-a)*(b-a));
}
}
rep(i,n){ // 円と壁の交点のまわり
vector<point> Q;
rep(j,4) get_intersect(C[i],wall[j],Q);
rep(j,Q.size()){ // 上下左右にちょっとずらした点を候補にする
cand.push_back(Q[j]+(point){+M*EPS,0});
cand.push_back(Q[j]+(point){-M*EPS,0});
cand.push_back(Q[j]+(point){0,+M*EPS});
cand.push_back(Q[j]+(point){0,-M*EPS});
}
}

bool ok=true;
rep(i,cand.size()){
point a=cand[i];
if(0<=a.x && a.x<=w && 0<=a.y && a.y<=h){
bool ok2=false;
rep(j,n) if(cover(C[j],a)) { ok2=true; break; }
if(!ok2){ ok=false; break; }
}
}
if(ok) hi=mi; else lo=mi;
}

printf("%.9f\n",(lo+hi)/2);

return 0;
}

G.
#include<cstdio>

using namespace std;

typedef long long ll;

const ll M=1000000;

int main(){
int n; scanf("%d",&n);

ll ans=0,seven=1;
while(n>0){
if(n&1) ans=(ans+seven)%M;
n>>=1;
seven=seven*7%M;
}
printf("%lld\n",ans);

return 0;
}

H.
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int M=1000000;
const int INF=1<<29;

int main(){
int m,n,c; scanf("%d%d%d",&n,&m,&c);
bool cat[21][21]={};
rep(i,c){
int x,y; scanf("%d%d",&x,&y);
cat[y][x]=true;
}

int dist[21][21],dp[21][21]={};
rep(i,m+1) rep(j,n+1) dist[i][j]=INF;
dist[0][0]=0;
dp[0][0]=1;
rep(i,m+1) rep(j,n+1) if(dist[i][j]<INF) {
int d=dist[i][j];

bool jump=true;
for(int y=max(i-1,0);y<=min(i+1,m);y++) for(int x=max(j-1,0);x<=min(j+1,n);x++) if(cat[y][x]) jump=false;
if(jump && i<m && j<n){
if (dist[i+1][j+1]> d+1) dist[i+1][j+1]=d+1, dp[i+1][j+1]=dp[i][j];
else if(dist[i+1][j+1]==d+1) dp[i+1][j+1]+=dp[i][j];
dp[i+1][j+1]%=M;
}

if(i<m && !cat[i+1][j]){
if (dist[i+1][j]> d+1) dist[i+1][j]=d+1, dp[i+1][j]=dp[i][j];
else if(dist[i+1][j]==d+1) dp[i+1][j]+=dp[i][j];
dp[i+1][j]%=M;
}

if(j<n && !cat[i][j+1]){
if (dist[i][j+1]> d+1) dist[i][j+1]=d+1, dp[i][j+1]=dp[i][j];
else if(dist[i][j+1]==d+1) dp[i][j+1]+=dp[i][j];
dp[i][j+1]%=M;
}
}

printf("%d\n",dp[m][n]);

return 0;
}

I.
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

int main(){
int n,m;
char s[6],t[100001];
scanf("%d%s%d%s",&n,s,&m,t);

vector<int> pos[128];
rep(i,m) pos[t[i]].push_back(i);

int ans=0;
sort(s,s+n);
do{
int tmp=0;
int iter[128]={};
while(1){
bool ok=true;
int pre=-1;
rep(i,n){
char c=s[i];
while(iter[c]<pos[c].size() && pos[c][iter[c]]<pre) iter[c]++;
if(iter[c]==pos[c].size()){ ok=false; break; }
pre=pos[c][iter[c]++];
}
if(!ok) break;
tmp++;
}
ans=max(ans,tmp);
}while(next_permutation(s,s+n));

printf("%d\n",ans);

return 0;
}

J.
#include<queue>
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

struct edge{ int v,cost; };

int calc_dist(int u,int v){
int d=abs(u-v);
return d%3==1?d/3+2:(d+1)/3;
}

void Dijkstra(int n,const vector<edge> *G,int s,int *d){
rep(u,n) d[u]=(u==s?0:INF);
priority_queue< pair<int,int> > Q; Q.push(make_pair(0,s));
while(!Q.empty()){
int d_now=-Q.top().first,u=Q.top().second; Q.pop();
rep(i,G[u].size()){
int v=G[u][i].v,cost=G[u][i].cost;
if(d[v]>d[u]+cost){
d[v]=d[u]+cost;
Q.push(make_pair(-d[v],v));
}
}
}
}

const int V_MAX=11;
int TSP(int n,const int d[V_MAX][V_MAX]){
static int dp[1<<V_MAX][V_MAX];
rep(S,1<<n) rep(u,n) dp[S][u]=INF;
rep(u,n) dp[1<<u][u]=0;
rep(S,1<<n) rep(u,n) if(S>>u&1) {
rep(v,n) if((S>>v&1)==0) dp[S|1<<v][v]=min(dp[S|1<<v][v],dp[S][u]+d[u][v]);
}
int res=INF;
rep(t,n) res=min(res,dp[(1<<n)-1][t]);
return res;
}

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

vector<int> V;
rep(i,n) for(int j=-3;j<=3;j++) V.push_back(a[i]+j);
rep(i,32000){
for(int j=-3;j<=3;j++) V.push_back(i+j);
for(int j=-3;j<=3;j++) V.push_back(i*i+j);
}
rep(i,100) V.push_back(-i);
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());

static vector<edge> G[260000];
rep(i,32000){
int u=lower_bound(V.begin(),V.end(),i)-V.begin();
int v=lower_bound(V.begin(),V.end(),i*i)-V.begin();
G[u].push_back((edge){v,1});
}
rep(u,V.size()){
for(int v=max(u-6,0);v<=min(u+6,(int)V.size()-1);v++){
G[u].push_back((edge){v,calc_dist(V[u],V[v])});
}
}

int d[11][11];
rep(i,n){
int u=lower_bound(V.begin(),V.end(),a[i])-V.begin();
static int dist[260000];
Dijkstra(V.size(),G,u,dist);
rep(j,n){
int v=lower_bound(V.begin(),V.end(),a[j])-V.begin();
d[i][j]=dist[v];
}
}
rep(k,n) rep(i,n) rep(j,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

printf("%d\n",TSP(n,d));

return 0;
}

K.
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

typedef long long ll;

const int P_MAX=10000000;
vector<int> P;
void sieve(){
static bool er[P_MAX+1];
rep(i,P_MAX+1) er[i]=(i>=2);
for(int i=2;i*i<=P_MAX;i++) if(er[i]) for(int j=i*i;j<=P_MAX;j+=i) er[j]=false;
rep(i,P_MAX+1) if(er[i]) P.push_back(i);
}

int main(){
sieve();

vector<int> ans(1,1);
rep(i,P.size()) ans.push_back((ll)ans.back()*P[i]%1000000);
sort(ans.begin(),ans.end());

int T; scanf("%d",&T);
while(T--){
int a; scanf("%d",&a);
puts(binary_search(ans.begin(),ans.end(),a)?"Yes":"No");
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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