スポンサーサイト

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

BUET Inter-University Programming Contest - 2011

2012/02/18 18:00~23:00 (JST)
BUET Inter-University Programming Contest - 2011 の参加記録

5 時間で 9 問。
外出先で問題だけ読んで、20 時くらいに帰宅してからコーディングをはじめた。

Tags : プログラミング UVa 未解決

結果

A. -
B. -
C. AC (04:40)
D. -
E. WA, AC (03:33)
F. -
G. -
H. -
I. -
Standing : 31/109


問題

問題セットの原文はここを参照。

B. Best Friend (UVa 12425)

正整数 N が与えられる。
Q 個のクエリ
「gcd(N, i) ≦ X となる i = 1, 2, ..., N の個数を求めよ」
を処理せよ。

0 < N ≦ 10^12
0 < Q ≦ 10^12
X は signed 64 bit integer におさまる

C. Counting Triangles (UVa 12426)

N 頂点の凸多角形が与えられる。
頂点を 3 つ選んでできる三角形のうち、面積が K 以下であるものの個数を求めよ。

1 ≦ テストケース数 ≦ 10
3 ≦ N ≦ 1000
1 ≦ K ≦ 10^15

D. Donkey of the Sultan (UVa 12427)

1 × R の盤上で二人でゲームをする。 ( R は十分大きい数 )
盤上のマスには左から順に 0, 1, 2, ... と番号がつけられている。

自分は 3 枚のコイン ( 金, ダイヤ, 銀 ) をマスの上に置く。
このとき、
・ 金コインはマス 0 から a1 以上 a2 以下だけ左側に、
・ ダイヤコインは金コインから b1 以上 b2 以下だけ左側に、
・ 銀コインはダイヤコインから c1 以上 c2 以下だけ左側に、
置かないといけない。

プレイヤーは順番にプレイする。
相手が先行。
一ターンにできる操作は
・ 金コインを一マス左に動かす
・ ダイヤコインを一マス左に動かす
・ 銀コインを一マス左に動かす
・ 金コインと銀コインを同時に一マス左に動かす
のいずれか一つ。
コインが重なったり、盤の外に出てはいけない。
手がなくなったほうの負け。

先手必勝の初期配置は何通りあるか?

0 ≦ a1 ≦ a2 ≦ 10^5
0 ≦ b1 ≦ b2 ≦ 10^5
0 ≦ c1 ≦ c2 ≦ 10^5

E. Enemy at the Gates (UVa 12428)

N 頂点、M 辺の連結単純無向グラフで、critical edge ( その辺を除くとグラフが非連結になるような辺 ) は最大いくつできるか?
最大値を求めよ。

2 ≦ N ≦ 10^5
1 ≦ M ≦ N(N-1)/2

F. Finding Magic Triplets (UVa 12429)

n, k : given

a + b^2 = c^3 (mod k) ( 1 ≦ a ≦ b ≦ c ≦ n )
をみたす (a, b, c) の組は何通りあるか?

1 ≦ n ≦ 10^5
1 ≦ k ≦ 10^5

G. Grand Wedding (UVa 12430)

頂点数 N、辺数 M の重みつき無向グラフがあたえられる。

グラフの各頂点に警備員を置くか置かないか決める。
このとき、すべての辺に対して、ちょうど一方の端にだけ警備員がいるようにしたい。
必要であれば、重み K 以上の辺をすべて取り除いていい。 ( ただしすべての辺を取り除いてはいけない )
K の最小値を求めよ。
一本も取り除かなくてもいい場合は 0, すべて取り除かないといけないときは -1 と答えよ。

1 ≦ N ≦ 50000
1 ≦ M ≦ 80000

H. Happy 10/9 Day (UVa 12431)

( b 進数表示で d が n 個ならぶ数 ) mod M を求めよ。
出力は 10 進数。

1 ≦ テストケース数 ≦ 1000
2 ≦ b ≦ 100
1 ≦ d < min(10, b)
1 ≦ n ≦ 10^12
1 ≦ M ≦ 10^12

解答

言語は C++。テンプレはここを参照。

