スポンサーサイト

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

Codeforces Beta Round #53

1/26 1:00~3:00. Codeforces Beta Round #53 の記録。

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

結果

A. WA,AC(416)
B. AC(852)
C. AC(966)
D. -
E. -
Hacks : -
Standing : 108/926
Rating : 16541776


問題

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

A. Square Earth?
長さ n の正方形と正方形の辺上にある 2 点が与えられる。
正方形の辺に沿って長さを測るとき、2 点間の最短距離を求めよ。

B. Martian Architecture
n 枚のタイルが一列に並んでいる。
m 個の階段情報が与えられる。
それぞれの階段情報は a b c という形をしていて、
位置 a のタイルから位置 b のタイルまでに、オフセット c で階段状に石板を積み上げることを表している。
すなわち、位置 a のタイルには c 枚の石板を積み、位置 a+1 のタイルには c+1 枚の石板を積み、...、位置 b のタイルには c+b-a 枚の石板を積む。

「ある位置には何枚の石板が積まれているか」というクエリが k 個与えられる。
すべてのクエリを処理せよ。
( n≦105, m≦105, k≦100 )

C. Array
ai ∈ { 1, 2, ..., n } で定義される長さ n の数列 {an} のうち、広義単調なものはいくつあるか?
( 広義単調 = 広義単調増加 または 広義単調減少 の意味 )

D.

E.


解答

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

A.
int main(){
int n,x[2],y[2],s[2]; scanf("%d%d%d%d%d",&n,&x[0],&y[0],&x[1],&y[1]);
rep(i,2){
if (y[i]==0) s[i]=x[i];
else if(x[i]==n) s[i]=n+y[i];
else if(y[i]==n) s[i]=n+n+(n-x[i]);
else s[i]=n+n+n+(n-y[i]);
}
if(s[0]>s[1]) swap(s[0],s[1]);
printf("%d\n",min(s[1]-s[0],s[0]-(s[1]-4*n)));

return 0;
}

ちょっと考えてから書き始めないと、大変な場合分けをすることになる。
上のコードでは、正方形の辺上を一周する座標を導入して、右回りと左回りの小さいほうを出力するようにした。

B.
int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
int a[100000],b[100000],c[100000];
rep(i,m) scanf("%d%d%d",a+i,b+i,c+i);

ll ans=0;
rep(i,k){
ll cnt=0;
int p; scanf("%d",&p);
rep(j,m) if(a[j]<=p && p<=b[j]) cnt+=p-a[j]+c[j];
ans+=cnt;
}
printf("%I64d\n",ans);

return 0;
}

各階段情報ごとに、b-a 個のマスをチェックしていては間に合わない。
前処理をせずに、各クエリごとに O(m) の手間をかける解法だと、O(mk) で間に合う。
もっと早い方法もあるけど、今回の場合はこれで十分。

C.
const ll M=1000000007;

ll inv(ll a){
ll m=M-2;
// calc a^m (mod M)
ll ans=1;
for(ll t=a;m;t=(t*t)%M,m>>=1) if(m&1) ans=(ans*t)%M;
return ans;
}

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

ll a[100001]; a[1]=1;
ll c[100001]; c[1]=1;
for(int i=1;i<n;i++){
ll coef=(2*(2*i+1)*inv(i+2))%M;
c[i+1]=(coef*c[i])%M;
a[i+1]=(4*a[i]-c[i]+M)%M;
}
printf("%d\n",(2*a[n]-n+M)%M);

return 0;
}

嘘解法で通してしまった。
まず、問題は単調増加数列の個数 (an とする) を数えれば十分だということはすぐにわかった。
というのも、「単調増加数列の個数」=「単調増加数列の個数」で、単調増加数列かつ単調減少数列であるのは定数列だけ。定数列は n 通りしかないから、答えは 2 an - n になる。

n が小さいときについて全通り生成してみると、
a1=1, a2=3, a3=10, a4=35, a5=126, a6=462, ...
という値が得られた。
これをじっと見ていると、an を大体 4 倍すると an+1 に近くなることに気付いた。
試しに 4 倍して、次の項との差をとってみると、
1, 2, 5, 14, 42, 132, ...
という値がでてきた。
これは Catalan 数!!

というわけで、漸化式
an+1 = 4 an - Cn
を使った解答が上のコード。
証明はしてないけど、通ったから正しいはず。

D.



E.


スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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