Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2009年11月26日01時から.

Assigment

普通っぽい部屋かな.
問題が250, 450, 1000の変則セット.
1000にじっくり時間をかけれそうなセットだ.

EASY

あからさまにBFSしてください,という問題….
実装あるのみ.サブミット.

MEDIUM

適当に使えるコスト列挙してDPにしか見えない.
瞬殺できるだろー.
平面グラフという条件を忘れていて,普通にエッジの数はn*(n-1)/2以下としてサブミットしてしまった.
平面グラフだった枝の数の最大値っていくらだ?
適当に絵を書いて考えてみる….
n=5で考えて,3n-6っぽい気がする….
n=4でもOK.n=6だと…自信ないけどあってるような….
3n-6でいいや,サブミット.

HARD

うーん…?
取り敢えず,ラッキーナンバーを列挙してみる.
これからどうするんだろう….
取り敢えず,ラッキーナンバーの中から,他の物の倍数になっているのは除外してみる.
でも,包除原理すると計算量2^1000を楽に越えるぞ.
いやいや,違う,数個使ったらB超えちゃうから,殆ど使えなくて,包除原理しても大した計算量にはならないはず!
書いてみた.よゆーで間に合う.サブミット.

MEDIUM

他にも完全グラフでやってる人いるから知れないからチャレンジケース作っておこう.
…あれ,挙動がおかしい….
条件で3*i-6と書くべきを3*n-6と書いてるorz
再々サブミット.最低点の135点….
完全グラフだと思ったときに間違うテストケースとして385をゲット.

ご飯

コーディング時間は後15分.
おなか減ったのでご飯食べよう.もぐもぐ.

Challenge

MEDIUMを片っ端から開く.
結構,使える枝の数の式間違えている人がいるぞー?
でも,もっと使えないと勘違いしてる人が多い…,そりゃそうだ.
そんなテストケース作ってねー….
急いで作る.206とか360とかでいけるのか?
とか思ってたうちに他の人に全部落とされちゃった….
ノード数が2のとき,例外処理してて枝数0を忘れている人がいたのでそれだけつつく.

System Tests

HARD落ちた….あれ?
MEDIUM連敗記録は脱出したけど,いつもより駄目な感じな結果.MEDIUM最低点だし.

追記 2009-11-26 03:40

HARD落ちた元凶はラッキーナンバーのリストの最後に100000000000LLを追加したこと.
GCDとれば,普通にカウントされるぐらいに小さかった….
通ってればHARD最速だったのになぁ…,とかまぁそういうのは良くありすぎるので,通すことが難しいのがよくわかる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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