スポンサーサイト

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

World Finals Warmup I

2012/02/25 23:00~ 02/26 23:00 (JST)
World Finals Warmup I の参加記録

11 問。
5 時間でいったん区切られて、その時刻までのランキングが出る。
コンテスト自体は 24 時間あって、最終的なランキングは別に出る。

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

結果

A. -
B. -
C. AC (01:08)
D. -
E. 3WA, AC (08:51)
F. AC (08:13)
G. AC (00:39)
H. -
I. -
J. WA, AC (02:09)
K. 2WA, AC (04:35)
Standing : 15/223

まったりやったけどかなりいい順位が取れた。

問題

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

C. Consistent Verdicts (UVa 12435)

N 人の人が二次元平面上の格子点にいる。
それぞれの人は銃をもっていて、一発ずつ撃つことができる。
どの人も同じ聴力をもっていて、距離 R 以下で撃たれた銃声のみ聞くことができる。

すべての人がちょうど一回ずつ銃を撃ったとする。
各人が何発の銃声を聞いたかを報告する。
R の値が不明であるとして、報告される数の組としてありうるものは何通りあるか?

テストケース数 ≦ 550
テストケースのうちちょうど 10 個は N = 1000
テストケースのうちちょうど 15 個は 100 ≦ N < 1000
そのほかのテストケースは N < 100
0 ≦ 座標値 ≦ 30000

E. Kisu Pari Na 2 (UVa 12437)

頂点数 N, 辺数 M の ( 無向 ) 森が与えられる。
q 個のクエリに答えよ。

[ クエリ ]
整数 K に対して
「少なくとも K 種類の頂点を訪れるまでの辺を移動する回数の最小値」
を求めよ。
スタート位置は自由に決めていい。

1 ≦ N ≦ 10000
0 ≦ M ≦ N-1
1 ≦ q ≦ 10000
1 ≦ K ≦ 10000

F. Farey Polygon (UVa 12438)

n 次の Farey 数列の初項に便宜的に 0/0 を加えたものを Fn とおく。
たとえば
F1 = { 0/0, 0/1, 1/1 }
F2 = { 0/0, 0/1, 1/2, 1/1 }

F4 = { 0/0, 0/1, 1/4, 1/3, 1/2, 2/3, 1/1 }

など。

Fn の各有理数の分母を x 座標, 分子を y 座標とみなしてできる点を二次元平面上にプロットし、順に線分で結んだ閉図形を n 次の Farey polygon と呼ぶ。

n 次の Farey polygon のすべての点の座標値を m 倍したものを、大きさ m の Farey polygon と呼ぶ。

ある n 次, 大きさ m の Farey polygon の内部 ( 境界は含まない ) に含まれる点の個数 I が与えられる。
ありうる n, m の値を求めよ。
複数ある場合は n が最小のもの、それでも複数ある場合はその中で m が最小のもの。

1 ≦ n ≦ 15000 かつ 1 ≦ m ≦ 15000 の中に解が存在しない場合は IMPOSSIBLE と答えよ。

テストケース数 ≦ 12000
0 ≦ I ≦ 10^16

G. February 29 (UVa 12439)

二つの日付が与えられるので、それらの間にうるう年が何回あったかを求めよ。

J. Forwarding Emails (UVa 12442)

N 人からなるネットワークがある。
各人は、誰かからメールを受け取ると、あらかじめ決められた一人にそのメールを転送する。
あなたは誰か一人にメールを送ることで、最終的にメールが送られる人数を最大化したい。
誰にメールを送るべきか?
候補が複数ある場合は、番号が最小の人に送ることとする。

2 ≦ N ≦ 50000

K. Quad (UVa 12443)

整数の pair (a, b) を考えよう。
pair には、和、積、絶対値が次のように定義されている。

(a1, b1) + (a2, b2) = (a1 + a2, b1 + b2)
(a1, b1) * (a2, b2) = (a1*a2 - b1*b2, a1*b2 + a2*b1)
abs((a, b)) = sqrt(a^2 + b^2)

