スポンサーサイト

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

The 2011 ACM-ICPC Asia Dalian Regional Contest

2011/10/02 13:00~18:00 (JST)
ZOJ で行われた The 2011 ACM-ICPC Asia Dalian Regional Contest の参加記録。

難問ぞろいだった。

Tags : プログラミング ZOJ ICPC 未解決

結果

A. -
B. -
C. -
D. WA, AC (01:01)
E. 2TLE
F. -
G. -
H. -
I. AC (01:46)
J. -
Standing : 80/400 人くらい


問題

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

D. Hexadecimal View

与えられる文字列を 16 進ダンプして出力せよ。
ただし、文字列中のアルファベットは大文字と小文字を反転して出力すること。
出力フォーマットはサンプル参照。

E. Number String

'I', 'D', '?' からなる長さ n (≦ 1000) の文字列 s が与えられる。
{1, 2, ..., n+1} の順列 p1, ..., pn+1 で、
・ s[i] = 'I' なら pi < pi+1 (i = 1, 2, ..., n)
・ s[i] = 'D' なら pi > pi+1 (i = 1, 2, ..., n)
であるものの個数を mod 1000000007 で答えよ。

F. Draw a Mess

m × n のキャンバスに図形を描く。
扱う図形は円、ダイヤモンド、長方形、三角形の 4 種類。縁だけではなく、中身が詰まっている。
使える色は 1, 2, ..., 9 の 9 種類あり、各図形は単色で描かれる。
すでにある図形に重ねて新しい図形を描く場合、重なる部分は新しい図形に上書きされる。

q 個の図形をすべて描き終わったときのキャンバス上の色の分布を求めよ。

1 ≦ m, q ≦ 50000
1 ≦ n ≦ 200

I. The Boss on Mars

n 以下で n と互いに素な正整数の 4 乗和を mod 1000000007 で求めよ。

1 ≦ テストケース数 ≦ 1000
1 ≦ n ≦ 108

解答

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

D.
int main(){
for(char s[4100];gets(s);){
int n=strlen(s);
for(int i=0;i<n;i+=16){
printf("%04x: ",i);

int j;
for(j=0;j<16;j++){
if(i+j>=n) break;
printf("%02x%s",s[i+j],j%2?" ":"");
}

for(;j<16;j++) printf(" %s",j%2?" ":"");

for(j=0;j<16;j++){
if(i+j>=n) break;
char c;
if (isupper(s[i+j])) c=tolower(s[i+j]);
else if(islower(s[i+j])) c=toupper(s[i+j]);
else c=s[i+j];
putchar(c);
}
putchar('\n');
}
}

return 0;
}

指示どおりに実装すればいい。
問題文をよく読まずにアドレス部を 10 進数で出力していたため 1WA.

E. (時間外, TLE)
const ll M=1000000007;

int main(){
for(char s[1001];gets(s);){
int n=strlen(s);
static ll dp[1001][1001];
dp[0][0]=1;
rep(i,n) rep(j,n+1) {
dp[i+1][j]=0;
if(s[i]=='I' || s[i]=='?') for(int k=0;k< j;k++) dp[i+1][j]+=dp[i][k];
if(s[i]=='D' || s[i]=='?') for(int k=i;k>=j;k--) dp[i+1][j]+=dp[i][k];
dp[i+1][j]%=M;
}

printf("%lld\n",accumulate(dp[n],dp[n]+n+1,0LL)%M);
}

return 0;
}


E. (時間外, AC)
const int M=1000000007;

int main(){
for(char s[1001];gets(s);){
int n=strlen(s);
static int dp[1001][1001];
dp[0][0]=1;
rep(i,n){
static int sum[1001];
sum[0]=0;
rep(j,i+1) sum[j+1]=(sum[j]+dp[i][j])%M;

rep(j,n+1){
dp[i+1][j]=0;
if(s[i]=='I' || s[i]=='?') dp[i+1][j]+=sum[j];
if(s[i]=='D' || s[i]=='?') dp[i+1][j]+=sum[i+1]-sum[j]+M;
dp[i+1][j]%=M;
}
}

printf("%lld\n",accumulate(dp[n],dp[n]+n+1,0LL)%M);
}

return 0;
}

コンテスト中は、複雑な O(n3) のメモ化再帰で解くことを考えていた。
結局、オーダーを落とすことができずに TLE だった。

watashi さんのブログ を参考にして解いた。

方針は DP.
dp[i][j] := {1, 2, ..., i} からなる順列について、その末尾の数が j であるときの解の総数
とする。

・ s[i] = 'I' のとき
{1, 2, j-1, j+1, ..., i+1} からなる順列 P がすでにできていて、P の末尾に j を追加すると考える。
j を追加できるのは P の末尾が j より小さいときのみなので、
dp[i+1][j] = Σk=1 to j-1 dp[i][k]
となる。

・ s[i] = 'D' のとき
同様に考えれば、
j を追加できるのは P の末尾が j より大きいときのみなので、
dp[i+1][j] = Σk=j to i dp[i][k]
となる。
P はサイズ i の順列であることに注意。

・ s[i] = '?' のとき
P の末尾がなんであろうと j を追加できるので、
dp[i+1][j] = Σk=1 to i dp[i][k]
となる。

※ 0-indexed の関係で、上に書いた式は添え字が ± 1 くらいずれてるかも。

これを素直に実装したのが上のコード。 (TLE と書いたほう)
このままだと O(n3) かかって間に合わないけど、累積和を前計算しておくことで O(n2) に落ちる。

watashi さんは 「非常简单的动态规划」 と言っているけど、自分にとってはぜんぜん簡単じゃない。
DP 配列の定義もちょっと技巧的だし。

