スポンサーサイト

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

ZOJ Monthly, August 2011

2011/08/28 13:00~18:00 ZOJ Monthly, August 2011 の参加記録。

ZOJ のコンテストは初参加。

The 2nd Touhou Only Monthly! ZOJ in Gensokyo!
とのことだったので、軽い気持ちでやってみた。
後半 3 時間の参加で、9 問中 2 問解けた。

かなり難しい問題セットだったらしい。

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

結果

Aya. 3WA, AC (03:19)
Cirno. -
Flandre. -
Mukyu. WA, AC (04:20)
Nitori. -
Remilia. -
Suika. -
Suwako. -
Yuuka. -
Standing : 209/550 人くらい


問題

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

Aya. Hello, Gensokyo
幻想郷には n 人の人がいます。
ある人とある人の間には関係があります。
三角関係はありません。
最大でいくつの関係がありうるでしょうか?

1 ≦ n ≦ 100000

Mukyu. Bookcase
棚に m 冊の本が並べられています。
これらの本をタイトルの辞書式順序で並べ替えたいと思います。

「 棚から 1 冊の本を抜き出し、それを棚の好きな位置に挿入する。 」

という操作を繰り返して本を整列させるとき、最小で何回の操作が必要になるでしょうか?

1 ≦ m ≦ 50

Suika. Weekend Party
n 人の人がいます。
それぞれの人は、アニメ,マンガ,ゲームの中から 1 つ以上の趣味を持っています。

今、n 人を円形に座らせようと思います。
すべての人が
・ 左隣の人と共通の趣味をもち、かつ
・ 右隣の人と共通の趣味をもつ
ような座らせ方が存在するかどうかを判定してください。

1 ≦ n ≦ 64

Yuuka. Parterre
n × m の花畑があります。
各マスにはちょうど 1 輪の花が咲いています。

長方形のループ上には同じ種類の花が咲いています。
ループの中心は花畑の中心と同じです。

たとえば、5 × 7 の花畑だと
1111111
1222221
1233321
1222221
1111111

といった感じです。 ( 同じ種類の花を同じ番号で書いた。 )

q 個の長方形領域が与えられるので、それぞれについて
・ その領域に含まれる花の種類数
・ その領域に含まれる花の中でもっとも本数が多い花の品種とその本数
を求めてください。

1 ≦ n, m ≦ 500
1 ≦ q ≦ 10000
1 ≦ 花の種類数 ≦ 250

解答

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

Aya.
int main(){
for(long long n;~scanf("%lld",&n);) printf("%lld\n",n*n/4);
return 0;
}

n 頂点の無向グラフで三角形ができないように辺を張るとき、最大でいくつの辺が張れるか?
という問題。

n が偶数のときは、図のようにすればいい。
Aya graph

n が奇数のときは、うまく作れなかったけど、n = 3, 5, 7 のときに試行錯誤して作った解をもとに OEIS で検索してみると、見事にヒットした。 ( これ )
公式を埋め込んで提出。 Accepted.

ちなみに、テストケースの数がべらぼうに多いのか、O(1) 解法なのに cin, cout を使うと TLE になった。

Mukyu.
int LIS(int n,const int *a){
int lis[50];
rep(i,n) lis[i]=INF;
rep(i,n) *upper_bound(lis,lis+n,a[i])=a[i];
return find(lis,lis+n,INF)-lis;
}

int main(){
for(int m,n;~scanf("%d%d",&m,&n);){
getchar();

int ans=0;
rep(_,m){
char book[50][64];
string book2[50];
rep(i,n){
gets(book[i]);
book2[i]=book[i];
}
sort(book2,book2+n);

int a[50];
rep(i,n){
int j;
for(j=0;j<n;j++) if(strcmp(book[i],book2[j].c_str())==0) break;
a[i]=j;
}
ans+=n-LIS(n,a);
}
printf("%d\n",ans);
}

return 0;
}

しばらく考えて、LIS を求めるだけかも...という発想にいたった。
確証はまったくなかったが、なんとなくそれでいけそうだったので書いてみたら通った。

LIS に属する本はすでに正しい位置にあるとして、それに属さなかった本のみを手動でスワップする。

