2011-06

Latest Entries

スポンサーサイト

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

Codeforces Beta Round #74 Div. 1

C → A → D → B の順で解き,A の Hack と E を並行させた.E が無理そうなので Hack に戻ったところ B のミスに気づき再提出と B の Hack.C が落ちて 6 位.

(追記)
E に rejudge が入りすべて落とされた模様.4 位になっていた.

A: Robbery


n 個の金庫があり,箱 i にダイアモンドが a[i] 個ある.ダイアモンドを 1 つ (箱または手元) から (箱または手元) に移す操作が,1 秒に m 回できる.1 秒ごとに,a[i] + a[i + 1] の値は変化してはならない.k 秒間で最大何個のダイアモンドを手に入れられるか求める.
1 <= n <= 10^4,1 <= m, k <= 10^9,0 <= a[i] <= 10^5.

n が偶数のとき全体の和が不変なので答は 0.n が奇数のとき,(n + 1) / 2 回の操作でダイアモンドを 1 個得られ,a[2j] が 1 ずつ減るので,floor(m / ((n + 1) / 2)) * k と min{ a[2j] } の小さい方まで取れる.

B: Widget Library


Widget,HBox,VBox がある.HBox は x 方向に,VBox は y 方向に他の物たちを詰め込む,物が定義されたり詰め込んだ様子が与えられたり,余白や詰める間隔が変更されたりするので,それぞれの物のサイズを答える.

入力を読むのが面倒.サイズを求めるときはメモ化再帰でよい.

同じものを 2 個ずつ詰め込んでいくとどんどん大きくなり,int だとオーバーフローする.%lld の注意があったのに忘れてしまい再提出.

C: Chip Play


n * m のマスのいくつかに矢印が書かれている.いずれかの矢印から始め,矢印方向で最も近い,まだ乗っていない矢印マスに移動する.移動回数の最大値と最大となるスタート地点の個数を求める.
n * m <= 5,000.

すべてのスタート地点を試してシミュレーション.次の行き先のリンクを次々張り替えていく (Union-Find の経路圧縮のようなもの).全体で O((nm)^2).

行き先を求めるとき set の lower_bound を使ったら TLE した.

D: Space mines


n 個の球があり,球 i には m[j] 本の針が刺さっている.針は球の中心を端点とする線分で,長さは球の半径の 3/2 倍以下.動く球のスタート地点と速度が与えられるので,最初に球か針に当たるまでの時間を求める.ずっと当たらなければそれを指摘.最初は当たっていない.
n <= 100,m[i] <= 100.

針の長さの条件から,最初の接触は球面あるいは針の端点.よって最初に当たる時間の候補はすべて「点 p との距離が d になる時刻」と書けるので,2 次方程式を解いて正の解を見る.

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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