B. ( 2012/02/20 )
vector<ll> divisor(ll a){
vector<ll> res;
for(ll 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;
}

ll phi(ll a){
ll res=a;
for(ll p=2;p*p<=a;p++) if(a%p==0) {
res=res/p*(p-1);
do{ a/=p; }while(a%p==0);
}
if(a>1) res=res/a*(a-1);
return res;
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
printf("Case %d\n",T);

ll n;
int q; scanf("%lld%d",&n,&q);

vector<ll> D=divisor(n);
sort(D.begin(),D.end());

// g[i] := ( gcd(n,j) == D[i] となる j = 1, 2, ..., n の個数 )
static ll g[6720];
rep(i,D.size()) g[i]=phi(n/D[i]);

// g[i] := ( gcd(n,j) <= D[i] となる j = 1, 2, ..., n の個数 )
rep(i,(int)D.size()-1) g[i+1]+=g[i];

while(q--){
ll x; scanf("%lld",&x);
printf("%lld\n",g[upper_bound(D.begin(),D.end(),x)-D.begin()-1]);
}
}

return 0;
}

[ 2012/02/20 追記 ]

gcd(N, i) の値は N の約数にしかならない。
N ≦ 10^12 のとき、N の約数は高々 6720 個。

前処理として、N の約数を全列挙し、各約数 d について
g(d) := ( gcd(N, i) = d なる i = 1, 2, ..., N の個数 )
をすべて求めておく。
gcd(N, i) = d
gcd(N/d, i/d) = 1
と同値。
つまり g(d) = φ(N/d) となる。
一つ一つ O(√(N/d)) でやって間に合った。

あとは、各クエリに対して、二分探索で答えが出せる。

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

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

template<class T>
T area2(const point<T> &a,const point<T> &b,const point<T> &c){
return llabs(cross(b-a,c-a));
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n;
ll k; scanf("%d%lld",&n,&k);
point<ll> p[1000];
rep(i,n) scanf("%lld%lld",&p[i].x,&p[i].y);

ll ans=0;
rep(j,n) rep(i,j) if(j+1<=n-1) {
int lo=j+1,hi=n-1;
while(lo<hi){
int mi1=(lo+hi)/2,mi2=mi1+1;
ll a1=area2(p[i],p[j],p[mi1%n]);
ll a2=area2(p[i],p[j],p[mi2%n]);
if(a1<a2) lo=mi1+1;
else hi=mi2-1;
}

const int top=lo;
lo=j;
hi=top-1;
while(lo<hi){
int mi=(lo+hi+1)/2;
if(area2(p[i],p[j],p[mi%n])<=2*k) lo=mi; else hi=mi-1;
}
ans+=lo-j;

lo=top+1;
hi=n+i;
while(lo<hi){
int mi=(lo+hi)/2;
if(area2(p[i],p[j],p[mi%n])<=2*k) hi=mi; else lo=mi+1;
}
ans+=max(n-lo,0);

if(area2(p[i],p[j],p[top%n])<=2*k) ans++;
}

printf("%lld\n",ans);
}

return 0;
}

問題文に制約が書いていないので注意。pdf には書いてある。

方針自体はすぐに立ったけど、気を抜くとすぐにバグを埋め込みそうだったので、何度もテストしながらかなり慎重に書いた。
結果、ちょうど 1 時間で書きあがって一発 AC できたので満足。

頂点を反時計回りで番号付けて 0, 1, .., N-1 とする。
三角形 i-j-k ( 0 ≦ i < j < k < N ) をさがすようにすれば重複カウントしない。
まず、二頂点 i, j を決めうちする。
k = j+1, j+2, ..., N-1 と動くにつれ、三角形 i-j-k の面積は途中まで増えて、そのあと減るという形になるのがポイント。
つまり、この関数は k について凸。

三つめの頂点 k' ( j < k' < N ) で i-j-k' の面積が最大になるものを三分探索で探す。
k' がみつかれば、面積が K 以下になる境目の点を j から k' の間の二分探索、k' から N-1 の間の二分探索でそれぞれ求める。
あとはまとめて数え上げればいい。
k = k' のときを重複カウントしないように注意。

O(n^2 log n)

類題は POJ 2500 : Pia's Party ( 解説 )
今回の問題よりは簡単。

D. ( あとで解いた )
// code for experiment
// bool dfs(int a,int b,int c){
// if(a>0 && !dfs(a-1,b+1,c)) return true;
// if(b>0 && !dfs(a,b-1,c+1)) return true;
// if(c>0 && !dfs(a,b,c-1)) return true;
// if(a>0 && c>0 && !dfs(a-1,b+1,c-1)) return true;
// return false;
// }

