スポンサーサイト

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

Codeforces Beta Round #22 (Div.2)

日本時間で 6/30 0:00~2:00 に行われた Codeforces Beta Round #22 の参加記録です。

今回はDiv.2のみの参加 (Div.1の人は参加できるけどRatingは変わらない) なので、いつもに比べると問題も簡単なはずなのに、どうも最近はふるわないな。

(一部の)問題と解答は [ 続きを読む ] から

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

[ 問題 ]
今回の問題セットはこんな感じでした。

A. Second Order Statistics

与えられる n 個の整数のうち、2 番目に小さいものを求めよ。
ex)
1 2 3 4 が与えられたときは 答え 2
1 1 2 3 が与えられたときは 答え 2 (1ではない)

1 ≦ n ≦ 100

B. Bargaining Table

部屋データ ( n×m の 2 次元配列で、何もないところは 0, 家具があるところは 1 ) が与えられる。
この部屋に入る長方形のテーブルのうち、周長最大のものを求めよ。

1 ≦ n, m ≦ 25

C. System Administrator

n 台のサーバーを m 本のケーブルで接続してネットワークを作りたい。
ただし、v 番目のサーバーに障害が起こったときにネットワークが途切れる ( ある 2 サーバー間をつなぐ経路がない ) ようにしたい。
また、同じ 2 サーバー間に複数本のケーブルをつないではいけないし、ケーブルの両端を同じサーバーにつないではいけない。
上記の条件をみたす接続方法を求めよ。複数ある場合はどれを答えてもいい。
そのような方法がない場合は -1 と答える。

3 ≦ n ≦ 105
0 ≦ m ≦ 105

D. Segments

x 軸上にあり、端点が整数値である線分が n 本与えられる。
x 軸上に何本かの釘を刺して、これらの線分を留めることを考える。
ここで、釘を刺す位置が線分の上 ( 端点でもいい ) であるとき、線分は留まるとする。

すべての線分を留めるのに必要な釘の最小個数と釘の位置を求めよ。
ありうる釘の位置が複数通りあるときはどれを答えてもいい。

1 ≦ n ≦ 1000

E. Scheme

n 人のメンバー間で伝言ゲームをする。

[ ルール ]
i 番目のメンバーは、伝言を受けたとき、fi 番目のメンバーに伝言を流す。
[ 追加ルール ]
i 番目のメンバーは、伝言を受けたとき、j 番目のメンバーにも追加で伝言を流す。

どのメンバーからはじめても全員に伝言が回るためには、最小でいくつの追加ルールがあればいいかを求めよ。

[ 解答 ]
言語は C++。include文とusing文は省略。
追記したコードのテンプレはここを参照。

A.
int main()
{
int n; cin>>n;
vector<int> s(n);
for(int i=0;i<n;i++) cin>>s[i];

sort(s.begin(),s.end());
s.erase(unique(s.begin(),s.end()),s.end());

(s.size()<=1)?(cout<<"NO"):(cout<<s[1]);

return 0;
}

書くだけだけど、STLを使うとこんなに短くなる。
すぐに書きあがった。

B. (時間外)
int main()
{
int n,m; cin>>n>>m;
int room[25][25];
for(int i=0;i<n;i++){
char tmp[26]; cin>>tmp;
for(int j=0;j<m;j++) room[i][j]=tmp[j]-'0';
}

int peri=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(room[i][j]==1) continue;
for(int h=1;h<=n-i;h++){ // height of table
for(int w=1;w<=m-j;w++){ // width of table
bool flag=true;
for(int y=i;y<i+h;y++){
for(int x=j;x<j+w;x++){
if(room[y][x]==1) flag=false;
}
}
if(flag) peri=max(peri,(w+h)<<1);
}
}
}
}

cout<<peri;

return 0;
}

競技中はなぜかこれができず、迷走している間に競技終了。
あとで冷静に考えたら簡単にできた。
DPでできるらしいけど、うまくできなかったのでブルートフォース<そうあたり>
入力値の上限が25なので、6重ループしても間に合う。

C. (時間外)
int id[100000];