LIS は自前のライブラリにあった O(n log n) のバージョンを使ったけど、O(n2) でも余裕で間に合うはず。

Suika. (時間外)
int m,fav[12];

bool dfs(int u,int S){
if(S==(1<<m)-1) return fav[u]&fav[0];

rep(v,m) if((S&(1<<v))==0 && (fav[u]&fav[v])) {
S|=1<<v;
if(dfs(v,S)) return true;
S-=1<<v;
}
return false;
}

int main(){
int f[128]; f['A']=0; f['C']=1; f['G']=2;

for(int n;~scanf("%d",&n);){
m=0;
int freq[8]={};
rep(i,n){
char s[4]; scanf("%*s%s",s);

int tmp=0;
rep(j,strlen(s)) tmp|=1<<f[s[j]];

if(tmp==1 || tmp==2 || tmp==4){
if(freq[tmp]<1) freq[tmp]++, fav[m++]=tmp;
}
else if(tmp==3 || tmp==5 || tmp==6){
if(freq[tmp]<2) freq[tmp]++, fav[m++]=tmp;
}
else{
if(freq[tmp]<3) freq[tmp]++, fav[m++]=tmp;
}
}

puts(dfs(0,1)?"Yes":"No");
}

return 0;
}

[ 2011/09/03 追記 ]

人を頂点、隣に座ることができるという関係を辺と思うと、ハミルトン閉路問題になる。
頂点数 64 のハミルトン閉路問題はそう簡単には解けないので、何とかして頂点数を減らすことを考える。

まず、単独の趣味 (A, C, G) をもつ人は 1 つに縮約してもいい。

そこから先がわからなかったけど、iakasT さんのブログ記事カンニングヒントにすると次のことがわかる。
・ AC が 3 人以上いるときに解がある ⇔ AC が 2 人いるときに解がある
・ AG が 3 人以上いるときに解がある ⇔ AG が 2 人いるときに解がある
・ CG が 3 人以上いるときに解がある ⇔ CG が 2 人いるときに解がある
・ ACG が 4 人以上いるときに解がある ⇔ ACG が 3 人いるときに解がある

(右) ⇒ (左) は自明。
(左) ⇒ (右) の証明は思いつかないけど、いろいろ試しても反例が見つからないのでどうやら正しいらしい。
ちなみに、ACG が 3 人必要なケースは A, C, G, ACG, ACG, ACG など。

以上から、高々 12 人のみを考えればいい。

全探索すると 11! ≒ 4 × 107 で少しあやしいようにも思えるけど、実際はすぐに解が見つかるか枝刈りが利きまくるかするので、余裕で終わる。

ちなみに、ハミルトン閉路問題は O(2n n2) 時間の DP で解けるので、現実的には n ≦ 18 くらいなら大丈夫。

Yuuka. (時間外)
struct Rect{ int t,l,b,r; };

struct Flower:Rect{ int c; };

inline int intersect(const Rect &a,const Rect &b){
return max(min(a.b,b.b)-max(a.t,b.t)+1,0)
*max(min(a.r,b.r)-max(a.l,b.l)+1,0);
}

int main(){
for(int m,n;~scanf("%d%d",&m,&n);){
Flower F[250];
int k=(min(m,n)+1)/2;
rep(i,k){
scanf("%d",&F[i].c); F[i].c--;
F[i].t=F[i].l=i;
F[i].b=m-i-1;
F[i].r=n-i-1;
}

int nq; scanf("%d",&nq);
while(nq--){
int t,l,b,r; scanf("%d%d%d%d",&t,&l,&b,&r);
Rect rc={t,l,b,r};

int freq[250]={};
rep(i,k){
freq[F[i].c]+=intersect(rc,F[i]);
if(F[i].r-F[i].l>=2 && F[i].b-F[i].t>=2){
freq[F[i].c]-=intersect(rc,(Rect){F[i].t+1,F[i].l+1,F[i].b-1,F[i].r-1});
}
}

int i_max=max_element(freq,freq+250)-freq;
printf("%d %d %d\n",250-count(freq,freq+250,0),i_max+1,freq[i_max]);
}
}

return 0;
}

[ 2011/09/02 追記 ]

問題文の読解が難しい。(Twitter で教えてもらった)
読めたら実装するだけだった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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