Entries

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

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

コメント

[C60] rng

二分探索しなくても、左端を x とおくと、その行の数が全部 x で表せて、右端を見ると一次方程式になって解くことができます (係数が 3^1000 くらいで double に入らなくて大変なことになります)。
さらに頑張って手計算すると、フィボナッチの入った変な式が出てきて一応 double におさまるようになりますが、そうすると誤差で落ちます…

[C61] D

最初rngさんと同じことしてましたが増加か減少かさえ見れば二分探索できそうですね, なるほど.

500変数にすると, 逆行列なりLU分解なりをもっておけば500^3になって通せたりします (対称性を終了直後に気づきましたorz)
  • 2010-07-27 09:22
  • lyr
  • URL
  • 編集

[C62] D

Dは行列が三重対角で,n変数でもO(n)で解けるのですねー.
そして,ちょっとでも変なやり方すると,誤差とかオーバーフローとかで大変なことになるのですね….
てか,2分探索は上手くやればいける気もしてきました,本番はなんであんな壊滅的な結果になったのだろう….(でもやっぱり誤差死しそうな気もする)
lyrさんの,逆行列とかをもっておけば~ってのもありですね,なるほど.

(そして,子音だけ見ると,自分のHNとlyrさんのHNが微妙に似てる気がしてきた)
  • 2010-07-27 17:49
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

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

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

A. Ring road

全てのノードの入次数 + 出次数が2で,弱連結な有向グラフが与えられる.
(無向グラフに直したら,1つの大きなサイクルになっているグラフ)
それぞれの枝の向きを変えるコストが与えられたとき,全ノード間を移動できるようにする最小コストを求める問題.

問題の意味を理解するのに少し手間取る.
全てのノードに対して,次数が0になればいいので….
次数2のノードに対して,コストの小さい方をひっくり返せば良い!
サンプル合わない.
ひっくり返したことで,隣のノードが次数2になるかもしれない….
普通にDFSで,1周回って,反転してる枝のコストを数えればいいのでは….
書いた.サンプル合った.サブミット.Accept.

B. F1 Champions

F1のレース結果が与えられる.
1位は25pt,2位は18pt, … というふうにレースごとにスコアが加算される.
優先度が,
 スコア順,1位を取った回数順,2位を取った回数順,…
でソートした時の1位の選手名と
 1位を取った回数順,スコア順,2位を取った回数順,…
でソートした時の1位の選手名を出力する問題.

ソートするだけっぽい.
vector<int>に優先度順に突っ込んでsortする.
サンプルは通った.サブミット.Accept.

C. Sequence of points

2次元上の,奇数個の点A[0], A[1], ..., A[n]が与えられる.
初期点が与えられて,tステップ目にその点を
 A[t%n]に対して対称に移動する
という操作をjステップ行った後の点の座標を求める問題.
nは10^5以下,jは10^18以下.

うーん,10^18回素直に計算することはできない.
でも,x座標と,y座標は分けて計算すればいいよね.
うーん,いや,まてまて.
これって,答え,long longで収まるのか?
収まらない気がするけど,mod pで出力するとか書いてないし…,多倍長?
ちょっと,紙の上でシミュレーションしてみよう….
n=4の場合…,どうみても発散していく気がする….
無理っぽ.
いや,なんか,nは奇数とか書いてある.
奇数の場合は…,もしかして発散しなさそう?
しかも,途中で最初に戻ってくる気がする.
周期的な部分を検出して,周期的な部分は適当に飛ばせば良いのでは.
周期を検出して書いてみる.
大きいランダムケースもすぐ終わった.
周期調べると,全部2n周期になる?
まぁ,良さそう,サブミット.WA.
あれ,long longにしないと答えがオーバーフローするのかな? (しなかった)
long longに直す.WA.
うーん,あ,long longに直し忘れてる箇所が1箇所あった.WA.
あれー.
自分でテストケース幾つか作って確かめる.
あ,jがちょうど周期で割り切れる場合,breakし忘れで,1個余分に移しちゃう….
直した.サブミット.Accept.

