Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Brazilian National Contest 2010 (この記事を編集する[管理者用])

2010年09月19日04時から5時間,11問.
[ Link ]

簡単な問題とか軽い実装問題が多い印象.
GとKでだいぶ嵌ったけど全部解いた.
以下解いた順番.

・問題A
無駄にbig integerを使って書いた.
・問題B
シミュレーションするだけ.
・問題I
強連結成分分解して終わり.
・問題E
左上と右下に配置したとして,2つの円が重なるかどうかを判定した.
・問題J
やるだけ.
・問題F
弱実装問題.やるだけ.Inputの欄に書かれている記号が誤植多すぎて読みにくかった.
・問題H
部分文字列のハッシュを全部計算しておいて,キーを12パターン試して該当するハッシュが存在するかどうかを調べた.
・問題C
それぞれ+に割り振った場合と-に割り振った場合で達成可能かどうか2N回DPしたらTLEだった.
ビットで,そこにたどり着くために+にできるものの集合を覚えておいて,
Fと-Fの両方にたどり着くときに使えるビットは?,片方のみは+や-というふうに1回DPするだけでOKにしたら通った.
・問題K
次にXXXと揃えれるパターンには移動不可というゲームに定式化しなおして,grundy numberを計算した.
サイズが小さいときにいくつかの例外的な処理が必要で嵌った.
・問題D
サービスルートに属するノードを通らず,それぞれサービスルートに辿りつくまでの最短距離を求める.
ワーシャルフロイドしても通った.
でも,それなりに遅かったので,後で問題G解いてからダイクストラで書き直した.
・問題G
3次元幾何.
最初,適当に三角形と三角形の距離を求めるとして,適当に距離が小さくなる方に移動させていったがWAだったりTLE.
最小を達成する2点が三角形の内部同士のことは考えなくて良いので,線分と三角形の距離を求めればよい.
線分の方は,どこで最小を達成するか調べるのに,3分探索するとして,点と三角形の距離を求めた.
それは,三角形の属する平面に垂線引いて,三角形の外なら,三角形のそれぞれの線分に垂線を引いて,後は三角形の頂点との距離を調べる.
3分探索が微妙なのか,結構TLE厳しめに感じたけど,通った.
他の人の実行速度を見る限り,3分探索しなくてもできるっぽい?

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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