Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年01月20日01時から.

Assignment

平和そうな部屋だー,ほのぼの.

EASY

 X op C
という形の不等式が50個以下与えられる.
opは5種類の等号,不等号のどれかで,Cは0以上1000以下の整数.
さて,Xとして自由な実数を選んで良いとき,最高で何個の不等式を満たすことができますか?

さて,EASYだから全探索かな,不等式の数は…,50個!無理だ!
いやいや,Cは1000までしかないんだから,Xを-1から1001まで動かして調べれば良いのだ.
書いた.あー,等号の場合もあるのか…,あー,Xは実数で良かったのか,整数だと思ってた.0.5刻みで動かせば十分かな.
問題読んでなさすぎる.これはサンプルないと死んでたなー.
でも,もう大丈夫だよね…?サブミット.
一応,問題文とサンプルをもう一度確認しておく.大丈夫そうだ.

MEDIUM

パスカルの三角形っぽく,下の2つの数字を足したら上の数字なるような三角形は何個作れますか?
数字は全部正の整数.
入力は,段数と一番上の数字.
段数も一番上の数字も1000000以下.

まず,一番下の数字に二項係数を掛けながら足していけば一番上の数字になる.
だって,一番上から,一番下の数字に辿り着くパスの数だけ足されるわけだよね.
じゃあ,段数が大きいと即座に0でOK.
何段から0になるか調べる…,21段ぐらい?
じゃ,後は単純にDPすれば良いんじゃないの?
書いた.
サンプルテストでTLEするな….
悩む.
最初に,真ん中の数字から足すと,状態数少なくなる?
サンプルは通るけど,自分で作ったケースでTLE.
てか,TopCoderはこんなad-hocに解決するものじゃない!(時々あるけど…)
うーん?
いやいや,これって,単に二項係数とばしの和を覚えておけば,O(段数*一番上の数字)でいけるじゃん.
ってか,そんなことしなくても,単純に,分割数求める感じのDPでいいじゃないか….
なんで,こんなのに時間かけてるの?orz
サブミット.

HARD

k=max(n,m)とする.n*mの升目に,各行,各列に高々1回のみしか同じ数字が出ないように1~kの数字を埋めたい.
答えのうち,辞書順最小のものを求める問題.
nもmも50以下.

え,難しくないんじゃ…?
いや,考えてみると良くわからん.
でも,効率的に枝刈れそうだし,探索で良いんじゃ?
無駄にはならないと思って取り敢えず探索だけ書いた.
枝刈り書こうと思ったら,効率よく枝が刈れないことに気づいた,ほぇ.
今の盤面から,何でも良いから解が1つあるかどうかだけ判定したい.
それはGreedyにおいていけばできるのでは → できない!
なんだ,これ,どうやるんだ…?
フロー…も,複数文字があるからなぁ….
時間切れ.

Challenge

250でX > 1000で落ちる人いないかなー?
全部開きながらチェックしていく…,そんな人はいなかった.
なんか,この人,実質2^50のサブセット全部成り立つのが存在するのを列挙してるんじゃないか…?
ランダム最大作って投げる.落ちた.+50ポイント.

System tests

EASYとMEDIUMは通る.
HARDは結局正解数0なのか…やっぱり難しかったようだ.
自分の部屋は,system testで4人EASY落ちてた.
結構見たつもりなのに,全然見てないようだ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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