2017-07

Latest Entries

スポンサーサイト

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

SRM 409 DIV 2

練習.

250: Stick


64 cm の棒があり,x cm 分を得るために以下の操作を繰り返す.
・持っている棒の長さの和が x 以下であればやめる.
・最短の棒を 2 つに分ける.
・分けた片方を捨てても和が x 以上であれば分けた片方捨てる.
操作が終了したときに持っている棒の本数を求める.

2 進法で大きい桁から作られていく.立っている bit を数えればよい.

500: OrderedSuperString


n 個の文字列 words[i] が与えられる.文字列 X であって,n 個の単調増加な index x[i] で X[x[i] .. $] が words[i] を prefix として持つようなものが存在するもののうち,最短のものの長さを求める.

words[i] を i の順に貪欲に繋げていく.繋げたところの index を持っていけばよい.

DIV 1 250 と共通.

1000: TeleportsNetwork


平面上の N 個の点が与えられる.点 0 以外の各点について,点 0 により近い点のうち最も近くにある点と辺を結ぶ (タイブレークあり).すると木ができるが,この木に高々 teleportCount 個のテレポートを配置し,点 0 へ向かうために通る辺の個数の最大値を最小化する.
N <= 50,teleportCount <= 4.

言われたとおりに木を作成し,Floyd-Warshall を回して O(N ^ (teleportCount + 1)).

最初,答の二分探索と DP の方が楽かと思ったが,根の方向に進むケースを見逃していてできていなかった.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/28-6c0721a7

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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