Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Yandex Open 2011 Qualification 1 (参加記録) (この記事を編集する[管理者用])

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

Yandex Openなるものが開催されるらしい.
予選は2回行われて,それぞれ上位500人が追加.
配点は500-1000-1500-2000-2500.

A. Plug-in

200000文字以下の文字列が与えられる.
連続する2文字で,同じ文字のものが,存在すればそれを消していく.
最終的に残る文字列を出力する問題.

微妙に問題文が読みにくいな.
ちゃんと定義が書いてあるところ以外の意味がつかみにくい.
やるだけ…,かと思ったが文字列の長さが長い.O(n^2)でTLEかな.
うーん,スタック使えばO(n)か.Aの割には難しい気が….
書く.サブミット.pretest passed.

B. Sequence Formatting

正整数,「...」,「,」,「 」(半角スペース)のみからなる文字列が与えられる.
以下を満たすように整形する問題.
 (1) 「,」の後には1つの半角スペースをつける
 (2) 「...」の前には1つの半角スペースをつける
 (3) 2つの正整数の間に,1個以上の半角スペースしかない場合は,正整数の間はちょうど1個の半角スペースにする
 (4) それ以外の半角スペースはない
 (5) 行頭,行末は半角スペースをなくす.これはルール(1),(2)よりも優先させる

やるだけ問題だけど,意外と書きにくい気がする.
書く.
これでいいかな.サブミット.pretest passed.

C. Average Score

n個 (100000以下) の1以上5以下の整数が与えられる.
それを2つのグループに分けたい.
片方のグループにはちょうどa個の整数,もう片方にはちょうどb個の整数を含むようにしたい.(a+b=n)
両方のグループの平均値を求め,その和を最大化したい.
そのようなグループ分けの仕方を求める問題.
複数あるなら,辞書順最小のものを求める.

どう考えても,集合サイズの小さい方に大きい数字を追いやれば良い.
後は辞書順最小になるようにgreedyに選ぶだけ.
サンプル通る.提出.pretest passed.

D. Polycarps Picture Gallery

m個 (40以下) の整数a[k]が与えられる.
n要素 (1000以下) の数列Xで,以下の条件をみたすものを1つ求める問題.
 (1) Xに含まれる各要素は1~mの整数
 (2) Xに含まれるkの数はa[k]以下
 (3) Xは隣り合う要素が等しくない (X[1]とX[n]も隣り合うとみなす)

問題を盛大に勘違いした.
(3)を隣り合う要素の差はちょうど1 (1とmの差も1) なんだと勘違い.
えっと,めんどくさい.
まず,m個のモノが円周上に並んでいて,それに輪をふにゃっとかけていく感じ.
その輪が何周するかで場合分けしよう.
後,1周もしない場合は,どこからどこまで行って戻ってくるかも場合分け.
後は,たどり着いた場所で行ったり来たりでgreedyに潰してn要素潰せるかどうか判定.
書く.
サブミット.WA.
m=1の場合にミスってる,など.
いろいろトリッキーな問題だなぁ.
WA.WA.WA.….
ん,なんか問題違うくないか?
問題ぜんぜん違う.読み間違えてるではないか.
なんだ,これから簡単じゃない?
考える.
普通にやればよさそう.
書く.
あれ,意外と普通がむずいのか?
適当にやってしまう.
pretest passed.

E. Martian Food

考えていない.

Hacks

AがTLEがたくさんいるはず.
と,思ったらpretestのcase 5でTLEしてる人を発見.
TLEするケースがpretestにあるのか.A問題だもんな.これは落とせないか,諦める.
B問題で,「1 2 3」で「123」にならなさそうなのを発見.落ちない.
え.
あ,条件(3)を見落としていた.
てか,それはpretestで落としてくれよー.
まぁ,同じ読み間違えしてる人がいないか探す.
最終的に合計で1成功2失敗で最初の失敗は取り戻した.

Results

AとCが通る.BとDは落ちる.
Bは読み間違え.Dは適当にやり過ぎ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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