Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12550 - How do spiders walk on water (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12550

問題概要

滝から距離D (10000以下) の位置に蜘蛛がいる.川は一直線で,長さ1ごとのセルに分割されている.
滝にどこまで近づいても滝に落ちずに帰ってこれるかを求める問題.
蜘蛛の力強さを表すパラメータPが与えられ,今いるセルの水の速さがP以下なら水の流れに逆らって移動できる.
各セルの水の速さは,滝に近づくに連れて単調非減少.
各セルの水の速さは全部与えられるか,最初の一部のみ(最小でも4セル分)与えられる.
最初の一部のみ与えられる場合は,各セルの水の速さは,それより手前の2セルの線形結合で書けることが保証されている.(線形結合の定数はすべての場所で同じ)
どこまで近づいても滝に落ちない,距離Dでも滝に落ちる場合はそれを指摘する.

解法

連立一次方程式を解いて係数を求める.
解が不定(行列式が0)の場合は,等比級数になっているので,別処理をする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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