Entries

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

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

コメント

[C58] Hi

問題のリンクを張ってくれなくなったな.

[C59]

SRMの参加記録の時は最初からリンク張ってませんよ.
書いてる時にまだ問題文がWebにUploadされてないので.
  • 2010-07-26 08:00
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Open 2010 Algorithm Round 4 参加記録 (この記事を編集する[管理者用])

2010年07月25日01時02分から.

Assignment

全体の参加者で赤が半分以上.
うさぎさんと空さんと一緒の部屋.

EASY

50人以下の銀行の残高が与えられる.
毎週,残高の額に比例する確率で,1人当選して,賞金が配られる.
N週後の0番目の人の残高の期待値を求める問題.
Nは1000以下.

Round 4はEasyは難しい.
Mediumはもっと難しい.
Easyを正確にそれなりの速さで解けば通る.
落ち着いて解け,と言い聞かせる.
問題読む.
ちょっと,問題長い.
大丈夫,落とさないように,ゆっくり読む.
うーん,期待値…,読んだ.
え,ちょっと,これすごい簡単.普段のDIV1 EASYより簡単.のんびりしてたらダメだよ!
適当に,線形性使って,毎週,割り振っていくだけ.(当たる確率は毎週不変であることは気づいてなくてN回ループ)
書く.通らない.
初期化忘れてる.
サンプル通った.サブミット.

MEDIUM

P(n) = nの各桁の積とする.
S = (P(1), P(2), ... )という無限列とする.
長さ50以下の列が与えられたとき,Sの連続部分列としてそれが現れる最初の場所を求める問題.
与えられる列は,Sの中に存在することは保証されている.
与えられる列の各要素は1000000000以下.

嫌らしそうな問題きた.これはいかにも落ちそう.
さて,方針が全く立たない.
うーん.
最初の要素と次の要素を比べて,(n+1)/n倍になっていたら,最初の要素の場所の下1桁はn.
後は,全部,場所の下1桁の数で割って,再帰的にやれば行ける?
0で割ることはできないが….
いや,最初から0しかないとかあり得るわけだし.
そもそも,要素数が1のとき困るではないか.
要素数1のときはどうするの?
うーん….
もしかして:全探索
与えられた列に0だけしかない場合は,適当に例外処理してやる.
そうじゃなかったら,0じゃない要素を1個見つけてきてあげて,それが満たす場所を全列挙して確かめる.
いけそうな気がする.書いてみよう.
….
え,いけるのか?
1を使うと無限に長いのまでできちゃうぞ?
全列挙って言っても無限に可能性がある.
でも,あんまり上の桁で1を使う意味ないことないか?
だって,全部で1を使っていたら,それを取り除けば,より早い場所に存在することになる.
与えられる要素の数が50までだから,100の位より上に1って出てくる事ない.
だから,有限通りしか可能性はない!
よし,書く.
書いた.
通らない.
何バグってたか忘れたけど,バグを取り除く.
サンプル通った.
サブミット.
さて,これって間に合うのか….
ランダムケース生成.
間に合わないorz
これだから,焦るなよ! でもやってしまったものは仕方ない….
うーん.
例えば,87650って答になるか?
67850の方が良いよね….
百の位以上で1を使わないのと同じように,上の桁は,小さい順にソートされてるはず.
これで探索スペース劇的に減るはず枝刈り.
色々ランダムケースを食わせても,200msぐらいで終わる.
自分で,最悪ケースっぽいの作っても400msで終わる.
いける!
リサブミット.

HARD

2次元平面上の1200点以下が与えられる.
どの3点も一直線上にはない.
4点選んで,線分を引いて,交わるようにする方法の数を求める問題.

どうせRound 4のHARDとか無理ゲー.
一応開いてみたけど,わからない.
30分ぐらい残ってるけど,EASYとMEDIUMの見直しをする.
MEDIUMの撃墜ケースを考えておこう.

Intermission

MEDIUMの撃墜ケースは何だ?
TLEする人多そうな気がするが…,でも,Round 4だしなぁ,みんな凄い人ばかりだしなぁ.
チャレンジ失敗して,MEDIUM落ちると,通過できなくなるので,絶対成功するの以外手を出さないことにする.
チャレンジせずに,MEDIUM落ちても,通過できる可能性は…微妙だけどありそう.
EASYはさすがに今回の問題だと落ちないよなぁ…,落ちないよなぁ…,たぶん…,怖い….

Challenge

MEDIUMで全部0なら,って例外処理してる人で,0の個数の場合分けの境界間違ってる人がいる.
これは落ちる.落とせる.落とした.
後はのんびり眺めてるだけ.

System tests

EASYとMEDIUM通った.
MEDIUMは自分が最悪ケースだと思ってたのは全然最悪じゃなくて,システムテストの最悪ケースだと1.7秒かかってた.
怖い…,ってか,本当なら落ちてて良いレベル….
ちょっと,枝刈りに手を抜きすぎてた,でも通ったら正義.
通過ラインは,EASY早解きだったみたい.

コメント

[C58] Hi

問題のリンクを張ってくれなくなったな.

[C59]

SRMの参加記録の時は最初からリンク張ってませんよ.
書いてる時にまだ問題文がWebにUploadされてないので.
  • 2010-07-26 08:00
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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