スポンサーサイト

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

ZOJ Monthly, September 2012

先月と同じチームで参加。
結果は先月よりよかったけど素直に喜べるほどよくはない。

Tags : プログラミング ZOJ

結果

チームとしては 7/11 完。
自分は易しめの A, C を解いた。貢献度低い。

問題

A. Kitty's Game
頂点に重みがついた有向グラフがある。パスの重みとは通った頂点の重みの最小公倍数のこと。頂点 1 から n へのパスで重みがちょうど K となるものは何通りあるか? mod 10^9+7 で求めよ。ただし、パスを辿る際には、始点から今いる頂点までの重みが strict に増えていかなければならない。

2 ≦ |V |≦ 2000
2 ≦ |E| ≦ 20000
2 ≦ K ≦ 10^6

C. Matrix Transformer
n×n の 0-1 行列があり、任意の二行or二列を選んでスワップしてよい。対角線 (1,1)-(n,n) 上の要素をすべて 1 にできるかどうか判定せよ。

1 ≦ n ≦ 200

D. Gao the Grid
W×H のグリッドの交点を三つ選んで結び三角形を作る方法は何通りあるか?
縮退して一直線になっているものはカウントしない。

1 ≦ W, H ≦ 1000

解答

A.
DP。
dp[i][u] := ( 頂点 1 から頂点 u までの重み i のパスの総数 )。
重みが strict に増えるという条件から dp の更新に変なループはできない。
i として考えるのは K の約数だけでいい。なぜなら一度 i が K を割り切らなくなるとその後どう進んでもパスの重みが K になることはないから。
K の約数は高々 240 個くらいだったはずなので間に合う。

C.
よくある行から列へのフロー。
1 のあるところに辺を張ったグラフで n 単位のフローが流れればよい。

D.
三角形こわい。
この方のブログを参考にして解いた。
まず、答えは
( 任意の三点の選ぶ方法の数 ) - ( 同一直線にある三点を選ぶ方法の数 )
で、第一項はすぐわかるので第二項を求めるのが本題。
同一直線上にある三点のうち、両端の二点 (x1,y1), (x2,y2) を固定すると、三つめの点として取れるのは gcd(|x1-x2|,|y1-y2|)-1 通りある。( これは蟻本にも書いてる。)
両端の二点を全列挙するわけにはいかないので、ここを工夫する。
平行移動して一致する線分をまとめて数える。
つまり、(x1,y1) = (0,0) とする。すると、この線分 (0,0) - (x2,y2) は x 方向に W-x2、y 方向に H-y2 だけずらすことができるので、この線分はグリッド中に (W-x2)・(H-y2)・(gcd(|x2|,|y2|)-1) 個ある。
これを x2, y2 について全探索すればよい。
ふつうにやると O(WH log(WH))。
GCD の計算をメモ化すれば O(WH) になる。
かしこいなぁ。

ソースコード

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

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

using namespace std;

typedef long long ll;

const ll M=1000000007;

int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int lcm(int a,int b){ return a/gcd(a,b)*b; }

vector<int> divisor(int a){
vector<int> res;
for(int i=1;i*i<=a;i++) if(a%i==0) {
res.push_back(i);
if(i*i<a) res.push_back(a/i);
}
return res;
}

int main(){
for(int n,m,k;~scanf("%d%d%d",&n,&m,&k);){
static vector<int> G[2000];
rep(u,n) G[u].clear();
rep(i,m){
int u,v; scanf("%d%d",&u,&v); u--; v--;
G[u].push_back(v);
}

static int val[2000];
rep(u,n) scanf("%d",val+u);

vector<int> d=divisor(k);
sort(d.begin(),d.end());

static int pos[1000001];
rep(i,k+1) pos[i]=-1;
rep(i,d.size()) pos[d[i]]=i;

static ll dp[256][2000];
memset(dp,0,sizeof dp);
if(k%val[0]==0) dp[pos[val[0]]][0]=1;
rep(t,d.size()){
rep(u,n) rep(i,G[u].size()) {
int v=G[u][i];
if(k%val[v]==0){
int L=lcm(d[t],val[v]);
if(d[t]<L && L<=k && pos[L]!=-1){
dp[pos[L]][v]+=dp[t][u];
dp[pos[L]][v]%=M;
}
}
}
}

printf("%lld\n",dp[(int)d.size()-1][n-1]);
}

return 0;
}


C.
#include<cstdio>
#include<vector>

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

using namespace std;

const int V_MAX=200;

bool augment(int u,bool *vis,int match[2][V_MAX],const vector<int> *G){
if(u==-1) return true;

rep(i,G[u].size()){
int v=G[u][i];
if(!vis[v]){
vis[v]=true;
if(augment(match[1][v],vis,match,G)){
match[0][u]=v;
match[1][v]=u;
return true;
}
}
}
return false;
}

int bipartite_matching(int L,int R,const vector<int> *G){
static int match[2][V_MAX];
rep(u,L) match[0][u]=-1;
rep(v,R) match[1][v]=-1;

int res=0;
static bool vis[V_MAX];
rep(u,L){
rep(v,R) vis[v]=false;
if(augment(u,vis,match,G)) res++;
}
return res;
}

int main(){
for(int n;~scanf("%d",&n);){
static char B[200][201];
rep(i,n) scanf("%s",B[i]);

vector<int> G[200];
rep(i,n) rep(j,n) if(B[i][j]=='U') G[i].push_back(j);

puts(bipartite_matching(n,n,G)==n?"YES":"NO");
}

return 0;
}


D.
#include<cstdio>

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

using namespace std;

typedef long long ll;

int gcd(int a,int b){ return b?gcd(b,a%b):a; }

ll nC3(int n){ return (ll)n*(n-1)*(n-2)/6; }

int main(){
for(int h,w;~scanf("%d%d",&h,&w);){
h++; w++;

ll ans=nC3(h*w);
rep(i,h) rep(j,w) if(i+j>0) {
ll c;
if(i>0&&j>0) c=2;
else c=1;
ans-=c*(gcd(i,j)-1)*(h-i)*(w-j);
}
printf("%lld\n",ans);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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