Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

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

DIV1,DIV2共通問題セット.ir5さんとrng_58さんがwriter.
配点は500-1000-1500-2000-2500.

A. Bus Game

x枚 (10^6以下) の100円玉とy枚 (10^6以下) の10円玉がある.
2人で順番に220円ずつ取っていく.
ただし,先手は100円玉ができるだけ多くなるように取り,後手は10円玉ができるだけ多くなるように取る.
最後に220円取れるのは先手と後手どちらかを答える問題.

おー,市バスだ.
シミュレーションやるだけかな.
書く.サブミット.pretest passed.

B. Colorful Field

n*m (40000*40000以下) のグリッドを考える.
k個 (10^3以下) だけ使えないマスが与えられる.
使えないグリッドを飛ばしながら,row-major orderで
 人参,キウィ,ぶどう,人参,キウィ,ぶどう,人参,キウィ,ぶどう,…
と置いていく.
t個 (10^3以下) のマスが与えられるので,それぞれ,そのマスに何があるか,もしくは使えないマスか,を答える問題.

ふむふむ.
そこまでに,mod 3で使えるマスが何個あったか求めるだけ.
使えないマスの数を求めたらいいよね.
各行に何個使えないのがあるか,記憶しておいて,その行までに使えないマスの総数も決めておく.
で,該当する行は全部調べてもいいや.(使えないマスの数が小さいのに気づいていない)
書き書き.
全然合わねぇ….
あ,使えるマスを数えるはずが,本当に使えないマスを数えてた.
修正.
合った.サブミット.pretest passed.

C. Beaver

10^5文字以下の文字列Xが与えられる.
また,10文字以下の文字列が10個以下与えられる.
Xの部分文字列で,与えられた文字列をどれも含まないもののうち,最長のものを求める問題.
複数あるならどれでも良い.

うーん,2分探索か?
いや,面倒なだけでそんなのいらない気がする.
尺取メソッド?
うん,それでいけそう.
書く.
サンプル通る.提出.pretest passed.

D. Domino Carpet

n個 (10000以下) のスイッチがある.スイッチは一列に並んでいて最初は全部OFF.スイッチの番号は順番に1~n. k個 (10以下) のスイッチのみONの状態にしたい. L個 (100以下) の整数 a[0], a[1], ..., a[l-1] が与えられる. 1回の操作で連続するa[k]個のスイッチを反転させることができる. 最小で何回の操作で目的を達成できるかを求める問題.

取り敢えず,全くわからない.そして,サンプルが弱すぎる.
うーん.
取り敢えず,反転させないといけない一番左のスイッチを,適応範囲の左端として適応するのを繰り返していけば良いよね.(嘘です)
ってな感じの探索やって終わるわけないな….
kが10と小さいのがポイントのはずだ.
うーん,スイッチ反転させるの,2つ組で考えたらいいんじゃないか? ビットDPみたいな感じにして.
そんなことはない.
k=3でも,色々なパターンで達成できる….
うーむ.
取り敢えず,連続する長さlenだけ反転させるのに必要な最小コストぐらいはDPで求めておけば良いのだろう.
それはすんなりできるよね.(大嘘)
で…?
反転させるべきスイッチと,その間にあるスイッチ群で,2^(2k-1)の状態数でBFSするとか,そんな感じ?
いや,n=10でa[0]=9, a[1]=8の場合,2回の操作で,1個だけスイッチを反転させることができるスイッチとできないスイッチがある.
そういうのをどうすればいい?
うーん.
はっ,真ん中のほうがそういうのができない場合が多くて,それは使えないa[k]が存在するということ.
a[k]はソートしておいて,DPするときに,どこまで使える場合に,長さlenを反転させる最小コストとかを記憶すれば.
おお,いいんじゃないか?
あれ,そのDPって簡単にできるか?
…出来なさそうな気がしてきたのだけど.
ダイクストラでいけるか.いや,それはTLEじゃないかな….
え,どうしたらいいんだ.
ってところで,残り時間が絶望的になってきたので放棄.

E. Martian Food

N*N (Nは200000以下) のグリッドを考える.
一番左下から右上へ,右か上に移動することを繰り返して移動する.
(a,b)-(a+c,b+c)を対角線とする長方形内のセルには,それぞれカウンターが設置されている.
最初すべてのカウンターはt (10^14以下) にセットされている.
1マス移動するたびに,移動後のマスとカウンターのマスのマンハッタン距離分だけカウンターの値が減少する.
全てののカウンターが0以上を保ちつつ,右上に辿りつける中で,辞書順最小の経路 (右ステップを優先する) を求める問題.

考えていない.

Hacks

Aで100円=10円*12になってる人がいたので落とす.

Results

ABC通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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