F. (時間外)
const double EPS=1e-9;

int m,n,ans[10];

class Line{
int next[50000],cnt;

int gao(int y,int b){
if(y>b) return y;
if(~next[y]){
return next[y]=gao(next[y],b);
}
else{
cnt++;
return next[y]=gao(y+1,b);
}
}

public:
void init(){ rep(y,m) next[y]=-1; }

void draw(int t,int b,int c){
cnt=0;
gao(t,b);
ans[c]+=cnt;
}
};
Line L[200];

void drawCircle(int xc,int yc,int r,int c){
rep(x,n) if(abs(x-xc)<=r) {
double d=sqrt(r*r-(x-xc)*(x-xc));
int t=max((int)(yc-d-EPS+1),0);
int b=min((int)(yc+d+EPS),m-1);

L[x].draw(t,b,c);
}
}

void drawDiamond(int xc,int yc,int r,int c){
rep(x,n) if(abs(x-xc)<=r) {
int t=max(yc-(r-abs(x-xc)),0);
int b=min(yc+(r-abs(x-xc)),m-1);

L[x].draw(t,b,c);
}
}

void drawRectangle(int xc,int yc,int l,int w,int c){
int t=yc,b=min(yc+w-1,m-1);
rep(x,n) if(xc<=x && x<=xc+l-1) {
L[x].draw(t,b,c);
}
}

void drawTriangle(int xc,int yc,int w,int c){
rep(x,n) if(xc<=x && x<=xc+w/2) {
int t=max(yc-(w/2-(x-xc)),0);
int b=min(yc+(w/2-(x-xc)),m-1);

L[x].draw(t,b,c);
}
}

int main(){
for(int nq;~scanf("%d%d%d",&n,&m,&nq);){
rep(j,n) L[j].init();
rep(c,9) ans[c+1]=0;

static char qc[50000];
static int q[50000][5];
rep(i,nq){
scanf(" %c%*s",qc+i);
rep(j,qc[i]=='R'?5:4) scanf("%d",q[i]+j);
}
for(int i=nq-1;i>=0;i--){
switch(qc[i]){
case 'C':
drawCircle(q[i][0],q[i][1],q[i][2],q[i][3]);
break;
case 'D':
drawDiamond(q[i][0],q[i][1],q[i][2],q[i][3]);
break;
case 'R':
drawRectangle(q[i][0],q[i][1],q[i][2],q[i][3],q[i][4]);
break;
case 'T':
drawTriangle(q[i][0],q[i][1],q[i][2],q[i][3]);
break;
}
}

rep(c,9) printf("%d%c",ans[c+1],c<8?' ':'\n');
}

return 0;
}

[ 2011/10/09 追記 ]

moorage さんのコード を参考にして解いた。

行数に比べて列数が少ないことに注目する。

クエリを前から順番に処理すると図形の上書きが起こってしまい難しくなるので、後ろから処理していく。
すでに描かれている図形には色がのらないイメージ。

1 つの図形を描くということは、キャンバスの各列に対して、(行方向の) 区間として指定される領域に色を塗るということ。
( もちろん、この区間はすでに描かれている図形によっていくつかに分断されるかもしれない。)

これを素直に実装すると、1 クエリあたり O(mn) かかってしまい、間に合わない。
そこで、キャンバスの行方向の各ラインに対して Union-Find の経路圧縮のようなことをやる。
すでに塗られている区間は飛ばして、次に来るまだ塗られていない位置を指すようにポインタを張る。
( 文章での説明が難しい… )
こうすることで、クエリ全体を通してキャンバスを走査する回数は O(mn) で抑えられる。

全体の計算量は O(nq + mn) となる。


経路圧縮をしなくても、各列について Segment Tree をもてば同じことができるけど、m n = 107 とぎりぎりのサイズなので、log がついてしまうと TLE になると思う。


あと注意すべき点としては、問題中の Hint の図が間違っていること。
三角形は、底辺が y 軸に平行で x 軸の正方向にとがっているものを考えないといけない。

I.
const ll M=1000000007;

int PrimeFactorization(int a,int *res){
int n=0;
for(ll p=2;p*p<=a;p++) if(a%p==0) {
do{ a/=p; }while(a%p==0);
res[n++]=p;
}
if(a>1) res[n++]=a;
return n;
}

inline ll pow4(ll a){
ll b=(a*a)%M;
return (b*b)%M;
}

inline ll sum4(ll a){
const static ll INV30=233333335;
ll res=a;
res=(res*(a+1))%M;
res=(res*(2*a+1))%M;
res=(res*((3*a*a+3*a-1+M)%M))%M;
res=(res*INV30)%M;
return res;
}

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

int np,p[10];
np=PrimeFactorization(a,p);

ll ans=0;
rep(S,1<<np){
int pop=0,mul=1;
rep(i,np) if(S&(1<<i)) pop++, mul*=p[i];
if(pop&1) ans=(ans-pow4(mul)*sum4(a/mul))%M;
else ans=(ans+pow4(mul)*sum4(a/mul))%M;
}
if(ans<0) ans+=M;

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

return 0;
}

n の素因数をすべて求めて、包除原理で計算する。

自然数のべき和については有名な公式があって、
14 + 24 + ... + m4 = m・(m+1)・(2m+1)・(3m^2+3m-1) / 30
と書けるので、これは O(1) で計算できる。
同じように、
p4 + (2p)4 + ... + (mp)4 = p4・m・(m+1)・(2m+1)・(3m^2+3m-1) / 30
と計算できる。

n の素因数の種類数 (個数ではない) は 8 個以下 (∵ 2・3・5・7・11・13・17・19・23 > 108) なので、これで間に合う。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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