Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年04月08日10時02分から.
[summary]

Assignment

250-500-1000の標準セット.
見覚えのある日本人がたくさんの部屋.なんか嬉しい.

EASY

1桁以上9桁以下の文字列が50個以下与えられる.文字は0~9の数字.
000000000~999999999までの数字の中で,少なくても1つ与えられた文字列をサフィックスにもつものの割合を求める問題.

えっと,やるだけ実装問題…ってことでいいんだよな,なんか妙に自信ない.
いや,良いはず,自信持て.
与えられた文字列ですでにサフィックスの関係にあるものは短いものだけ残して削除.
後は,単純に 10^文字列の長さ に1個該当するからそれを数えていくだけ.
で,これは本当に独立に該当するよな,複数のサフィックスに該当したりしないよね….するわけない.
じゃ,書くだけ.
とりあえず,ソートして,str[i]がstr[i+1]~str[n-1]までのどれかのサフィックスになってたら削除,といこう.
書いた.全然合わない….
あれ….
!!?
サフィックスって,後ろだ,プレフィックスじゃねぇorz
じゃ,じゃあ,str[i]がstr[0]~str[i-1]までのどれかのサフィックスになってたら削除,で.
…,合わない.
いやいやいや,サフィックスだと,ソートの意味がねぇだ….
じゃじゃじゃ,じゃあ,str[i]がstr[0]~str[n-1]までのどれかのサフィックスになってたら削除,で.
同じ要素があったら全部削除されてる!
じゃじゃじゃじゃじゃじゃ,じゃあ,最初に同じ要素を1つにまとめておく.
サンプル通った.サブミット.
色々突貫工事で修正してしまったので超心配なので,見直しする.
これはダメの典型例….
良さそうなので次へ.

MEDIUM

codeforces formatみたいなコンテストを行う.
各問題を解くのに必要な時間が与えられたとき,最大スコアを求める問題.
正確に言うと,コンテスト時間T (100000以下) が与えらる.(ちょうどT後はサブミットできる)
また,各問題 (問題数は50以下) に対して 最高点と減少点,その問題を解くのに必要な時間が与えられる.
問題を解いて得られる点数は
 最高点 - 減少点 * コンテスト開始時からその問題を解き終わるまでに経過した時間
でマイナスになることもある.

えっと,問題数50だからビットDPできない.
どうするべ.
あ,そうか,減少点の高いものから解いていくのがいいから,減少点でソートしてDPでいいのかな.
違うだろ!
減少点が同じなら,早く解ける問題から解いたほうがいいよな….
どこで釣り合うのだろう….
割るだけっぽい.
後はソートしてDP書くだけ.
がりがり.
書いた.サンプル通る.サブミット.

HARD

0~N-1までのN個の数字から,和がNの倍数になるように,K個の数字を選ぶ選び方の数をmod 1000000007で求める問題.
Nは10^9以下,Kは1000以下.

全然わからなかった.

Challenge

MEDIUMのサンプル弱かったので,減少点でソートとかして間違えてる人がいそう.
ランダム最大を用意しておく.
なんかソートがおかしい人を見つけ次第落として4成功1失敗.
DPしてない人がいて,落とせそうだったけど,誰かに先をこされた.

System tests

EASYとMEDIUM通る.
チャレンジが効いて好成績.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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