Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年05月27日00時02分から.
サーバ不調のため途中からコンパイルできなくなり,ノーコンテスト.

Assignment

久しぶりに,青~黄色下位が多い気がする部屋.
それよりTomyam先生のデビュー戦.

EASY

 p/2^0, p/2^1, ..., p/2^k
が全部素数のとき,自然数pにスコアkをつける.
D以上のスコアを持つ,N以下で最も大きい自然数を求める問題.
存在しないなら,-1を返す.
Nは10^7以下,Dは10以下.

前回(ニコ生Open 第2回)の反省を踏まえて,じっくりゆっくりやる.
エラトステネスで素数求めて,DPで全部のスコアを計算する.
エラトステネスの配列をcharで,DPをintで持てば50MBなのでメモリは大丈夫.
書いた.0.5秒とかかかるのか,ローカルだと一瞬なんだけどな,でもそれが最悪ケースだから問題ない.サブミット.
(なんか,サーバーの実行時間も不安定だった模様)
dが7以上で-1なのか…,まぁ,そんなもんかも.

MEDIUM

ノード数25以下の有向グラフが与えられるので,ノード0からn-1に行く以下の制約を満たす最小距離を求める問題.
ただし,自分自身に枝をはってるかもしれない.
制約は,移動距離がT1, T2, T3という枝を通ったのであれば,
 T1, T2, T3, T1+T2, T2+T3, T1+T2+T3
のどれも13の倍数ではない.

問題文読む.
問題文中の例が意味分からん,13は13の倍数じゃないのか??
サンプル見ると,最初のサンプルで13は駄目だよって書いてあるぞ,どういうことぞ???
つうか,最初のサンプルおかしくね?
なんで最小パス13なんだ?距離27以上の枝しかねぇぞ??
なんだこれ???
小文字と大文字の距離が逆なの?
逆っぽい.
なんか,こんなくだらないことで悩んでないで,取り敢えず書こう.
ていうか,問題読解にだいぶ時間かかってるんだけど,これ自分のせいじゃないよな….
方針は簡単.
今までの距離の部分和%13をどれだけ取っているか2^13倍にノードを拡張してダイクストラでしょ.
細かいことは考えてないけど,書けばわかるよ.がりがり….
あー,これ条件から,ビット立てて行く時,新しく絶対ビット立てれないと13の倍数になって駄目で,1のビットは1つずつ増えていく.
ループないよー,ダイクストラじゃなくてDPでいいじゃん.
そういうのが見えてないのが頭弱い.無駄に実装量増やしているだけ.
まぁ,書き始めたからこのままいく,そっちの方が速い.
サンプル通った.提出.

HARD

3次元上の有向線分が50個以下与えられる.
平行移動して,1本の自分と交わらない線分にしたとき,始点と終点の距離の最大値を求める問題.

どゆこと?
不可能な場合とか書いてないけど,絶対に作れるのか?
うーん.
てか,これ,2次元版の問題PKUかどっかになかったっけ…,なんか結構感動した解法だった気がするが…,憶えてないんじゃ意味ねぇな….
うーん.
不可能な場合はない,作れる.
というか,多分,x[i], y[i], z[i]をマイナス1倍しても良い,2^50通り試して,その中で最も
 xの和^2 + yの和^2 + zの和^2
が大きくなるのを求める問題と同値.
ちょっと自信ないけどたぶんそう.
さて,どうするんだ….
幾何的に考えるのか,それとも,単純に数字として扱った方が楽なのか….
800点台とかで提出してるな,なんだと,簡単なのか?
わからん.
でも,2^50通りしか考えれないし,リスタート+ランダム局所探索で通っちゃったりするんじゃない?
そう思ったら通る気がしてきたぞ?
いまから,一瞬で局所探索書いて,サブミットして通したら上位狙える.
いいや,やっちゃえ.
コンパイルできないんですけど….
でも,チャットみても,皆,コンパイルできねーとか言ってないな…,リログするか.
リログした,チャットが全く進んでない件.
twitter見ると皆同じ症状.
ノーゲームかなぁ.
てか,せっかくのTomyam先生のデビュー戦なのに….

Challenge

そんなものはなかった.

System tests

後でプラクティスでシステムテスト試すとEasy, Medium, Hard全部通った.
あー,惜しかったなぁ….
偉い人の「500はダイクストラだとTLE疑惑」で戦々恐々としてたけど,最悪ケースで7msだった.
てか,Hard,やっぱりランダムで通るんかい.まぁ,想定解法ではないはずなのでのちのち勉強.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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