Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年05月30日00時から2時間15分,5問.
[ Link ]
全体的にサーバの調子が悪く繋がりにくかった.(ので2時間の予定が15分延びた)

A. Cottage Village

1次元の世界で,中心x[i],幅w[i]に家が建っている.家の数は1000個以下.
自分は幅wの家を建てたいのだけど,少なくても1個の家に接するように建てたい.
オーバーラップしてはいけない.
家の建て方は何通りあるか調べる問題.

各家の占める場所はx[i]-w[i]/2からx[i]+w[i]/2まで.
小数やだ,2倍する!
後は,両端の2通りと,家の間がwより大きければどちらに寄せるか2通り,ちょうどwだったらすっぽり入れる1通り足していく.
ログインしようとしたらサーバにつながらない.
つながれーつながれー.
繋がった.サブミット.
繋がらなくなった….
繋がれー繋がれー.
問題はBとCは開けたけど,DとEは読み込み中で止まってる.
まぁ,次の問題見よう.

B. Laser

n*mのチョコレート板の2点(x1, y1), (x2, y2)にレーザーが当てられている.
2つのレーザーは最初チョコレート板があった範囲の外にでないように,両方共,同じように移動できる.
レーザーでチョコレート板を溶かしきったとき,残ってるチョコレート板の面積を求める問題.

問題文わっかりにっくいなぁ….
うーん,ああ,そういうことか.
最初の2点のx座標の差とy座標の差のみ重要…なんだよね?
左上端と右下端に(x座標の差)*(y座標の差)だけ残る.
書く.書いた.long longにしないとダメなあたりに気をつけよう.
サブミットできんので,一旦Cに行く.

C. Industrial Nim

nを10000以下として,10^16以下の整数x1, t1, ..., xn, tnが与えられる.
石の山が
 x1, x1+1, x1+2, ..., x1+t1-1
 x2, x2+1, x2+2, ..., x2+t2-1
 …
 xn, xn+1, xn+2, ..., xn+tn-1
のNimが先手必勝か後手必勝かを判定する問題.

要するに,1~nまでのXORを高速に求めてくださいという問題.
それはbitごとにみると,周期性があるのでそれを利用すればOK!
ってことで書く.
書いたところで,サーバーが一瞬復活.AはAcceptだった.
BとCを送る.
サーバー落ちた.
結果見れないけどStandingのみ見れた.
Cは通ってる.Bは-1とか書いてる.あ,間違えてる気がする.

B. Laser (再)

残った破片が普通に繋がっていることもある….
切り取られるのは,左下隅,左上隅,で両方に切り取られている部分は包除原理により足してあげよう.
これでいいんじゃ?
サブミット…できない.
できた.Accept.

E. Triangles

図のような三角形のうち,上の頂点から始まって元に戻ってくるパスの数をmod 1000000007で求める問題.
ただし,パスは自分と接してはいけないし,パスで囲まれる部分にグレーの部分を含んでいてはいけない.

グレーを含んでいてはいけないという文を読み飛ばした.
とりあえず,無理ゲー.
規則を探す?
普通にDFSして小さいとき求めてみた.
あれ,74ってn=3の時の答えだぞ….
数列検索してもよく分からない,Dに行こう.

D. Map

1000*1000の場所の高さが与えられる.
a*bのビルを建てたい.
建てるときは建てる場所のうち,標高が最も低い場所にあわせて,余分な部分を削る.
次のような操作を繰り返す.
 建てれる場所が残っているなら,最小削りで建てれる場所のうち,最も左上に建てる
結果をシミュレーションする問題.

とりあえず,a*bの部分の和と,a*bの部分の最小値を全部計算しないといけない.
えーっと,和はO(1000^2)でできるけど….最小値は…できる…の?
最悪でもO(500^3)なのでちょっと愚直に書いてみようか.
ローカルで1秒ちょっと,間に合う…か,間に合わない…か,微妙な感じ.
とりあえず,暫定的にこれで行く.
あとはどうする?
GCJ 2010 Round 1CのC問題に似てる.
ヒープ作って…,なんてしたらオーバーフローする….
いや,ヒープいらん.
各マス更新すると作れなくなるだけなので,最初にソートして,立地条件のいい場所から建てていく.
前建てたのと重なって建てればいフラグが建っているなら飛ばすだけでいい.
書いた.
送信.WA.
あれ….
ソート間違えてる….ていうかwhileと書くべきをifと書いてる.なんていう初歩的ミス.
送信.WA.
あれ….
ソートまだ間違えてる.余分な+1がある.
送信.もっと早い段階でWA.
%lldにしてた….
送信.Accept.

E. Triangles

あー,グレーは囲んではいけないことを理解.
なんか,普通にDPっぽく計算出来そうな気がする.
間違えて,ページ再読込したら,繋がらなくなった.
ちょっと,図が見えない!
つながれー,つながれー,つながれー,つながれー.
なかなか繋がらない….
でも,時間的にこれ解くの苦しいかなぁ….
諦めよう,うん.

Result

レート更新されるのかされないのか分からないけど,悪くない順位.サーバ不調で諦めた人が多いのかも.
UVaとかで鯖落ち耐性はある程度あるのが良かった…のか?
コンテスト開いてくださってる側も頑張ってるのだと思うし,こういう時は,イライラせずに,結果はどうあれ問題を楽しみましょう,というの感じで.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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