int main()
{
int n,m,v; cin>>n>>m>>v;

if(m<n-1 || (n-2)*(n-1)/2+1<m){
cout<<-1<<endl; return 0;
}

id[0]=(v==1)?2:1;
for(int i=0;i<n-1;i++){
id[i+1]=id[i]+1;
if(id[i+1]==v) id[i+1]++;
}
swap(id[0],v);

int cnt=0;
cout<<id[0]<<" "<<v<<endl;
cnt++;

for(int i=0;i<n-2;i++){
cout<<id[i]<<" "<<id[i+1]<<endl;
if(++cnt==m) return 0;
}

for(int i=0;i<n-1;i++){
for(int j=i+2;j<n-1;j++){
cout<<id[i]<<" "<<id[j]<<endl;
if(++cnt==m) return 0;
}
}

return 0;
}

グラフ理論の言葉で言いなおすと、
n 個の頂点、m 本の辺をもつ単純連結グラフで、ここから番号 v の頂点を取り除くと非連結になる (つまり、v がグラフの切断点になっている) ものを求める問題。

nを頂点の数とする。
グラフが連結でなければいけないので、最低でも (n-1)本 の辺が必要。これは、すべての頂点が1直線につながっている場合。
一方で、辺が多すぎると題意を満たすグラフは作れなくなる。
題意を満たす範囲で辺の数が最大のグラフは、完全グラフKn-1に、vから1本の辺が出ている場合。(参考 : 完全グラフ)
n=6の例

これ以上辺を追加すると、vが切断点にならないか、グラフが単純にならなくなる。
他の分け方(KaとKb(a+b=n)が頂点vのみでつながっている)も考えられるが、この分け方のほうがいつでも多くの辺をもつ。(証明してないけど多分正しい)
この分け方をしたとき、題意のグラフが作れるための辺の最大数は (n-2)(n-1)/2 本。(詳細は上記の参考リンク)

ここまで詰めれば、あとは書くだけ。

D. (時間外)
int main(){
int n; scanf("%d",&n);
vector<pii> a(n);
rep(i,n){
int left,right; scanf("%d%d",&left,&right);
if(left>right) swap(left,right);
a[i]=mp(right,left);
}
sort(a.begin(),a.end());

vi nail;
int lastnail=-INF;
rep(i,n){
int left=a[i].second,right=a[i].first;
if(lastnail<left){
nail.pb(right);
lastnail=right;
}
}

printf("%d\n",nail.size());
rep(i,nail.size()) printf("%d%c",nail[i],i<nail.size()-1?' ':'\n');

return 0;
}

[ 2011/03/20 追記 ]

解いた。

線分の右端点を左から順に走査していく。
まだ留まっていない線分が現れたら、その右端点に釘を打つ。

という Greedy Algorithm で正しい答えが得られる。
O(n).

証明は、区間スケジューリング問題と似た感じでできる。
( 区間スケジューリング問題が Greedy Algorithm で解けることの証明は、たとえば 『アルゴリズムデザイン』 にある。)
つまり、このアルゴリズムで得られた解が、ある意味で最適解より悪くないことを示せばいい。

証明 ( もどき )
最適解 ( 釘たちの位置 ) を 1 つ固定する。
最適解の一番左にある釘 N0 を考える。
N0 は右端点が一番左にある線分 S0 を留めているはず。
でないと、S0 を留める釘がないことになってしまう。
一方、Greedy Algorithm では S0 の右端点に釘 N0' を打つ。アルゴリズムの動作から、N0' は N0 より右 (or 同じ位置) にあるはず。
S0 の右端点より左に線分の右端点はないから、多くの線分を留めるには N0' の方が特。つまり、
{ N0 が留める線分 } ⊂ { N0' が留める線分 }
が成立する。
再帰的に考えれば、つねに Greedy Algorithm で得られた解の方がいい解 (or 同じ) であることがわかる。
( 証明終 )

2011/10/09 : 証明を微修正

E.
完成次第追記します。



結局、本番では A しか解けず。
ratingは14301351
まぁ、この結果だと下がるよね。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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