スポンサーサイト

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

VKPC

2011/08/28 に ATCODER で開催された VKPC の問題セットを今さらながら解いた。
せっかくなのでソースコードを公開しようと思う。

Tags : プログラミング VKPC

ソースコード

A.
#include<cmath>
#include<cstdio>

using namespace std;

int main(){
int a,b,m; scanf("%d%d%d",&a,&b,&m);
printf("%.0f\n",(log(b)-log(a))/log(m));
return 0;
}

// a*m^n = b
// n = (log b - log a)/(log m)

log で O(1).

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

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

using namespace std;

int main(){
int m; scanf("%d ",&m);
char s[100][101];
rep(i,m) gets(s[i]);

int n; scanf("%d ",&n);
bool chk[100]={};
rep(i,n){
char t[256]; gets(t);
*strchr(t,':')='\0';
rep(j,m) if(strcmp(s[j],t)==0) chk[j]=true;
}

puts(count(chk,chk+m,true)==m?"yes":"no");

return 0;
}

文字列操作。 strchr() かわいい。

C.
#include<cstdio>
#include<algorithm>

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

using namespace std;

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

int ans=21;
rep(S,1<<m){
int pc=0,sum=0;
rep(i,m) if(S&(1<<i)) pc++, sum+=a[i];
if(sum==n) ans=min(ans,pc);
}
if(ans<21) printf("%d\n",ans); else puts("NA");

return 0;
}

全探索。

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

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

using namespace std;

typedef pair<int,int> pii;

int main(){
int n; scanf("%d",&n);
pii ch[100000];
rep(i,n) scanf("%d%d",&ch[i].first,&ch[i].second);
sort(ch,ch+n);

int m; scanf("%d",&m);
rep(i,m){
int T; scanf("%d",&T);
int ans=0,t=0;
rep(i,n){
t=max(t,ch[i].first);
t+=ch[i].second;
if(t<=T) ans++;
}
printf("%d\n",ans);
}

return 0;
}

シミュレーションのようなもの。
最初は書きにくそうに思えたけど、かなりシンプルに書ける。

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

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

using namespace std;

typedef pair<int,int> pii;

const int M=1000000007;

int main(){
int m,n,k; scanf("%d%d%d",&m,&n,&k); m++; n++;
static bool cat[1001][1001];
vector<pii> C;
rep(i,k){
int a,b,r; scanf("%d%d%d",&a,&b,&r);
if(r==1) C.push_back(make_pair(a,b));
if(r==2) cat[a][b]=true;
}
C.push_back(make_pair( 0 , 0 ));
C.push_back(make_pair(m-1,n-1));
sort(C.begin(),C.end());
C.erase(unique(C.begin(),C.end()),C.end());

static int dp[1001][1001];
dp[0][0]=1;
rep(k,(int)C.size()-1){
int y0=C[ k ].first,x0=C[ k ].second;
int y1=C[k+1].first,x1=C[k+1].second;
for(int i=y0;i<=y1;i++) for(int j=x0;j<=x1;j++) if((i>y0 || j>x0) && !cat[i][j]) {
if(i>0 && !cat[i-1][j]) dp[i][j]+=dp[i-1][j];
if(j>0 && !cat[i][j-1]) dp[i][j]+=dp[i][j-1];
dp[i][j]%=M;
}
}
printf("%d\n",dp[m-1][n-1]);

return 0;
}

よくある DP のちょっとした応用。
必ず通った場所を端点とする長方形に問題を分割する。

F.
#include<cstdio>
#include<cstring>
#include<algorithm>

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

using namespace std;

int main(){
int n; scanf("%d",&n);
char s[100][101];
rep(i,n) scanf("%s",s[i]);

int m=strlen(s[0]),ans=0;
rep(j,m+1) rep(i,j) {
char t[101];
strncpy(t,s[0]+i,j-i); t[j-i]='\0';

bool ok=true;
rep(k,n) if(!strstr(s[k],t)) ok=false;
if(ok) ans=max(ans,j-i);
}
printf("%d\n",ans);

return 0;
}

O(n length3) で通った。
strncpy() が最後に null 文字を追加してくれないことを知らなくてはまった。
strstr() かわいい。

G.
#include<cstdio>
#include<cassert>

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

using namespace std;

