Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM449 DIV1 (参加記録) (この記事を編集する[管理者用])

2009年09月24日00時から.

最近,解き方わからない問題とか普通に残ってて,SRMの記事が書けてなかったりする….
いっそ,1問1記事にしてできるところから適当に書いていこうかな….

Assignment

250,550,950の微変則セット.

EASY

問題開く.問題文わかりやすい.
与えられた2辺の間の角度のsinを最大化すれば良いよね.面積はsqrt(A) sqrt(B) sin(角度) / 2だから….
…,取り敢えず,x軸からどのぐらいの角度を取れるか,各辺について列挙してみよう.
そんなに多くない気がするから,全部組み合わせてsin取って最大値計算すれば良いんじゃないか…?
書いた.良さそう.最悪ケースわからないけど間に合いそう.submit.

MEDIUM

問題文少し長い.てか座標系が嫌すぎる.取り敢えず問題読む.
戦略立てれない.マッチング?でもmod取るんだからDP?
単純なDPでも状態数大きいけど,うまくやればそんな時間掛からないのかも?
取り敢えず,愚直なDPを書く.
N=4でTLE.駄目ぽ.諦めた.

HARD

問題文読む.なんか嫌な感じな問題に見えたけど,サンプル見たりちょっと紙に書いてると,単なるK^カタラン数じゃないか,と気づく.
しかし,カタラン数,除算のないDPだとO(n^2)かかるよな…,てか,O(n)でも無理だろ.
取り敢えず,1000000123を素因数分解かけてみる.素数だ.
じゃあ,割り算できる.カタラン数,コンビネーションで書けるから,階乗を計算できればよろしい.
階乗を20億まで計算して埋め込む….
答え出るよね,サブミット.
大きな数字入れるとなんか挙動不審な気がする.
違うよ!カタラン数は指数部なんだからmod 1000000122しなきゃ!
残り時間7分ぐらい.焦る.
1000000122は素数なわけないし,素因数分解して2乗以上出てきたら困るし….
残り時間2分ぐらい.
素因数分解してみた.2乗でてこないじゃん….
まぁ,時間ないわな….

Challenge

自分以外はEASYしかサブミットしていない….
眺めただけで終了.
HARDチャレンジ食らうと思ってたのに誰もチャレンジしてくれなかった.

System tests

EASY通る.良かった.少し心配だった.HARDは勿論落ちる.
Rateは増える.なんで増えるの.ってかこれで増えるぐらいまで落ちたのか….

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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