Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年03月21日01時から2時間,5問.

A. Chat Servers Outgoing Traffic

チャットのログが与えられる.
発言すると,その発言はログインしているすべての人に送られる.
入室退室では,データの転送量はかからないとして,いくらのデータが送られたか求める問題.
1文字1バイト.

誰々が入室したとか書いてあるけど,中にいる人数だけ覚えておけばよいよね.
適当に書く.サブミット.通った.

B. Center Alignment

与えられた文字列を枠で囲んでセンタリングする問題.
枠は最小.
センタリングするとき,左右のスペースが等しく出来ない場合は,1つ余分に左に振り分けて,次に同じようなケースが登場したら右に振り分ける,と交互にやる.

書くだけ書くだけ.
書いた.サブミット,WA.
あれ,よくみたらサンプル2つ目なんか合ってないな….
おおぅ,左右に順番に振り分けるとか読み飛ばしてたよ….
サブミット.WA.
左右に振り分け方,行ごとに変えてた….等間隔にできないと振り分け方を変えるのだよ….
サブミット.WA.
むぅ…?
枠は最小でないといけない,1つは正の長さの行があるって言ってたから,最初と最後に空行があれば消してたんだけど,消さないようにしてみる.
Accept….そういうことだったのか!

C. Longest Regular Bracket Sequence

1000000文字以下の()からなる文字列が与えられる.
対応付けられた括弧になる最も長い部分文字列の長さと,その数を求める問題.

(が現れると+1して,)が現れると-1して,)が現れたとき,自分の値を下回らないように辿り着ける自分と同じ値の(までの距離の最大値を取ればいい.
Segment treeでMRQすれば良いんじゃね?
適当に書く.
サンプルは通ったが.取り敢えずサブミットしてみよう.WA.
適当に色々試すとダメっぽいことが発覚.
ちょっと修正してサブミット.WA.
ケアレスミスあったので修正してサブミット.WA.
なんか,泥沼.
もうちょっと良く考えようよ.頭の中整理して!
取り敢えず,今まで書いてたコードは削除.
うーん,segment treeとか要らなくないか?
普通になぞるだけでできそうだぞ.
自分の深さから)が来たら,出現した記憶をリセットして,自分と同じ深さが以前出現した場所までの距離の最大値をとれば良い.
書いた.サブミット.Accept.

D. Follow Traffic Rules

車の最大スピード,加速度=減速度,進みたい距離,ある点とそこでの最大速度が与えられるので,進みたい距離を進むのに必要な最小時間を求める問題.

スタート→点→残りと2段階に分けて考えれば良い.
スタートから点にたどり着くときにどれだけ加速して良いかは2分探索で求めよう.
がりがり.
後は,点にたどり着いた時の速度を用いて残りの距離を走るのに必要な時間は….
場合分けとか色々面倒な気がするので,これも2分探索でいいや.
書いた.サンプルは1発で通った.
まあ,とりあえずサブミットしてみようよ.Accept.

E. Bindian Signalizing

円上に山が1000000個以下ある.それぞれの山の高さが与えられる.
2つの山が互いに見えるとは,円周に沿って,2つの山の小さい方より高い山が間にないと見える.
互いに見える山のペアは何個ありますか?

うーん?
2つの山が与えられて,その間が見えるかどうかはsegment treeでMRQすれば良い.
が,2つの山の選び方が多すぎてどうにもならない.
あー,取り敢えず,一番大きな山を見つけて,そこで区切ると良さそうな気がする.
そうすると,円形は考えなくて良くて,区間にできる.
区間でも同じで,一番大きい山を見つけてそれで区切って再帰的にやれば良いのではないか!
で,見ることのできるペアは,区間に分けたときの両端(区間の外)と,その区間で最も高い山(複数あるかもしれない)の間は見えるので,n*(n-1)/2とか足していけばよい.
書いた.MLE.
むー,いちいちvector<int>(をC言語で実装した自分のライブラリ)とか使ってるとメモリ足りないのかな….
普通に配列で確保して,上手く使いまわすようにしよう.
サブミット.RE.
ほぇ….あ,再帰の深さが深すぎる気がする.最大で深さ1000000.
スタック使って書きなおす.
サブミット.RE.
ほぇ….どこか配列溢れているのかな…?
適当に配列のサイズを増やす.サブミット.RE.
多分最悪ケースは1 2 3 ... 1000000だよな,作って入れてみる.普通に答え返ってくる.
あれぇ….ランダムでテストケースを作る.segment fault来た.残り15分ぐらい.
何がおかしいんだ?
ミス発見…,同じ区間で2つ以上の山が最大の高さのときに,無限ループで,どんどん配列の先にアクセスしている.
vector<int>は無限に要素をpush_backし続けるコードになっていた.
全部これが原因じゃないかorz
1文字直す.サブミット.Accept.

Result

結果は全完の中では圧倒的大差で最下位.
ICPC形式のコンテストだと,正解数のみしか気にしなくて,取り敢えずサブミットしてしまえ,って感じなのだけど,いくらなんでも酷過ぎるなぁ.
一度しみ込んだ癖は直らないと思うので,取り敢えずサブミットしてしまえで通るようになりたい…,ってのは間違った考え方かなorz
レートはアップ.ようやく黄色くなったよ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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