Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #26 (参加記録) (この記事を編集する[管理者用])

2010年08月17日00時から2時間,5問.
[ Link ]

Codeforces formatについて

今回からCodeforcesオリジナルの新ルール.
TopCoderと同じように得点方式となり,コンテスト開始時から1分おきに,各問題の点数が減っていく.
また,提出したときは簡易テストしか行われず,精密なシステムテストはコンテスト終了後に行われる.
提出して,簡易テスト通過したコードはロックすることができ,ロックすると再提出ができなくなる.
(再提出の場合は,TopCoderと同じように5%の減点があり,問題ごとの最低点も決められている)
ロックした問題については,(コンテスト中に)他人のコードを見ることができるようになり,撃墜することができるようになる.
撃墜に成功したら100点,失敗したら-50点.

A. Almost Prime

Almost Primeとは,素数の約数の数が厳密に2個のもの.
1~NまでにAlmost Primeが何個あるか求める問題.
Nは3000以下.

C問題からやろうとして,問題だけ読んだけど,嫌な感じだったので普通にA問題からやる.
1個1個判定しても十分間に合うサイズ.
なので,そうする.
サブミット.簡易テスト通過.

B. Regular Bracket Sequence

()からなる1000000文字以下の文字列が与えられる.
その部分列(部分文字列じゃない)でカッコがちゃんと対応付けられていて,最も長いものの長さを求める問題.

あれ,これ,同じ問題が昔なかったか?
あるような,コピペサブミット.WA.
あ,昔のは,部分文字列で,今回は部分列なのか.
だったら簡単じゃないの?
左から眺めていて,(の出てきた数を数えて,)が出てきたらgreedyに対応させる.
サブミット.簡易テスト通過.

C. Parquet

n*mの箱に,1*2のピースと,2*1のピースと,2*2のピースを使って敷き詰める.
それぞれのピースの使える数が与えられたとき,敷き詰め方を1つ求める問題.
不可能ならそれを指摘する.
n,mは100以下.

端から,置けるのをでっかいのからgreedyにおいていけばいいのでは?
いや,中途半端に余った部分をちゃんと処理できなくなる可能性がある.
n,mが奇数なら中途半端に残るので,そこから処理してあげたらいいのでは….
良さそう.書く.意外と面倒.
これはコーナーケースが怖そう.
いくらか自前でテストする.
良さそう.サブミット.簡易テスト通過.

D. Tickets

+の玉n個と-の玉がm個が箱に入っている.
初期値はkで,玉を1個ずつ引いていって,+を引いたら1足す,-を引いたら1引く.
最後までマイナスにならない確率を求める問題.
n,mは100000以下,kは10以下.

解析的に求まる気もするし,そうじゃない気もする.
妙に値が小さいので解析的に求まるんじゃないのではないか….
適当に,現在の値が200を超えるとか,沢山になったらもうマイナスにならないと仮定して状態数減らしてDPすればいいのではないか.
要求精度も高くないし.
書く.
大きなテストケースを適当に入れてみる.あんまり値がブレない.いけるんじゃない?
サブミット.簡易テスト通過.

A, B, Cはロックする.
で,他の人のコードを眺める.
BでO(n^2)の人がいたので,落とそう.
撃墜方法がわからない.長さ1000000の文字列を上手く貼り付けてない疑惑.
その文字列を生成するコードでもいいらしいので,コードを提出.落とせた.

E. Multithreading

N個のプロセスがあって,プロセスiがn[i]回
 y[i] := y
 y := y[i]+1
という操作を行う.メモリは共通.
最初yの値が0で最終的にWになる方法を1つ求める問題.
方法とは,全部のプロセスは1行ずつ実行する(その間は他のプロセスは邪魔しない)として,実行順番のこと.

うーん.
n=1はコーナーケース.別処理するべき.
Wがn[i]の中で一番小さいの以上は作れそう.
最初にiを使って,いくつか無駄に使って,iを使って,後は順番に使う.
それ未満には出来ない?
いや,できる.
2段階無駄なのを処理させると,2にできそう.
そして,そもそもn[i]=1のものがあれば,それを使うことで1にできる.
後はadhocに処理を書くだけ.
意外と面倒.
書いた.サブミット.簡易テスト通過.

DとEをロックする.
Dは他の人のコード見ると解析的に求まってるなぁ….
Eのコード読み間違えて,1回ハック失敗.

Result

DがWAで落ちて,他は通った.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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