Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年04月27日00時02分から.
[summary]

Assignment

参加人数の上限が2200人に引き上げられて最初の回.2200人ちゃんと登録してました.
250-500-1000の標準セット.
結構日本人に多い部屋.

EASY

BとWのみからなる100000文字以下の文字列が与えられる.
先頭の文字を削除して,
 それがBだったら,残りの文字列の全てのBをWに変えて,WをBに変える
 それがWだったら,残りの文字列を左右反転させる
文字列がなくなるまで行うとき,Bを削除した回数を求める問題.

シミュレーションでいいよね,O(n)でやる.
Wを取り除いた数で,先頭から見るか,後ろから見るかを変える.
Bを取り除いた数で,今状態が反転してるかどうかを調べる.
簡単簡単.
書く.
合わない.
くだらないミスでしばらく時間を潰してしまったあと合う.
提出.

MEDIUM

H*W (50*50以下) のグリッドを考える.
各グリッドは白か黒の色をしている.
問題文で与えられたプログラムを使って,色を塗り替える.
最終的に色がどうなったかが与えられるので,もともとの色はどうだったか,考えうるパターン数をmod 1000000007で求める問題.

問題の核となる部分がプログラムとか,何も直感が働かないな.
どういうプログラムなんだ….
よくわからん,やってることもよくわからないプログラムだ.
うーん.
取り敢えず,行ごとにバラバラに考えていいことはわかる.
じゃあ,行ごとにDPか?
よく考える.
そんな感じでもない気がする.
ちょっと紙に書いてプログラムをシミュレーションする.
取り敢えず,答えが0かどうかだけ判定してしまおう.
最初,全部2行目を?にしておいて,1行目のプログラムを走らせて,?じゃなくて,色がついた場所で,違う色が付いていたらダメ.
後は,どれだけ自由度があるか?
WBかBWだったらその下が塗られるから,塗られるとその前は何でもいいから,2^WBかBWの下にあるマスの数 とかでいいのかな?
サンプルは合うなぁ.取り敢えず提出.
なんかいろいろ怪しい.swapしてずれるかもしれないし.でも,そういうのも大丈夫だよね?
一応,自信ないので,全探索アルゴリズムを書いて,比べてみよう.
書いた.
合ってない!
うげ.
….
あれ?
これって,単純に,2^?じゃなくなった数 でいいんじゃ?
合う….
てか,どう考えても,これでいいじゃないか.
ちょっと,頭悪すぎる.提出.

HARD

問題文で与えられたプログラムを考える.
そのプログラムで,与えられた出力になるような,Cが高々k個までしか含まれない入力のパターンの数をmod 1000000007で求める問題.
与えられる出力の長さは2500文字以下.

またコレ系の問題かよ!?
でも,難しくなさそうな雰囲気ではあるが….
うーん.
これって,単純に出力できる区間を判定出来れば,単純なDPだよね.
判定はどうすればいいのかな….
できそう.
だが,愚直にやると 長さ^3 になってTLEになる.
うーん.
いや,頑張ればO(長さ^2)でできそう.
書く.
合わない.
間違ってる.
なんかArenaが調子悪いとかいう知らせが来た.
合わない.
間違ってる.
なんか,Arena再起動するとかきた.これはノーコンテストフラグ.
合わない.
時間切れ.

Challenge

Arena調子悪くてノーコンテスト.
チャレンジも後に行われたみたいだけど参加してなかった.

System tests

EASYとMEDIUM通る.
No Rated.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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