Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年03月30日20時02分から.
[summary]

Assignment

250-500-1000の標準セット.

EASY

実数 A (-10以上10以下) と B (-2以上2以下) が与えられる.
最初の得点は0.
行動の順番は自由にして良いので,ちょうどnA (0以上50以下) 回だけ以下の(1)を行う,ちょうどnB (0以上50以下) 回だけ以下の(2)を行ってできる最高点を求める問題.
 (1) 現在得点にAを足す
 (2) 現在得点にBをかける

えーっと,これは….
絶対これは,計算量的な意味で簡単にできるはず.少なくても場合分けすればできそうだし.
でも,それをやると泥沼…,ちゃんとロジカルに考えないとダメ.これは下手なことすると落とす.
….
もうDPでいいんじゃないか?
Aを足す回数とBを足す回数を状態にして普通にDPできるだろう.
あ,マイナスがあるから,最大値と最小値両方覚えるDPか…,ちょっと面倒.
でも,書くのみ.DP以上に正確に解く方法はない…気がする.
ゴーゴー.
書いた.サブミット.

MEDIUM

beautifulな数列aとは以下の条件をみたすものである.  ・数列の各要素は0以上40以下の整数  ・k番目の要素は,0番目~k-1番目の要素の平均値以下にならないといけない  ・a[k] > a[k+1] > a[k+2]というように2回連続で減ることはない 一部埋まっていない,長さN (40以下) の数列が与えられるので,埋まってない場所を適当な数字に置き換えてできるbeautifulな数列の個数をmod 10^9+7で求める問題.

サイズは40以下…,2つに分けて全探索で2^(N/2)とかかな?
違うなぁ.
うーん,単純にDPじゃない?
平均以下だから,これまでの和を状態に覚えておけば良い.
後,何回連続で下がっているかも状態に含める.
書く.
…,あ,これ状態に,前回の数字が必要だな,下がってるかどうかのチェックのため.
これ,計算時間量40^5とかになるな….
まぁ,大丈夫な気もするし,ゴーゴー.ダメだったら計算量落とせそうだし.
書いた.
普通に最悪ケースで間に合う.
じゃ,サブミット.

HARD

幅W (1000以下),高さH (10^9以下) のグリッドを考える.
そのグリッドの jewelCount (1000以下) だけのマスにゴールドが置いてある.置いてある量はマスによって変わる.
移動は,
 左右に1マス移動する (ただし合計でLR回 (1000以下) までしか移動できない)
 下に1マス移動する
の2パターンでき,それぞれの移動に必要な時間が与えられる.
あるgoalValue以上のゴールドを集めるのに必要な最小時間を求める問題.不可能ならばそれを指摘する.

全然わからなかった.

Challenge

EASYは場合分けとかしてる人がいれば色々落ちそうだなぁ,とは思っていたものの,よく見たらサンプルが異常に強いことに気づく.
なので,適当に眺める程度にやろうと思ったら他の人が結構落としてた.
慌ててちゃんと見始めたけど,特に見つけられなかった.
そして,勘違いして1ミス.

System tests

EASYとMEDIUM通る.
簡単なDPだったので,せっかくMEDIUM早解きでいい順位だったのに,Challengeで失敗してダメダメ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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