Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

The Sixth Hunan Collegiate Programming Contest Semilive (この記事を編集する[管理者用])

2010年10月31日18時から5時間,11問.
[ Link ]

前日と打って変わって,帰宅して,家の快適な環境で参加.
9問目までは簡単めで残り2問が無理ゲー.
9問目まで2時間以内で解いたが,J問題に2時間半使って結局通らなかった.
9問目までノーミスで通せたのは気持ちよかったかもしれない.
以下問題別.

・問題A (解いた)
サンプル見る限り,入力/2を出力すれば良さそうだったのでそうした.
・問題B (解いた)
やるだけ.
・問題C (解いた)
やるだけ.別に最初に書かれてるやり方でなくても普通に判定すればよい.
・問題D (解いた)
箱サイズを縦横2Rだけ小さくして半径0で考える.
箱の方を鏡に移して2次元平面上全部箱で埋め尽くして考えればよい.
最後はmod 2*箱サイズで考えることになる.
・問題E (解いた)
二分探索.
1+IRR^kというのは(1+IRR)^kという意味らしい.これが最大の罠.
・問題F (解いた)
枝刈りなし全探索でもまあまあの時間で終わるっぽかったので頑張って枝刈った.
・問題G (解いた)
ダイクストラ.各枝のコストを求めるのは3分探索した.
・問題H (解いた)
DPでやるだけ.1回DPしておけば,全部のクエリに対して答えが求まる.
・問題I (解いた)
完全な長方形が除かれるというのが嫌らしい気がしたので,長方形も許す場合を小さいケースで全探索してみた.
すると,どうみてもフィボナッチ数が出てきたので,それで実装.
・問題J (解いてない)
頑張って実装したが,最初はTLE.
高速化して色々試したがずっとWAから抜け出せなかった.
・問題K (解いてない)
昔やった2次元版(三角形と円の共通部分の面積)でもそれなりに難しいのに,3次元でできるわけないと思って放置.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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