int main(){
// code for experiment
// int a1=1,a2=5,b1=1,b2=5,c1=1,c2=5;
// for(int a=a1;a<=a2;a++){
// for(int b=b1;b<=b2;b++){
// for(int c=c1;c<=c2;c++){
// printf("%d, %d, %d: %s\n",a,b,c,!dfs(a,b,c)?"win":"lose");
// }
// }
// }

int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int a1,a2,b1,b2,c1,c2; scanf("%d%d%d%d%d%d",&a1,&a2,&b1,&b2,&c1,&c2);
if(a1%2==1) a1++;
if(a2%2==1) a2--;
if(c1%2==1) c1++;
if(c2%2==1) c2--;
printf("Case %d: %lld\n",T,(ll)((a2-a1)/2+1)*(b2-b1+1)*((c2-c1)/2+1));
}

return 0;
}

Nim と思うと、二つ以上の山を同時に操作することになるのでよくわからない。

実験すればすぐにルールがわかると聞いたので実験してみた。
0 - 金 の間の距離を a
金 - ダイヤ の間の距離を b
ダイヤ - 銀 の間の距離を c とすると、
必勝の配置 ⇔ a, c が偶数
であることが見ればわかる。
なんでこれでいいんだろう??

E.
int main(){
int T; scanf("%d",&T);
while(T--){
int n;
ll m; scanf("%d%lld",&n,&m);

ll i; // i : クリークの頂点数
for(i=1;i*(i-1)/2+(n-i)<m;i++);

printf("%lld\n",n-i);
}

return 0;
}

critical edge というのは、要するに

-(グラフ)-(グラフ)-(グラフ)-

という感じにグラフを模式的に書いたときの - のこと。
各 (グラフ) の部分に critical edge はないとしているので、この部分にめいっぱい辺をつめこんで完全グラフにしてしまう。とすると

-(完全グラフ)-(完全グラフ)-(完全グラフ)-

みたいな形になるけど、これは完全グラフを一つにまとめた方がよりたくさん辺をつめこめることに気付く。
つまり、整数 A > 0, B > 0, A + B = C に対して、
A(A-1)/2 + B(B-1)/2 ≦ C(C-1)/2
となる。
結局、完全グラフに何本か辺が生えたみたいな形が最適になる。

M を int で読み込んで 1WA.

ひどい説明だ...

F. ( あとで解いた )
const int N_MAX=100000;

template<class T>
class Fenwick_tree{
int n;
T a[N_MAX];
public:
void build(int n){
this->n=n;
rep(i,n) a[i]=0;
}

void add(int i,T v){
for(;i<n;i|=i+1) a[i]+=v;
}

T sum(int i,int j)const{
if(i==0){
T s=0;
for(;j>=0;j=(j&(j+1))-1) s+=a[j];
return s;
}
return sum(0,j)-sum(0,i-1);
}
};

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n,k; scanf("%d%d",&n,&k);

// c = 1, 2, ..., n のときの c^3 mod k の値を前計算
static Fenwick_tree<int> F;
F.build(k);
for(int c=1;c<=n;c++) F.add((ll)c*c*c%k,1);

ll ans=0;
for(int b=1;b<=n;b++){ // b の値を固定して、そのときの a を一気に数え上げる
int bb=(ll)b*b%k;

int l=1+bb,r=b+bb;
if(r<k){
ans+=F.sum(l,r);
}
else{
ans+=F.sum(l,k-1);
ans+=F.sum(0,k-1)*(ll)((r-k)/k);
ans+=F.sum(0,r%k);
}

// b <= c なので c = b のときの値を BIT から削除
F.add((ll)b*b*b%k,-1);
}
printf("Case %d: %lld\n",T,ans);
}

return 0;
}

laycurse さんのツイートを参考にして解いた。

b^2, c^3 の挙動は複雑だけど、a の挙動は簡単にわかるのがポイント。
c^3 の値をあらかじめ BIT に詰めておいて、b でループを回す。
a = 1, 2, ..., b の中で c^3 - b^2 と一致する a を BIT で一気に足し上げる。
計算量は O((n+k) log k).

G. ( 2012/02/20 )
template<class T>
struct edge{
int v;
T cost;
};

const int V_MAX=50000;

