Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年02月01日21時02分から.

Assignment

赤が自分しかいない部屋.
250-500-950の少し変則セット.

EASY

50*50以下のグリッドが与えられる.各グリッドは赤,緑,青,白のどれか.
1回で,青は横幅1マスで縦にいくらでも長く塗れる.
1回で,赤は縦幅1マスで横にいくらでも長く塗れる.
緑は赤青両方で塗られたマス.
真っ白の盤面から,与えられたグリッドを作るための最小塗り回数を求める問題.

これは実際に塗るだけ…,というか,線分がいくつあるか,赤青独立に数えるだけ.
書く.サンプル通る.提出.

MEDIUM

1次元上を左右どちらにかわからないが速度1で動いている粒子がある.
最初N個 (50以下) の粒子の初期位置が与えられる.
その後,いくらか正の時間が経った後 (たった時間は未知) のM個 (N以上) の粒子の位置が与えられる.
それは,N個の粒子に加え,M-N個の粒子を加えている.
さて,最初のN個の粒子と,M個の粒子の対応関係としてvalidなものはいくつあるか,を求める問題.
最初,最後には,同じ位置には粒子はないとする.

えっと.
たった時間が決まれば,2部マッチングの数.
たった時間は,それぞれの粒子の位置の差で,50*50通り試しても問題ない気がする.(実は50通りで十分なことに気づいてない)
2部マッチングの数って,簡単に求まるものだっけ? そうじゃない気がするな.
えっと…,N個の粒子それぞれに対応できるのは,正方向,負方向に動いた場所で,たかだか2個までしか対応しない.
だから,グラフの次数は最大で2.これはキーポイントっぽい.
うーん….
わからない.
….
……….
……………….
やばい,時間だいぶ経って,提出してる人が結構な数いるのに,全く方針すら浮かばないぞ.
てか,これって,実は全探索で間に合うんじゃね?
いや,あんまり下手な全探索だとダメだけど…,「賢い全探索」なら間に合う気がする.
 ・対応できる粒子がなくなったものが存在したら打ち切る
 ・1個しか対応できない粒子が1個しか対応できない粒子と対応できるなら即座に対応させる
 ・2個対応できるのがあって,対応先が両方その粒子としか対応できないなら,その粒子を対応済みにしてその後答えを2倍する
みたいな感じ.
最悪ケースでどれとどれを対応させるかで2^50ぐらいはできそうだが,そういうケースは一瞬で終わるはず.
書いた.最悪ケースを入れてみる.2^25が返ってくる.え?
何か間違えたか…,いや,違う,このケースだと2^25でいいんだ….
あれ? ちょっとまてよ….
これ,long longで返す問題だけど,long longになりそうにないぞ??
罠か!
最悪ケースが何かはわからないけど,賢くない全探索でも…,いや,それは微妙かなぁ….
とりあえず,サブミット.

HARD

50個以下の文字列が与えられる.始点文字列と終点文字列が与えられる.
ある文字列から別の文字列に移動するコストは,
 移動前の文字列の長さ^2 + 移動後の文字列の長さ^2 - 移動前,移動後の文字列の最長共通プレフィックスの長さ^2
となる.
全部のノードをちょうど1回ずつ通るような,始点文字列から終点文字列まで移動するコストの最小値を求める問題.

ハミルトンパスってなんじゃい? てか,どっちじゃい?
Wikipedia先生教えてー.ノードを全部1回ずつ通るやつか.
うーん…,最小ハミルトンパスって難しいよね? うん,調べた感じNP完全っぽい.
….
全くわからない.
……,はっ.
残り時間僅かで,はたと気づく.
これって基本的に,辞書順でソートして,順番に訪れればいいんだよね?
始点と終点の扱いが問題なのか….
ここまで辿りつくの遅っ.
始点と終点の前後1ノードは全部試して,後は全部順番に訪れることにする.
何も保証はないけど,取り敢えず出してみてもいいかな.
2分で書く.サブミット.
うおおお,ノード数2のとき,次に行くノードの候補がなくて,無限大が返ってくるー.
ノード数が6以下ならnext_permutationで全探索する!
リサブミット.

Challenge

500で賢くない全探索してる人がいるなぁ…,これ落ちるんじゃないかな?
いや,チャレンジ失敗したらでかい位置だぞ,成功してもでかいけど,ちゃんと考えろ.
うーむ,どうだろう,よくわからない.というかお腹痛い.
諦めてトイレ.
トイレで考えてると,2^25通り答えがあって,さらに,毎回50個なぞってたから,どう考えてもTLE.
落ちるじゃん!
と気づいたけど,何もできず.

System tests

HARDは落ちる.ちゃんと考えてないgreedyが通るほど甘くはない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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