Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2009年12月18日01時から.

Start

作業してたら少し遅れた….
300,550,900の変則セット.

EASY

0と.からなる50*50以下の盤面が与えられる.
3*3以上の0で長方形の枠が作られていると思って,一番深い場所の深さは?
枠は接しているかもしれない.関係ない0が混じっているかもしれない.

さぁ,どうしたものか….
Greedy…でもいけそうな気もするけど,なんかすごい場合分けが必要な気もするぞ.
計算時間が怖いけどDPでいいんじゃないの?
取り敢えず,50^5程度のDPを書いてみる.間に合う.サブミット.

MEDIUM

三角形がN段積み上がってる図形で,凸な六角形の数をカウントする問題.
Nは500000以下.

数学ゲーな気がします.
上端の長さと,高さが決められたら,作れる六角形の数は計算できそう,右に何回行って,左に何回行くとかそういうので.
いや,でも,それは場合分けが必要だ….
それをO(1)で計算したところで,上端と高さ2つ決めないといけないのでO(N^2)で死亡コース.
う~ん…,わからん.

HARD

900だし,こっちのが簡単な気がする.
問題文ややこしいな….

根付木の枝にスイッチがついてて,1回押すとON, OFF切り替わる.
5種類の木が与えられて,それぞれにコストが定まっていて,そのコストを払うと,最初の木にぴったり重なる部分に対する枝のスイッチを全部押せる.
ただし,各種類の木に対して,同じ場所(ルートが同じ)で適応できるのは高々1回.
スイッチを全部切り替えるのに必要なコストの最小値は?
5種類の木のノード数は5以下,最初の木のノード数は23以下,最初の木は子供が6ノード以上あるノードはない.

まず,最初に読んだとき,
 各種類の木に対して,同じ場所(ルートが同じ)で適応できるのは高々1回.
って条件は意味がないと勘違いしてしまった….
そう思い込んじゃったら,ダイクストラじゃんとか思って書き始める.
状態数が2^22で,枝数も多いので間に合わない気がする….
でも,まぁ,取り敢えず書いてみる.
答えが合わない.
ようやく,条件に意味があることを理解する.
時間切れ.

Challenge

部屋内で,MEDIUMは1人しか提出してない.たぶん落ちない.問題的にも提出してる人的にも.
HARDは提出0.
ってことで,EASYを狙うしかない.
2*2で枠と判定したら間違う,TLE狙い,を考えて0を50*50を準備.

…読めない.
中盤でこの人は間違えてる,ってのを見つけたんだけど,何を投げれば落ちるのかわからなかった.
終盤で落とされてた.

System Tests

EASYは通った.
0点多い,ってか,EASYが難しいよね.少し昔ならMEDIUMで出題されてそうな問題.
反面,MEDIUMもHARDも結構皆解けてるんだよなぁ….
Rateは微妙に増加.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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