pair (a, b) が prime であるとは、(a, b) が、絶対値が 1 より大きい 2 つの pair の積で表せないこととする。

これをさらに拡張して、quad と呼ばれる pair の pair を定義しよう。
2 つの pair p, q に対して、組 (p, q) を quad と呼ぶ。
quad には、和、積、絶対値が次のように定義されている。

(p1, q1) + (p2, q2) = (p1 + p2, q1 + q2)
(p1, q1) * (p2, q2) = (p1*p2 - q1*q2, p1*q2 + p2*q1)
abs((p, b)) = sqrt(abs(p)^2 + abs(q)^2)

quad (p, q) が prime であるとは、(p, q) が、絶対値が 1 より大きい 2 つの quad の積で表せないこととする。

実数 x が cool であるとは、ある prime quad z が存在して abs(z) = x となることとする。

自然数 n に対して、n 以下の cool number の個数を求めよ。

テストケース数 ≦ 1000
0 < n ≦ 10^4

解答

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

C.
const int N_MAX=1000003;
struct hash_table{
int a[N_MAX];
short id[N_MAX],id_now;

bool insert(int aa){
int i=aa%N_MAX;
while(id[i]==id_now && a[i]!=aa) i=(i+1)%N_MAX;
if(id[i]!=id_now){
a[i]=aa;
id[i]=id_now;
return true;
}
else return false;
}
};

hash_table H;

#define sq(x) (x)*(x)
#define sqsum(x,y) (sq(x)+sq(y))
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d",&n);
int x[1000],y[1000];
rep(i,n) scanf("%d%d",x+i,y+i);

int ans=1;
H.id_now=T;
rep(j,n) rep(i,j) if(H.insert(sqsum(x[i]-x[j],y[i]-y[j]))) ans++;

printf("Case %d: %d\n",T,ans);
}

return 0;
}

R = 0 からはじめて、R をどんどん大きくしていく。
R のとりうる値は実数なのですべてを試すことはできないけど、
興味がある ( 報告される数の組が変化する ) のは、二点間の距離としてありうる R の前後だけ
なので、実際に調べるのは O(n^2) 通りだけでいい。

この距離の値を境目に、報告される数の組は必ず変わる ( それもベクトル値として単調増加する ) ことが、実験すればみえてくる。

なので、重複カウントすることはなく、単に二点間の距離として異なるものはいくつあるかを数えればいいことになる。

テストケース数に対する記述が丁寧で、しかも制限時間が 1 sec なので、かなり時間にシビアな問題であると推測できる。
距離を全列挙したあとソートすると O(n^2 log n) かかって間に合わない可能性が高い。
また、座標値 ( の 2 乗 ) はかなり大きいので、バケットソートの要領でソートするのも難しいように思える。

こういうときはハッシュテーブルを使う。
テーブルの初期化に時間を使うのがいやなので、テーブルが持つ値をちょっとだけ拡張して、初期化は 1 回だけで済むようにした。
ハッシュ関数は単に mod をとるだけという手抜き実装だけど、問題なく一発で通った。
時間計算量は O(n^2)。
現時点で実行時間 1 位!! ( 0.404 sec, 18 人中 )

E.
const int INF=1<<29;

int n;
vector<int> G[10000];

int ans[10001];
bool vis[10000];

int sz; // 木の頂点数
pair<int,int> dfs(int u,int pre){
pair<int,int> res(0,u);
vis[u]=true;
sz++;
rep(i,G[u].size()){
int v=G[u][i];
if(v!=pre){
pair<int,int> tmp=dfs(v,u);
tmp.first++;
res=max(res,tmp);
}
}
return res;
}

