2017-05

Latest Entries

スポンサーサイト

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

SRM 410 DIV 2

練習.

250: ContiguousCacheEasy


n バイトのメモリがある.一度に k バイトキャッシュでき,最初 [0, k - 1] を持っている.addresses[i] に順にアクセスする.このとき新たなキャッシュが必要になったら現在の場所に近い場所を持ってくる.新しく読み込むメモリの合計を求める.

各回に読み込むのは min{(移動量), k}.

500: AddElectricalWires


N 個のノードがあり,その wire での接続関係 (無向単純グラフ) が隣接行列で与えられる.いくつかのノードは main grid に直接繋がっていて,main grid に繋がっている 2 ノードは wire で直接にも間接にも繋がってはいない.この条件を保ちつつ wire を増やすとき最大何本増やせるか.
N <= 50.

main grid に直接繋がっているノードを含む連結成分のサイズを列挙し,それぞれを完全グラフにできるので増やせる辺がわかる.main grid に間接的にも繋がっていないノードたちは最大の連結成分につ繋げるのがよい (nC2 が凸なので).

1000: ClosestRegex


文字列 text と正規表現 regex が与えられる.ここで regex が含む特殊な文字は '*' のみであり,すなわち regex の各単位は「文字 X 1 個にマッチ」「文字 X 0 個以上にマッチ」のいずれかである.text の何文字かを書き換えて regex にマッチするようにしたい.書き換える文字数を最小化した上で,得られる辞書順最小の文字列を求める.
|text| <= 50,|regex| <= 50.

text[x .. $] を regex[y .. $] にマッチさせるための,最小書き換え数とできる辞書順最小の文字列の pair を求めていく.regex[y + 1] == '*' ならば y を 2 つ進められる.text[x] を必要ならば regex[y] に書き換え,次は (x + 1, y) あるいは (x + 1, y + 1) を見ることになる.string を比較するので計算量は O(|text|^2 |regex|).
計算量に余裕があり string を比較できるので,最小値だけ求めてから復元,とするより楽.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/37-ebb5b121

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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