Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年03月07日21時から2時間,4問.
某所のホテルから参加.
一応ノートPC,キーボード,マウス,ヘッドフォンは持ってきた.
Codeforcesがどんな感じなのかわからないので,取り敢えず参加してみたって感じで.

Codeforcesに関して

Codeforcesは順位付けの方法がICPC形式のプログラミングコンテスト.
ただし,実行時間の計測はテストケース1つごとに行うTopCoder方式で厳密.
TopCoderと同じような感じで,毎回の結果を基にRatingがつけられる.
現在β.

A. Shortest path of the king

8*8のチェス盤のある場所からある場所に,最小ターンでkingが移動する方法を求める問題.

なんというか,向かっていくだけ.
書いた.Accept.

C. Tic-tac-toe

Tic-tac-toe (3×3の升目に○か×を書いて3目並べするあれ)の盤面が与えられる.
それが,
 絶対にありえない盤面
 次のターンが先手
 次のターンが後手
 ちょうど先手が勝ったところ
 ちょうど後手が勝ったところ
 ちょうど引き分けになったところ
のどれかを判定する問題.

あー,これはたぶんアドホックにやるとミスる問題だ.
というか,前アドホックにやってミスりまくった問題だ.Waterlooの問題だったか.(その問題は盤面のサイズの最大値が1000*1000ぐらいだった気がする)
9マスしかないので,状態数は高々3^9なので,全パターン,シミュレーションすればよい.
書いた.
サンプルが通らん…,illegalになる.
10分ぐらい悩む.
ぬお,これ,インプット,アルファベット大文字のOじゃなくて,数字の0じゃねぇかorz
サンプル通る.送る.Wrong Answer.
+1じゃねぇ,+2だよとか,しょうもないミスを直してAccept.

B. Lorry

船が100000個以下ある.
それぞれの船のコストは1か2で,能力値が1以上10000以下.
合計コストがv以下で,合計能力値が最大になる組み合わせを1つ求める問題.

仕方ないから,頑張って解読する….
ずいぶんかかってようやく問題理解.
尺取メソッド…?
で,いいよね,む,ちょっと違うか?
最初にコスト1のとコスト2のを能力順に別々にソートしておいて,
最初は,コスト2のを詰め込めるだけ詰め込んでおいて,後はコスト2のを1つずつ減らしながらコスト1のを2個ずつ付け加えて,最大値を取る.
書いた.送る.Wrong Answer.(テストケース9で)
むむ…,これって,結果はソートして出さないと駄目なのかな…,そうしてみよう.
送信.Wrong Answer.(テストケース2で)
は?
何でテストケース2で躓いているんだ….
ソートした出力と,ソートしてない出力の一部,両方出してたorz
必要ないの消す.
送信.Wrong Answer.(テストケース9で)
やっぱり関係ないのかな….
10分ぐらい悩む.
これ,よく見たら,船の数10^5まであるじゃねぇか…,勝手に10^4だと脳内変換されてた.
配列10^4しか確保してないよ…,範囲外にアクセスしてるよ….
修正.送ろうとしたらマウス暴発で2連打.2個送られた….(マウス買い替え時かも)
これでWrong Answerとかだと,ペナルティ2倍.
Acceptだった.

D. Least cost bracket sequence

 ()?
の3文字からなる50000文字以下の文字列が与えられる.
各?を(に置き換えるコストと,)に置き換えるコストが与えられる.
()だけで括弧の対応付けが取れる文字列に変換するための最小コストとその変換後の文字列を1つ求める問題.

DPだとO(文字数^2)でアウトだよなぁ…,まぁそんなにやさしいわけがない.
でも,DPでちょっと工夫すれば状態数が減ったり…しなさそう.
悩む.
左からなぞって,)→(に変換するコストの最小値をsegment tree (というかRMQ) を使って簡単に計算しておけるようにすればgreedyにいけるんじゃないか?
いやいや,(→)の変換も考えないといけないし,それは簡単じゃない….
適当にローカルサーチっぽく…とか謎なことを色々考えたけど何も思いつかないまま終了.

Result

Ratingは一応初期値よりは上がったみたいだけど酷い結果だった….

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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