Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年10月06日10時02分から.

Assignment

250-550-950の変則セット.
950からやってもいいのかもしれない.

EASY

S(X)で10進数でXの各桁の和を表すこととする.
例えば,S(22)=2+2=4,S(484)=4+8+4=16.
S(X*X)=S(X)*S(X)を満たすXをうさぎ数と呼ぶ.
A以上B以下のうさぎ数は何個あるか求める問題.
Bは10億以下.

rngセット!
sqrt取るから平方数だけ調べれば良いよね,全部調べれるよね.
rngセットらしからぬ簡単なEASY.
….
違うって!
さぁ,どうしたものか….
とりあえず,2桁で考えてみる.164を各桁の間にスペース入れて1 6 4と書くとx y * x y = x^2 2xy y^2で
 S(x y)=x+y
 S(x^2 2xy y^2)=(x+y)^2
だから,x^2,2xy,y^2が10以上になるといけない.
同様に,3桁以上の場合も考えられる.繰り上がるとダメ.
繰り上がるかどうかってどうやって判定するんだ,単純じゃない気もするが….
いやいや,各桁0~3まで全部調べれば良いのだ.
書く.
合わない….
小文字のaと大文字のAを書き間違えてた.あんまり大文字の変数名使うの良くないよな….
修正.サンプル通過.サブミット.
最大ケース入れる.間に合う.
まぁ,これは大丈夫だろう.次に行く.
rngセットなら950は解けないので550をやろう….rngセットの550も解けない気もするけど….

MEDIUM

1列のぷよぷよ.1個ずつぷよが落ちてくる.ぷよは全部で4色.L個以上並ぶと消える.
N個落ちてきたとき,ちょうど全部のぷよが消えた.
そのような落ち方のパターン数をmod 1000000007で求める問題.
Nは1000以下,Lは10以下.

どうみてもDP.
DP…なんだけど,どうするのだ.
カッコの対応,カッコがL個で対応するとして,カッコの種類が4種類の感じ?カタラン数の拡張?
最初に落ちてきたぷよに着目して,それは,全部消えるパターンを間に挟みながらL個並ぶ.
間のパターンの数はDP+DPで求めれるはず.
いけそう.
….
単純にやるとO(N^3)….
いや,間のパターン数のDPは毎回全部計算しなおす必要はない.
書く.かきかき.
てか,間は,最初に落ちてきたぷよと同じ色が両端だったらだめだよね….L個降ってきたあとはOK.
えええええ.
普通に4で割って,3をかければ済むことか?
最後の残りの処理が分からん.
いや,間も,最初と最後のぷよの色が違うことも許されるパターンもあって,それは16で割って9でかけるとか?
えええええええええええ.
混乱.
適当に書く.
合わない.
N=4, L=2, return 28すら合わない.
残り20分.
950の提出が多いので問題だけ見に行く.
戻ってきて,最後にちょっとあがいたけど,無理だった.

HARD

1~Nまでの数字のうちM個の数字を書いたカードをK枚用意する.
1~Nまでの数字全てに対して,それぞれのカードに含まれているかどうかの情報が与えられたら,数字を確定できる最小のカード枚数Kを求める問題.
N,Mは10億以下.

わからんって….
うーん….
M=N/2のときは,Nのビット数が答えか?
各数字を一意に2進数で表示すれば良い.
ビット数っぽいし,n/m進数とかで適当にlog(n)/log(n/m)みたいな感じにならないかなー.
ならない.
うーん.
あれ?
NがMよりずっと大きい場合を考えると,N個の数字があって,1回でM個の数字を除外できるのだから,
Nが2Mより多かったら,Mを引いていって,そうでなければ,残りの候補を半分いれたカードを作ってN=(N+1)/2にして,
N=1に到達するステップ数が答え!
….
よく考えろ,違うだろう.
最初に全部のカードを決めないといけないので,残りの候補を散らばせるような都合の良い配置はできない.
うーん.
最初高さNの塔が1個あって,毎ステップ塔を分裂できる.ただし,塔を分裂してできた新しい塔の高さの和はM.
そうやって,全部が高さ1の塔になるまでのステップ数の最小値が答えだ.
時間ない,ギブアップ,MEDIUMやろうよ.

Challenge

HARDを3人提出してるけど,正直解けてるとは思えない.
N-=MとかN=(N+1)/2みたいなのが見えたら即座にチャレンジする.また,コードがみょうに簡潔な場合もチャレンジしよう.N=10億,Mはちっちゃめな適当な値.
開始直後2人落とせた.1人は先越された.

System tests

EASYはつつがなく通過.
HARDは結局ほとんど通ってない.
EASYのみの中ではたぶん2位だけど,MEDIUM提出者はほとんど落ちてないので,Rateは結構落ちた.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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