int main(){
int n,t; scanf("%d%d",&n,&t);
int m[51]={},to[50][3];
int sz=0,pre[150],now[150];
rep(i,n){
scanf("%d",m+i);
rep(j,m[i]){
scanf("%d",to[i]+j);
pre[sz]=i;
now[sz]=to[i][j];
sz++;
}
}

double A[151][151]={};
rep(j,sz){
int i[3],c=0;
rep(k,m[now[j]]){
int &ii=i[k];
for(ii=0;ii<sz;ii++) if(now[ii]==to[now[j]][k] && pre[ii]==now[j]) break;
assert(ii<sz);
if(now[ii]!=pre[j]) c++;
}

if(c==0) A[j][j]=1;
else{
rep(k,m[now[j]]) if(now[i[k]]!=pre[j]) A[i[k]][j]=1.0/c;
}
}
rep(i,sz) if(pre[i]==0) A[i][sz]=1.0/m[0];
sz++;

double v[151]={}; v[sz-1]=1;
rep(l,31){
if(t&(1<<l)){
double v2[151]={};
rep(i,sz) rep(j,sz) v2[i]+=A[i][j]*v[j];
rep(i,sz) v[i]=v2[i];
}

double A2[151][151]={};
rep(i,sz) rep(j,sz) rep(k,sz) A2[i][j]+=A[i][k]*A[k][j];
rep(i,sz) rep(j,sz) A[i][j]=A2[i][j];
}

double ans=0;
rep(i,sz) if(now[i]==n) ans+=v[i];
printf("%.9f\n",ans);

return 0;
}

解けなかったので、作題者の hyon さんに直接答えを聞いた。
遷移行列を作って行列べき乗。
各状態は、今聞き込みをしている人と直前に聞き込みをした人のペアを状態にする。
m ≦ 3 の条件があるので、状態数は 150 くらいに抑えられて、全体で 150^3 log t になって間に合う。
いい問題だと思う。

H.
#include<set>
#include<cstdio>

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

using namespace std;

typedef long long ll;

ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

inline int popcount(ll x){
x-=(x>>1)&0x5555555555555555LL;
x=(x&0x3333333333333333LL)+((x>>2)&0x3333333333333333LL);
x=(x+(x>>4))&0x0f0f0f0f0f0f0f0fLL;
x=(x*0x0101010101010101LL)>>56;
return x;
}

int main(){
ll a,b,c,x; scanf("%lld%lld%lld%lld",&a,&b,&c,&x);

ll x2,y;
xgcd(a,c,x2,y);
x2*=-b;
x2%=c; if(x2<0) x2+=c;

int ans=77;
set<ll> S;
while(1){
if(S.count(x)) break;

ans=min(ans,popcount(x^x2));

S.insert(x);
x=(a*x+b)%c;
}

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

return 0;
}

A と C が互いに素の仮定から、
A X + B = 0 mod C
は解けるので解けばいい。
拡張ユークリッド互除法。

I.
#include<cctype>
#include<cstdio>

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

using namespace std;

struct bigint{
bool sgn;
int a[100];

bigint(){
sgn=true;
rep(i,100) a[i]=0;
}

bigint(int b){
sgn=(b>=0);
if(b<0) b=-b;
char s[101]; sprintf(s,"%0100d",b);
rep(i,100) a[i]=s[99-i]-'0';
}

void print(){
if(!sgn) putchar('-');
bool ok=false;
for(int i=99;i>0;i--) if(ok || a[i]!=0) {
putchar('0'+a[i]);
ok=true;
}
printf("%c\n",'0'+a[0]);
}
};

bigint operator+(bigint A,bigint B);
bigint operator-(bigint A,bigint B);

bigint operator+(bigint A,bigint B){
if(!A.sgn){
A.sgn=true;
return B-A;
}
if(!B.sgn){
B.sgn=true;
return A-B;
}

bigint C;
rep(i,99){
int d=A.a[i]+B.a[i]+C.a[i];
C.a[i]=d%10;
if(d>=10) C.a[i+1]++;
}
return C;
}

bigint operator-(bigint A,bigint B){
if(!B.sgn){
B.sgn=true;
return A+B;
}
if(!A.sgn){
A.sgn=true;
bigint C=A+B;
C.sgn=false;
return C;
}

bool ok=true;
for(int i=99;i>=0;i--){
if(A.a[i]>B.a[i]) break;
if(A.a[i]<B.a[i]){ ok=false; break; }
}
if(!ok){
bigint C=B-A;
C.sgn=false;
return C;
}

bigint C;
rep(i,99){
int d=A.a[i]-B.a[i]+C.a[i];
C.a[i]=(d+10)%10;
if(d<0) C.a[i+1]--;
}
return C;
}

int main(){
int id[128]; id['X']=0; id['Y']=1;

bigint x[2]={};
for(char s[16];gets(s);){
char c1=s[4],c2=s[6];
int i1=id[c1],i2=id[c2];

if(s[0]=='A'){ // ADD
if(c2=='-' || isdigit(c2)){
int a; sscanf(s+6,"%d",&a);
x[i1]=x[i1]+bigint(a);
}
else{
x[i1]=x[i1]+x[i2];
}
}
if(s[0]=='S'){ // SUB
if(c2=='-' || isdigit(c2)){
int a; sscanf(s+6,"%d",&a);
x[i1]=x[i1]-bigint(a);
}
else{
x[i1]=x[i1]-x[i2];
}
}
if(s[0]=='I'){ // INC
x[i1]=x[i1]+bigint(1);
}
if(s[0]=='D'){ // DEC
x[i1]=x[i1]-bigint(1);
}
}

rep(i,2) x[i].print();

return 0;
}

