Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年05月14日00時10分から2時間,5問.codeforcesルール
[ LINK ]

サーバが不調で開始が10分遅れて0時10分開始.
配点は500-1000-1500-2000-2500の標準セット.

A. Magical Array

長さN (10^5以下) の整数列が与えられる.
空でない,その連続する部分列で,同じ要素しか含まないものは何個あるかを求める問題.

問題文の意味が分からない.
coincideってなんだ….
一致するってことか?
サンプル見るかぎりそうっぽい.
じゃ,同じ要素が連続してる数を数えるだけだ.
書く.サブミット.pretest passed.

B. Doctor

最初1~Nまで番号つけられたN人が順番に一列に並んでいる.(Nは10^5以下)
一番最初にいる人が,一番後ろに回るという操作をK (10^14以下) 回繰り返す.
ただし,番号kの人が,一番先頭にa[k] (10^9以下) 回目に来たときは,並び直さずに帰ってしまう.
最終的の列の状態を出力する問題.
K回も操作を行えないときはそれを指摘する.

二分探索っぽい.
が,意外とめんどう,ってか,バグリそうな感じ.
まぁ,書く.
入力のKを読み込む変数名をsumにしようかと思ったけど,あとでsumは使いそうだからallにする.
書く.
合わない.
sumとallを書き間違えてる….
直す.サンプルは合う.提出.WA.
まだ書き間違えてた.
直す.提出.pretest passed.
ちょっと見直しする.良さそう.次へ.

C. Track

n*m (50*50以下) の盤面が与えられる.
スタート地点とゴール地点が1個ずつあって,その他のセルにはアルファベット小文字が書かれている.
隣接してるとは上下左右の4方向とし,隣接マスに動くのに時間1だけかかる.
スタート地点から,ゴール地点まで移動するのに,高々k種類 (4以下) のアルファベットのセルしか経由してはいけない.
その条件で最小距離で移動したい.
移動経路のアルファベットを出力する問題.複数あるなら辞書順最小のパスを求める.

え,方針が思いつかない.
kが4以下だから,全パターン試しても…間に合わないよな?
だいたい26^4*50*50ぐらいか…,無理っぽい.
Dを見に行く.
Dをやった後に帰ってくる.
もうちょっと,ちゃんと計算しよう.
C(26,4)*50^2…,あれ,ぎりぎり間に合うのかも?
辞書順最小のパスをどうやって求めるかだが….
単に,1文字ずつ確定していけばいいのか.
使う文字を固定したとき,50^2でちゃんと計算できそうだ.
書こう.
….
これめんどい.
….
バグを埋め込みつつなんとか書けた.
サブミット.WA.
うーん.
いろいろ酷いバグを修正した後pretest passed.

D. Numbers

区間[a,b]内の整数で,2~k-1では割り切れず,kで割り切れる物の数を求める問題.
a, b, k は2*10^9以下.

えーと,問題文が分かりやすい.
….
まず,kが素数じゃないと0だよね…,kの素因数で割れちゃう.
てか,kが大きいと0だよね?
2*3*5*7*11*…*kが2*10^9を超えたら答えは0だろ.(違!)
kは高々30ぐらいか.
じゃあ,包除原理でできそう.
書く.
サブミット.WA.
あれぇ….
試しにkを30をちょっと超えた素数とかにも対応してやってみる.
あれ,答えが正だ.
なんで?
….
え,いや,そりゃそうだろ.
kがsqrt(10^9)を超えると答えが0になるんだよ.(2重に違! 答えは1かもしれない 10^9じゃなくて2*10^9)
でも,同様に包除原理でできるよね.
数字かけるとどんどん大きくなるから,あまりに大きくなった部分は無視すれば良いから.
書く.
pretest passed.

E. Two Subsequences

s1, s2を文字列として,
 f(s1, s2) = s1がprefix,s2がsuffixとなるような長さ最小の文字列
で定義する.また,
 f(s1, s2, s3, ..., sk) = f( f(s1, s2, ..., s(k-1)), sk)
と定義する.
01のみからなる20文字以下の文字列,からなる配列Aが与えられる.要素数は200000以下.
Aの要素を2つに順序を保つように分割し,それらをfにかましたときの長さの和の最小値を求める問題.つまり,
 f(A[i0], A[i1], ..., A[ik])
 f(A[j0], A[j1], ..., A[jl])
の長さの和の最小値を求める問題.
ただし,Aの各要素はA[i?]かA[j?]のどちらか片方に含まれていなければいけず,
 i(x-1)よりixの方が大きく
 j(x-1)よりjxの方が大きい.

考えてない.

Hacks

Dで妙なことやってる人がいる.
b/kのサイズのbool型のvectorを取っている.
MLEだろー.と思ったら失敗した.
そういえば,boolのvectorは8つで1バイトになってて,なんか扱いが変なんだっけか…,なんかそういうの聞いたことある気がする.
と,思ったらそれが落とされていた.
よくみたら,その後,k回ループを回していた.kがでかいほうが落ちたのか….

Results

ABC通る.Dが落ちる.
あれだけ酷い勘違いをした後にまともに解けるわけはなかった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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