template<class T>
bool isbipartite(int n,const vector< edge<T> > *G,int thre=-1){
static int color[V_MAX];
rep(u,n) color[u]=-1;

rep(u,n) if(color[u]==-1) {
color[u]=0;
queue<int> Q; Q.push(u);
while(!Q.empty()){
int v=Q.front(); Q.pop();

rep(i,G[v].size()){
int w=G[v][i].v;
if(thre!=-1 && G[v][i].cost>=thre) continue;
if(color[w]==color[v]) return false;
if(color[w]==-1){
color[w]=1-color[v];
Q.push(w);
}
}
}
}

return true;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,m; scanf("%d%d",&n,&m);

int cost_min=(1<<31)-1,cost_max=0;
static vector< edge<int> > G[V_MAX];
rep(u,n) G[u].clear();
rep(i,m){
int u,v,cost; scanf("%d%d%d",&u,&v,&cost); u--; v--;
G[u].push_back((edge<int>){v,cost});
G[v].push_back((edge<int>){u,cost});
cost_min=min(cost_min,cost);
cost_max=max(cost_max,cost);
}

if(isbipartite(n,G)){ puts("0"); continue; }

int lo=cost_min,hi=cost_max;
while(lo<hi){
int mi=(1LL+lo+hi)/2;
if(isbipartite(n,G,mi)) lo=mi; else hi=mi-1;
}
if(lo==cost_min) puts("-1");
else printf("%d\n",lo);
}

return 0;
}

[ 2012/02/20 追記 ]

K を固定したとき、警備員の配置が実現可能かどうかは、グラフが二部グラフかどうかと同値。
すぐには気付けなかった。

K について二分探索できる。
なぜなら、二部グラフから辺を取り除いたものは二部グラフだから。

H. ( 2012/02/20 )
ll M;

ll modmul(ll a,ll b,ll m){
ll r=0;
for(;b;b>>=1,a=(a<<1)%m) if(b&1) r=(r+a)%m;
return r;
}

const int N_MAX=2;

template<class T>
void mul(int n,const T A[N_MAX][N_MAX],const T x[N_MAX],T y[N_MAX]){
static T z[N_MAX];
rep(i,n){
z[i]=0;
rep(j,n) z[i]+=A[i][j]*x[j];
z[i]%=M;
}
rep(i,n) y[i]=z[i];
}

template<class T>
void mul(int n,const T A[N_MAX][N_MAX],const T B[N_MAX][N_MAX],T C[N_MAX][N_MAX]){
static T tmp[N_MAX][N_MAX];
rep(i,n) rep(j,n) {
tmp[i][j]=0;
rep(k,n) tmp[i][j]+=modmul(A[i][k],B[k][j],M);
tmp[i][j]%=M;
}
rep(i,n) rep(j,n) C[i][j]=tmp[i][j];
}

template<class T>
void pow(int n,const T A[N_MAX][N_MAX],ll m,T B[N_MAX][N_MAX]){
static T tmp[N_MAX][N_MAX];
rep(i,n) rep(j,n) {
tmp[i][j]=A[i][j];
B[i][j]=(i==j?1:0);
}
for(int t=0;m>0;t++){
if(m&(1LL<<t)){
mul(n,B,tmp,B);
m-=1LL<<t;
}
mul(n,tmp,tmp,tmp);
}
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
ll n;
int b,d; scanf("%lld%d%d%lld",&n,&b,&d,&M);

ll A[2][2]={{b,1},{0,1}};
pow(2,A,n-1,A);

ll v[2]={1,1};
mul(2,A,v,v);

printf("Case %d: %lld\n",T,d*v[0]%M);
}

return 0;
}

[ 2012/02/20 追記 ]

まず、問題の数は
d・b^0 + d・b^1 + d・b^2 + ... + d・b^(n-1) mod M
= d・(b^0 + b^1 + b^2 + ... + b^(n-1)) mod M

と書ける。
d は最後にかければいいので、b^0 + b^1 + ... + b^(n-1) の部分を考える。

S_k := b^0 + b^1 + ... + b^k
とおけば、
S_0 = 1
S_{k+1} = b・S_k + 1
という漸化式がたつ。
行列で書いて

となる。
これの n-1 乗を mod M で求めればいい。
繰り返し二乗法で log でできる。
かけ算がオーバーフローするので、そこはなんとかする。
スポンサーサイト

コメントの投稿

非公開コメント

Dの証明

この手の法則が成り立つのを証明するのは、「勝ちの状態からは負けの状態に必ず行ける」と「負けの状態からは勝ちの状態にしか行けない」ことを示すのが典型です。実際に先手が必敗⇔a,cが偶数なので(a, b, c)が(奇、*、奇)のときは(a-1, b+1, c-1)で(偶、*、偶)に行けて…、などを確かめてやれば正しいことが分かります。
他の問題例としては、SRM472のPotatoGameなども同じように実験→証明することができます。

Re: Dの証明

おお、なるほど!!
納得しました。アドバイスありがとうございます。
プロフィール

fura2

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

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

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