Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1392-9ee87c35
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #23 (参加記録) (この記事を編集する[管理者用])

2010年07月10日00時から2時間,5問.
[ Link ]

A. You're Given a String...

100文字以下の文字列が与えられる.
オーバーラップしてても良いので,2回以上登場する部分文字列のうち,最も長い部分文字列の長さを求める問題.

100文字以下だから全部探索すれば良いよね.O(長さ^2)だし…じゃなかったO(長さ^3)になるのか.
書いた.サブミット.Accept.

B. Party

n人の人がいて,与えられないけど,友達関係がある.
友達がちょうど0人の人が一斉に消える.
残っている中に,友達がちょうど1人いる人が一斉に消える.
残っている中に,友達がちょうど2人いる人が一斉に消える.

という操作を繰り返した最終的に,残る人数の最大値を求める問題.
与えられるのはn.

うーん….
3の時の答えは1なのか…,どういう場合だ….
 ○-○-○
みたいなときか.
答えは,ceil(n/2)とか?
いや,n-2っぽい?
n-2っぽい気がしてきた.証明できない.
うーん.
わかった.
n-2ノードで完全グラフを作って,2つのノードを追加するとき,degをn-3にして,もともとあったノードのdegをn-2以上にできるので,そういうふうにすれば最終人数n-2を達成できる.
n-1には…まぁ,できないよね.
1人抜けたときに,次数が下がる(生き残れる可能性がある)のは高々,その次数の人までで,次数がn-1なら,全員いっぺんに消えてしまうから.
n=1のときコーナーケースなので,それに気をつけよう.
サクッと書いてサブミット.Accept.

C. Oranges and Apples

2N-1個の箱に,オレンジとリンゴがそれぞれ10^9以下だけ入っている.箱ごとに入ってる数は違う.
そこからN個の箱を選んで,オレンジもリンゴも総数の半分以上が含まれているようにしたい.
そのような選び方を1個求める問題.存在しないならそれを指摘する.

うーん,わからんぞ.
片方を多い順に貧欲に選んだとして,後は,適当に入れ替えて,もう片方の条件をみたすようにできるかどうか….
それは普通のナップザックっぽいDPになるけど,10^9じゃ無理….
うーん.
NOになるケースなんてあるのか?
ない気がする.
少なくても簡単には作れない.
本当に無いのかなぁ….
と色々考えてたけど分からなかった.

D. Tetragon

凸な四角形で3辺の長さが同じものがある.
その3辺の中点が与えられるので,もともとの四角形を復元せよ,という問題.
そのような四角形が存在しないならそれを指摘する.

色々やればできそうな気もするけど,幾何だし,面倒そうだし,放置.

E. Tree

ノード数700以下の木が与えられる.
いくつか枝を取り除いて,連結成分のサイズ(ノード数)の積を最大化する問題.
最大値を求める.

根付き木だと思ってDPを下から組み立てて行けば良さそうだけど….
いけるのか?いけそう.
多倍長が面倒….
書いてみる.
うーん.
いや,何気にちょっと面倒?
自分の親と繋がる場合と繋がらない場合に分けて,DPを記録する….
繋がる場合は,自分の子どもが葉なら繋げておいて,そうじゃないと繋げない.
….
うーん,これ,greedyでもいけるんじゃないの…?
取り敢えず葉は全部繋げて….
後は,残りは….うーん?
ちょっと考えたけど,ダメそうだった.
….
DPに戻ろう.
繋がらない場合は…,子供とつながらないと駄目.
それは,全部確かめるとTLEしそう….多倍長だし.
うーん.
一番小さい集合と繋がればいいのでは.
よさそう.
書いた.
WA.
あれぇ….

Result

全然解けない.
寝ぼけてて無気力気味だったのもあるけど,そうじゃなくても多分解けてない.
なんでRate上がったんだろう….

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1392-9ee87c35
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。