Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年01月13日11時02分から.

Assignment

300-450-1000の変則セット.
チャレンジの神様などと一緒の部屋.

EASY

N個 (10^6以下) の石が一直線に並んでいる.
左からM番目の石のみ白くて,他は黒い.
2人でゲームをする.順番にターンが回ってくる.
毎ターン,白い石を含むように連続するK個の石を選び,順番をひっくり返し,白い石を左からL番目に移動した人の勝ち.
先手必勝か,後手必勝か,永遠に長引かせられるか,を判定する問題.

状態数が100万しかないし普通にDPすれば良いのでは!
…,いや,各ノードからの枝数もO(100万)ぐらいあるし,無理っぽ.
そもそも引き分けにできるとかそういうのでループするし….
!!
これ,後手は絶対ループに持ち込める.すべての手は可逆だから.
ってことで,1手で勝てるなら先手必勝,そうでなければ引き分け.
いや,なんか,サンプルに後手必勝とかあるんですけど….
ああ,そうか,どんな先手の手に対しても.その後,後手が1手で勝てちゃうことがあるのか.
ってか,このサンプル弱くないか?
基本的に最初にある白い石の場所が端ばっかり.先手の手が1手に限られてる場合が殆ど.
まぁ,書く.
….
if文の条件が面倒…,というか間違えそうで怖い.等号がいるか要らないかとか慎重に検証しながら書く.
書けた.サンプル通った.サブミット.慎重になったせいか遅い….でも間違えるよりマシ.
450は瞬殺できる可能性が高いし,さらに1文ずつ見直してから次の問題へ.

MEDIUM

LEN文字 (K+1以上50以下) の文字列が与えられる.
各文字は,未確定(0)か,数字の1~Kのどれか.(Kは7以下)
未確定の文字を1~Kのどれかに置き換えて,最も近くにある同じ文字間の距離を最大化したい.
最大値を求める問題.

とりあえず制約を読む.
Kが小さい.K!の全探索+アルファとかか何かか?
問題を読む.
うーん…,何か違う….
Greedyか何かでできるんだろうか….
わからない.
DPするとすれば….
各文字が前出てきた場所を覚えておけば状態数50 * 50^7でできる…,厳しい.
えー.
あ,答えの最大値はKだよね.
だから,K以上前に現れたものはKぐらい前に現れたものと同じと思っても問題ない.
状態数 LEN * K^K か….これいくら?
 50 * 7^7 = 41,177,150.
厳しい?いやTopCoderさんならやってくれる.
計算量は
 50 * 7^7 * 7 * 7 = 2,017,680,350
…,無理じゃん.
いや,頑張れば7は1個消せて
 50 * 7^7 * 7 = 288,240,050
かな.
えーーーー.
でも,めんどうだし,450でこんな難しいはずはない….
サマリーを見ると…,自分は300で遅れてる方なのに,みんな提出してない.
やっぱりこれ難しいんだ.
そうと決まったら書く!
とりあえず,書きやすい50 * 7^7 * 7 * 7 = 2,017,680,350で書く.
K=6なら余裕で間に合うけど,K=7で明らかに死亡.
1個ループを削って,50 * 7^7 * 7 = 288,240,050に直す.
K=7で,Arenaで6秒ぐらいかかる様子….えええええええ.
どうしよう….3倍の最適化は厳しい….
….
試行錯誤の末,単に,たどり着けてない状態は処理しないようにしたら0.4秒程度で終わるようになった.
え.なんか怪しいけど大丈夫かな….
そうか,前にこの数字が出てきた場所,ってのは同じ場所にならないから状態数はK^Kじゃなくて全然もっと少ないはず.(K!+アルファぐらい)
サブミット.
(システムテストで最悪ケースで0.5~0.6秒程度でした)

HARD

100*100以下のグリッドが与えられる.使えるマスと使えないマスが指定される.
使えるマスのみからなる,空でなく,連結で凸な一連のマスを選ぶ方法は何通りあるかを mod 1000000007 で求める問題.
凸とは,2つの同じ行または列のセルが含まれてるなら,その間のセルも含まれてなければならない,という条件.

これもDPな気がする.
前の行に使ったセルの左端,右端はとりあえず状態に含まれる.
あと,左端は単調減少→単調増加,右端は逆,とならなければ行けないので,極地を超えたかどうかのフラグを用意する.
状態数はO(4*50^3)で,状態の更新に50^2かかる….
微妙だけど,頑張れば通るような気がしないでもない感じ.
違った.サイズの最大は100ではないか!
状態数はO(4*100^3)で,状態の更新に100^2かかる…から…,O(100^5)….
無理だ.
うーん,取り敢えず書きながら考えよう….
って思ってたら,書くだけでも時間なかった.

Challenge

450でTLE狙い.か,250で条件ミス狙いか.
250を見る.
なんか,条件がいろいろ怪しい人が1人いたので落とす.
後は見てるだけで終了.

System tests

結構自信なかったけど300も450も通った.一安心.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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