void f(int u){
pair<int,int> tmp=dfs(u,-1);
sz=0;
int diam=dfs(tmp.second,-1).first;
int i;
// 最長パス上は辺を一度だけ通ればいい
for(i=1;i<=diam;i++){
ans[i]=min(ans[i],i-1);
}
// 最長パスに乗っていない辺は二度通る
for(;i<=sz;i++){
ans[i]=min(ans[i],diam+2*(i-1-diam));
}
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int m; scanf("%d%d",&n,&m);
rep(u,n) G[u].clear();
rep(i,m){
int u,v; scanf("%d%d",&u,&v); u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}

rep(i,10001) ans[i]=INF;
rep(u,n) vis[u]=false;
rep(u,n) if(!vis[u]) f(u);

printf("Case %d:\n",T);
int q; scanf("%d",&q);
while(q--){
int k; scanf("%d",&k);
if(ans[k]<INF) printf("%d\n",ans[k]);
else puts("impossible");
}
}

return 0;
}

問題文の 7 割くらいを使って、それも図まで用意して Fibonacci 数の説明ががっつり書いてある。
何かあるんじゃないかと思わせるけど、実際の問題とはまったく関係がない。なんだこれは...

さて、方針としては、前処理の段階ですべての K についての答えをあらかじめ求めておくということにする。
グラフの各連結成分 ( これは木 ) ごとに調べて、それらの min を取ればいいことは明らか。

では、木についてどのように調べればいいか。
これも実験していれば気付くけど、木の最長パスが重要で、最長パス上の辺は一度だけ通るようにすればいい。
それ以外の辺は行って戻ってくるのに 2 回通ることになる。

木の最長パスの長さ ( 直径という ) は適当に DFS すれば O(V+E) で求まる。
実装例が Spaghetti Source にあるけど、実はワンパスでできるんじゃないかとひそかに思っている。 ( 未検証 )

ans 配列のサイズが 1 つ足りてなくて、たくさん WA をもらってしまった。

F.
const int N_PHI=15000;
int phi[N_PHI+1];
void build_phi(){
rep(i,N_PHI+1) phi[i]=i;
for(int i=2;i<=N_PHI;i++) if(phi[i]==i) {
for(int j=i;j<=N_PHI;j+=i) phi[j]=phi[j]/i*(i-1);
}
}

int main(){
build_phi();
int len[N_PHI+1]; // len[i] := ( i 次の Farey 数列の長さ )
len[0]=2;
rep(i,N_PHI) len[i+1]=len[i]+phi[i+1];

for(ll I;scanf("%lld",&I),I!=-1;){
if(I==0){ puts("1 1"); continue; }

int n=1,m;
for(m=15000;m>=2;m--) if(2*(I+m*m-1)%(m*(m-1))==0) {
ll a=2*(I+m*m-1)/(m*(m-1));
while(n<=15000 && len[n]<a) n++;

if(n>15000){ m=1; break; }
if(len[n]==a) break;
}

if(m==1) puts("NOT FOUND");
else printf("%d %d\n",n,m);
}

return 0;
}

たくさんのステップを踏まないと解けない超大作。
今年解いた問題の中で今のところ一番好きかもしれない。

まず、多角形の内部にある点の個数と聞いて反射的に思いつくのが Pick の定理。
すなわち
A : 多角形の面積
I : 多角形の内部にある格子点の個数
B : 多角形の辺上の格子点の個数
とすると
A = I + B/2 - 1
が成立する。

I は入力で与えられる。

A はどのような値になるか?
これは、外積を用いた多角形の面積の公式から計算できる。
Farey 数列の性質で、
a/b c/d が隣接しているとき bc - ad = 1 となる
というものがある。
この式は、Farey polygon においては、二つの隣接する頂点を指す位置ベクトルの外積を計算していることになる。
( このことから、Farey polygon が単純多角形であることもわかる )
これらの和の半分が面積になるので、大きさ 1 の Farey polygon の面積は
(L(n)-2)/2
となる。 ( 0/0 を付け加えた分を考慮している )
ここで、L(n) は次数 n の Farey 数列の長さ。
大きさ m の Farey polygon では、面積は 2 乗に比例するので
m^2・(L(n)-2)/2
となる。