シミュレーション。ただし多倍長。
てきとーに多倍長を実装したらバグを埋め込みまくってひどい目にあった。

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

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

using namespace std;

const int INF=1<<29;
const double EPS=1e-4;

struct Point3{
double x,y,z;
Point3 operator-(const Point3 &p)const{ return (Point3){x-p.x,y-p.y,z-p.z}; }
};

double dot(const Point3 &p,const Point3 &q){
return p.x*q.x+p.y*q.y+p.z*q.z;
}

Point3 cross(const Point3 &p,const Point3 &q){
return (Point3){p.y*q.z-p.z*q.y,
p.z*q.x-p.x*q.z,
p.x*q.y-p.y*q.x};
}

int n,dp[1<<12];
Point3 p[12][3];

// -1 : 平面 i と三角形 j が交差
// 0 : 平面 i の上に三角形 j が乗っている
// 1 : 平面 i の表側に三角形 j がある
// 2 : 平面 i の裏側に三角形 j がある
int docchi(int i,int j){
Point3 v1=p[i][1]-p[i][0];
Point3 v2=p[i][2]-p[i][0];
Point3 no=cross(v1,v2); // p[i][0] を通る平面 i の法線ベクトル

// 平面 i の方程式 ax+by+cz=d
double a=no.x,b=no.y,c=no.z;
Point3 coe={a,b,c};
double d=dot(coe,p[i][0]);

int res[2]={};
rep(k,3){
double tmp=dot(coe,p[j][k]);
if(tmp<d-EPS) res[0]++;
if(tmp>d+EPS) res[1]++;
}
if(res[0]>0 && res[1]>0) return -1;
if(res[0]>0) return 1;
if(res[1]>0) return 2;
return 0;
}

int dfs(int S){
if(~dp[S]) return dp[S];

if(S==0) return dp[S]=0;
rep(i,n) if(S==(1<<i)) return dp[S]=0;

int ans=INF;
rep(i,n){
int L=0,R=0;
bool cut=false;
rep(j,n) if(S&(1<<j)) {
int b=docchi(i,j); // 三角形 i で指定される平面のどっち側に三角形 j があるか
if(b==-1) cut=true;
if(b== 1) L|=1<<j;
if(b== 2) R|=1<<j;
}
if(!cut && S!=L && S!=R) ans=min(ans,1+max(dfs(L),dfs(R)));
}
if(ans==INF) ans=0; // 分割できる平面がない

return dp[S]=ans;
}

int main(){
for(;scanf("%d",&n),n;){
memset(dp,-1,sizeof dp);
rep(i,n) rep(j,3) scanf("%lf%lf%lf",&p[i][j].x,&p[i][j].y,&p[i][j].z);
printf("%d\n",dfs((1<<n)-1));
}
return 0;
}

空間幾何 + メモ化。
平面の方程式 ax+by+cz = d に対して、
三角形の 3 つの頂点すべてが ax+by+cz ≦ d なら表側
三角形の 3 つの頂点すべてが ax+by+cz ≧ d なら裏側
ax+by+cz < d, ax+by+cz > d となっている頂点がそれぞれ 1 つ以上あるなら交差
三角形の 3 つの頂点すべてが ax+by+cz = d なら平面に乗っている
とすれば判定できる。

平面との距離が 10^-7 以下ならどうこうと書かれていたけど、平面と点の距離を計算するのが面倒だったので、適当に EPS を設定してごまかした。
EPS を変えながら再提出しつづけたら通った。

私は高専卒なので知らないんですが、高校の数学で勉強する内容だと思います。

K.
#include<queue>
#include<cstdio>
#include<cstring>

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

using namespace std;

typedef pair<int,int> pii;

int main(){
int n; scanf("%d",&n);
int d1[1000],t1[1000],d2[1000],t2[1000];
rep(i,n) scanf("%d%d%d%d",d1+i,t1+i,d2+i,t2+i);

int ans=-1,memo[1000];
memset(memo,-1,sizeof memo);
queue< pair<int,pii> > qu; qu.push(make_pair(0,make_pair(0,0)));
while(!qu.empty()){
int cost=qu.front().first;
int div=qu.front().second.first;
int t=qu.front().second.second; qu.pop();

if(div>=1000000){
ans=cost;
break;
}

rep(i,n) if(memo[i]==-1 && t1[i]>=t && d1[i]==div) {
memo[i]=cost+1;
qu.push(make_pair(cost+1,make_pair(d2[i],t2[i])));
}
}

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

return 0;
}

問題文が読めれば、ただの BFS + メモ化 であることに気づく。

L.
#include<cmath>
#include<cstdio>

using namespace std;

int main(){
long long n; scanf("%lld",&n);
printf("%d\n",(int)sqrt(n-1));
return 0;
}

世界 i が α ⇔ i は奇数個の約数をもつ
であることが容易にわかる。
さらに、
i は奇数個の約数をもつ ⇔ i は平方数
であるので、n 以下の平方数の個数を数えればいい。
sqrt で O(1).
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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