D. Broken robot

1000*1000以下のグリッドのある場所に最初ロボットがいる.
時間1後,
 今の場所,ひとつ下,ひとつ右,ひとつ左
のうち,盤面の外に飛び出さない方向を1つ選んで当確率に移動する.
一番下の行についたら止まる.
止まるまでの時間の期待値を求める問題.

うーん.サイズが大きい.
連立一次方程式を解いてたら間に合わない.
収束するまで回しても,多分そんなに収束しない.
わからないので,先にEを読む.
Eが瞬殺問題だったので,終わらせて戻ってくる.
dp[i][j]を(i,j)にロボットが居るとき,一番下の行に辿りつくまでの期待値としよう….
k行目の期待値は,k+1行目の期待値のみに依存する.
なので,行ごとに分けて考えれば良い.
でも,1000回,1000変数の連立一次方程式を解くはめに….
対称性を使うと500変数ぐらい.
無理.
ぴかーん.
k+1行目が全部分かっていて,k行目の一番端の値を決めつけたら,k行目の残りの値はわかる.
一番端の値で2分探索すればいいのではない?
逆の端の値が,本来の値より大きいなら,小さくして,小さいなら大きくする.
書いてみる.
いや,端の値から,次の値を求める式が,単調性が成り立たない,2分探索無理.
うーん.
うーんうーん,制限時間の限り,回してみてdp[i][j]が収束しないか調べてみる.
なんか,求める桁数も小数点以下4桁までで良くて,精度荒くていいっぽいし.
あれ,なんか,1000*1000でも,小数点以下5桁まであうっぽいぞ….
提出.WA.
やっぱり駄目かー.
一応,制限時間ギリギリを狙って,ループ回数を調整.
同じところでWA.
あれ,ちょっと,これって,もしかして….
グリッドのサイズの幅が1のとき,普通に間違える….
修正.サブミット.Accept.

E. Berland collider

1次元で,等速直線運動してる粒子が500000以下与えられる.
逆向きに動く粒子が初めて衝突するまでの時間を求める問題.
同じ向きの粒子は,あたってもすり抜ける.
衝突しないならそれを指摘する.

うーん,なんかよくわからないけど2分探索の匂い.
2分探索で行ける!
時間tまでに衝突するかどうかは
 ある左向きの粒子より,初期位置が左にある粒子のうち,時間tで最も右にある粒子の位置と,左向きの粒子の時間tでの位置が最初と反転していたらぶつかる
というふうな判定をすればいい.
書いた.サブミット.通った.

Result

一応5問解いて,赤復帰.
でも,ケアレスミスが多すぎる.

コメント

[C60] rng

二分探索しなくても、左端を x とおくと、その行の数が全部 x で表せて、右端を見ると一次方程式になって解くことができます (係数が 3^1000 くらいで double に入らなくて大変なことになります)。
さらに頑張って手計算すると、フィボナッチの入った変な式が出てきて一応 double におさまるようになりますが、そうすると誤差で落ちます…

[C61] D

最初rngさんと同じことしてましたが増加か減少かさえ見れば二分探索できそうですね, なるほど.

500変数にすると, 逆行列なりLU分解なりをもっておけば500^3になって通せたりします (対称性を終了直後に気づきましたorz)
  • 2010-07-27 09:22
  • lyr
  • URL
  • 編集

[C62] D

Dは行列が三重対角で,n変数でもO(n)で解けるのですねー.
そして,ちょっとでも変なやり方すると,誤差とかオーバーフローとかで大変なことになるのですね….
てか,2分探索は上手くやればいける気もしてきました,本番はなんであんな壊滅的な結果になったのだろう….(でもやっぱり誤差死しそうな気もする)
lyrさんの,逆行列とかをもっておけば~ってのもありですね,なるほど.

(そして,子音だけ見ると,自分のHNとlyrさんのHNが微妙に似てる気がしてきた)
  • 2010-07-27 17:49
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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