B はどのような値になるか?
a/b と c/d が隣接しているとき、対応する線分上の格子点の個数は gcd(|a-c|, |b-d|) + 1 である。 ( 蟻本にも載っている )
実は、|a-c| |b-d| は互いに素になることが、Farey 数列の作り方からいえる。
n 次の Farey 数列で a/b と c/d が隣接していたとすると、n+1 次の Farey 数列では
a/b, (a+c)/(b+d), c/d
という並びが現れる。これは Farey 数列の有名な性質。
Farey 数列の各項は既約なので、|(a+c)-c| と |(b+d)-d| は互いに素となる。
なので、重複して数えた分を引いて、
B = m・L(n)
がわかった。

なお、n 次の Farey 数列の長さ L(n) も簡単に計算できる。
書き出してみればわかるように、Euler φ の和になる。
この部分は RUPC でも出題された。

これらの計算結果と Pick の定理をあわせると L(n) と m についての方程式が立つ。
L(n) について解くと
L(n) = 2・(I+m^2-1)/{m・(m-1)}
となる。
あとは、これをみたすような m と n のペアのうち、n が最小のものを見つければいい。
テストケース数が多いので、m, n の上限まで 15000^2 を調べていては間に合わない。
そこで、関数 2・(I+m^2-1)/{m・(m-1)} が m について単調減少であることを用いる。
尺取法の要領で n を増やしつつ m を減らすように調べれば O(m+n) で済む。
これで時間制限に間に合う。

I == 0 がコーナーケースなので注意。

G.
// [a, b) にある c の倍数の個数
ll f(ll a,ll b,ll c){
if(a%c!=0) a+=c-a%c;
return (b-a+c-1)/c;
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
char month1[16],month2[16];
ll day1,year1,day2,year2;
scanf("%s%lld,%lld",month1,&day1,&year1);
scanf("%s%lld,%lld",month2,&day2,&year2);

if(strcmp(month1,"January")==0 || strcmp(month1,"February")==0);
else year1++;

if(strcmp(month2,"January")==0 || strcmp(month2,"February")==0 && day2<=28);
else year2++;

printf("Case %d: %lld\n",T,f(year1,year2,4)-f(year1,year2,100)+f(year1,year2,400));
}

return 0;
}

日付の値が大きいので一日ずつ見ていくと間に合わない。
まとめて数え上げればいい。

包除原理を使うと数えやすい。

J.
int n,next[50000];
vector<int> rnext[50000];

bool vis[50000];
int n_order,order[50000];
int n_scc,scc[50000];

void dfs1(int u){
vis[u]=true;
int v=next[u];
if(!vis[v]) dfs1(v);
order[n_order++]=u;
}

void dfs2(int u){
vis[u]=true;
rep(i,rnext[u].size()){
int v=rnext[u][i];
if(!vis[v]) dfs2(v);
}
scc[u]=n_scc;
}

void SCC(){
n_order=0;
rep(u,n) vis[u]=false;
rep(u,n) if(!vis[u]) dfs1(u);

n_scc=0;
rep(u,n) vis[u]=false;
for(int i=n-1;i>=0;i--){
int u=order[i];
if(!vis[u]) dfs2(u), n_scc++;
}
}

int dp[50000];
int dfs(int u){
int v=u;
dp[u]=1;
while(1){ // 同じ強連結成分の中を巡る
v=next[v];
if(v==u || scc[u]!=scc[v]) break;
dp[u]++;
}

v=u;
while(1){ // 同じ強連結成分の中の dp 配列を更新する
v=next[v];
if(v==u || scc[u]!=scc[v]) break;
dp[v]=dp[u];
}

if(u!=v) dp[u]+=dfs(v); // 次の強連結成分に移動
return dp[u];
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
scanf("%d",&n);
rep(u,n) rnext[u].clear();
rep(i,n){
int u,v; scanf("%d%d",&u,&v); u--; v--;
next[u]=v;
rnext[v].push_back(u);
}

SCC();

rep(u,n) dp[u]=-1;
for(int i=n-1;i>=0;i--){
int u=order[i];
if(dp[u]==-1) dfs(u);
}

printf("Case %d: %d\n",T,max_element(dp,dp+n)-dp+1);
}

