Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年03月09日01時02分から.

Assignment

250-550-1000の微変則セット.

EASY

N匹 (50以下) の同じ街に住むウサギに,
 あなたの街に,あなた以外に,あなたと同じ色のウサギは何人いますか?
と聞いた答えa[k]が (1000000以下) 与えられる.
答えが正しいと仮定したとき,その街に住むウサギの最小数を求める問題.

うさぎセットだ….なのにCat Pochi.
同じ答えのウサギを全部まとめてあげて,a[k]+1を足していくだけ.
あ,そうか,その答えのウサギはa[k]+2以上いたら,2グループに分けないといけないのか.
まぁ,a[k]って答えたウサギをa[k]+1匹消して,処理続行でいい.
書くだけ.書いた.サブミット.

MEDIUM

半角スペースをSPと書き,改行をNLと書くことにする.
50行以下のテキストで,各行,s[k]個の半角スペースがあるものを作りたい.
この時,SPACEキーとDELETEキーとRETURNキーを押す回数の合計数を最小化したい.
カーソルの移動は自由で,
 SPACEキーを押すと,その行のスペースの数が1個増える
 DELETEキーを押すと,その行のスペースの数が1個減る
 RETURNキーを押すと,その行と同じ数だけのスペースを持つ行が,その次の行に付け加わる

550だけあって,ちょっと面倒なDPっぽい.
しかも,サンプルが弱すぎる….これは慎重にやらないと.
多分,ある区間を作るとき,あるものから作った場合の最小コストを記録する形で行ける…よね.
 dp[a][b][c] = 区間[a,b]のものを作るとき,最初に使う行のスペースの数はs[k]個のときの最小コスト
一部ぐらいはgreedyが出来る部分があって,もうちょっと単純に行けるかと思ったけど,O(n^5)は間に合うだろうし,
下手に何か仮定したら間違えそうな問題だから,できるだけ間違えないようなアルゴリズムで書く!
では,書く.いろいろ混乱.
苦戦しながら書き上げた.サブミット.
最大ケース試す.TLE.えええええええーーー.
流石に無駄にループ回しすぎてる部分を削る.最大ケースで600msぐらい.リサブミット.
自明な小さいケースを入れる.答えがバグる.ローカルで試す.ローカルだとうまく動く.
なんでだ….
配列の範囲外にアクセスしてる!
修正.再度リサブミットorz
てか,この問題は自信ないなぁ…,とりあえず,HARD見て無理そうなら見直しするとして,HARDを見てみる.

HARD

次のゲームを行うとき,プレイヤーが絶対勝てないようにするためには,ゲームマスターは最小で何色使えば良いかを求める問題.
ゲームマスターは最初に,ABCDのみからなる長さk (30以下) の文字列に対応する色をすべて決める.
プレイヤーは1つの文字列を選び,最初に選んだ文字列と違う文字列で最初と同じ色に出来れば勝ち.できる操作は以下の通り.
 1. 隣接する2文字を入れ替える
 2. 部分文字列としてbefore[k]を含んでいるなら,その部分をafter[k]に置き換える
before[k]とafter[k]の長さは同じで,この文字列は入力で与えられ,ゲームマスターが自由に決めることはできない.
beforeとafterの要素数は50以下.

さて,問題文の意味が分かりにくいぞ.
なんとなく理解した.
隣接文字を入れ替えることができるのだから,何が何文字あるかだけを考えれば良い.
状態数は30^4ぐらい.
それをどれに移動できるか全部グラフを作る.
枝の数が30^4 * 30^4のサイズになる….
いや,状態数はそもそも30^3だよね.文字列の長さがちょうどkじゃないといけないから.もっと少ない.
なんとかなるのでは.
グラフ作ってどうするの?
とりあえず,強連結成分分解はしたいよね….
あれ,で,後DAGになれば,単なるDPなのでは….
いけるじゃん.
行ける…けど,結構実装重いし,MEDIUMで時間使いまくってあんまり時間ないぞ?
諦めずに,書けるところまで書く!
書く.
書く.
デバッグ.
書く.
書く.
デバッグ.
書く.
書く.
書けたー.残り5秒.サブミットーーー.

Challenge

550は簡単な訳ない.みんなできてないに違いない.サンプルも弱いし.
ランダムで爆撃準備OK.
開く! 何この簡単なコード.Greedyっぽい? こんなの通るわけ無いじゃん,攻撃! 失敗orz
なんだと….
てか,DPほとんどいないぞ? Greedyばっかだぞ?
え,Greedyでいけるのか….
結構上位陣もGreedyだし,いけるらしい…?
後は怖くなって何もできず.GreedyはGreedyで結構落ちてたけど落とし所がわからなかった.

System tests

自信なかったMEDIUM通る.
終了直前提出のHARD落ちる.
HARDはDPでメモ用の配列用意してたのに,メモしてなかった.
メモしたら通った.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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