return 0;
}

与えられた有向グラフを強連結成分分解する。
できた DAG に対して、DP で答えを求められる。
dp[u] := 人 u にメールを送ったときにメールが行きわたる人数

グラフの形が特殊なので、最初、なんとか強連結成分分解しないで解こうとしていたけど、思ったより難しかったのでやめた。

K.
const int P_MAX=1000000;
bool er[P_MAX+1];
void sieve(){
rep(i,P_MAX+1) er[i]=(i>=2);
for(int i=2;i*i<=P_MAX;i++) if(er[i]) for(int j=i*i;j<=P_MAX;j+=i) er[j]=false;
}

const int emb[]={78498,152,153,138,158,153,(中略),1094,1087,1105};

int main(){
sieve();
int np[10000]; // np[i] := (number of primes less than i^2)
int sum=0,sq=1;
rep(i,1000000){
if(er[i]) sum++;
if(sq*sq==i) np[sq++]=sum;
}

sum=0;
rep(i,9000) np[i+1000]=(sum+=emb[i]);

int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d",&n);
printf("Case %d: %d\n",T,np[n]);
}

return 0;
}

実験的に答えを予想して解いた。
証明はできていないけど、考えた・調べたところまでメモしておく。

答えは n^2 以下の素数の個数になる。
( 二乗は abs の定義で sqrt をとっていることによる )

まず pair について考える。
かけ算の定義から、複素数が関係しそうだと想像できる。
そこで、pair (a, b) をガウス整数 a+bi に対応させてみると、
pair の足し算、かけ算、絶対値はそれぞれ複素数の足し算、かけ算、絶対値にぴったり対応する。
prime pair はガウス素数に対応する。

次に quad について考える。
quad x = ((a,b), (c,d)) について、
先ほど (a,b) と a+bi を、(c,d) と c+di を同一視したので、同じように新たな単位 j を用いて x と (a+bi)+(c+di)j を同一視してみる。
この代数系はテッサリン (tessarine) などと呼ばれている。
WikipediaWikipedia を参照。
ちなみに、積の定義を少し変えれば ( 片方を共役にすれば ) 四元数ができる。これについては Wikipedia が詳しい。

quad x = ((a,b), (c,d)) を考える。
定義にしたがって計算すれば
abs(x)^2 = a^2 + b^2 + c^2 + d^2
である。

(1) abs(x)^2 が素数になるような prime quad x がつねに存在すること
(2) abs(x)^2 が合成数になるような prime quad x は存在しないこと
を示せばいい。
どちらも証明できていないけど、途中まで書く。

(1)
・ abs(x)^2 = 2 のとき
x = ((1,1), (0,0)) とすれば題意をみたす。

・ abs(x)^2 = 1 (mod 4) のとき
Fermat の二平方和定理より、4n+1 型の素数は二つの平方数の和で書ける。
abs(x)^2 = A^2 + B^2 とおく。
x = ((A,B), (0,0)) とすれば、abs(x)^2 = 1 (mod 4)。
さらに x は prime であることもわかる。
なぜなら、A^2 + B^2 = 1 (mod 4) をみたす A + Bi はガウス素数だから。

・ abs(x)^2 = 3 (mod 4) のとき
二平方和定理より、
abs(x)^2 - 2 = A^2 + B^2 と書ける。
x = ((A,B), (1,1)) とすれば、abs(x)^2 = 3 (mod 4) をみたす。
x が prime かどうかはわからない。

(2)
二平方和定理の Hurwitz quaternion を用いた証明と似たようにすればできるかもしれない。



実装については、篩で必要な範囲の素数をあらかじめ求めておいて、各クエリに対して O(1) で答えるようにする。
速い篩を使えばまともにやっても間に合うと思うけど、僕の篩は特に工夫していないので、必要な値を前計算することにした。
送れるソースコードのサイズに上限があるので、小さいところはまじめに計算する、隣接する値の差分をとって桁数を減らすなどの工夫をした。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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