Entries

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

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

TJU 3184 - Government Help (この記事を編集する[管理者用])

CTU Open 2008 問題H
[ Link ]

[ 問題概要 ]
n個の与えられた正整数を順番に2人に分け与えていく.
与える順番は自由,どちらに何個与えるかも自由.
与えた瞬間瞬間に,2人に与えた数字の和の差を考えて,その最大値を最小化したい.

どんな順番で誰に分け与えると良いかを出力する問題.
答えが複数ある場合は,どれを出力しても良い.

正整数は100000以上199999以下.

[ 解法 ]
正整数の最小値と最大値は2倍以上差がつかないのがポイント.
与えられた数字のうち,最小のものが和の最大値とすることができる.
交互に2人に与える.最初に最小のものを与えて,後は大きい順に与える.
図を描くと振動していく様子がわかるはず.

TJU 3185 - Tree Insertions (この記事を編集する[管理者用])

CTU Open 2008 問題I
[ Link ]

[ 問題概要 ]
数列が与えられるので,数列から二分探索木を作る.
では,そのような二分探索木となるような数列は何通りあるかを求める問題.

[ 解法 ]
多倍長 + DP + 二項係数.
先頭の数字を見て,それより小さいのとそうでないのでグループ分けする.
すると左右の小問題に帰着される.後は左右はどっちが先に来ても良いので二項係数をかける.

USACO 2008 NOVEMBER (この記事を編集する[管理者用])

GOLD 4問,SILVER 3問,BRONZE 3問.
Link先はTJU.
[ Link ]

GOLD 1問目: Mixed Up Cows
16匹以下の牛たちのIDが与えられるので,牛を並び替えて,隣会う牛のIDの差がkより大きくなるような並べ方は何通りあるか求める問題.
DPするだけ.

GOLD 2問目: Cheering Up the Cows
連結な無向グラフが与えられる.
枝を移動するのにかかる時間,ノードに訪れるたびにすごさなければいけない時間が与えられる.
目的は,枝をいくつか切り捨てて,連結な木を作って,何処か始点を決めて,その木にそって全部のノードを最低1回以上訪れて始点に戻る時間を最小化したい.

残された枝は2回ずつ通って,基本的にノードには次数だけ訪れることになる.
ただし,始点のみ1回訪れる回数が大きい.
なので,枝の重みを2倍して,繋がっている2つのノードの時間を足してMSTを求める.
後は,ノードの時間が最小のを1個分足したら答え.

GOLD 3問目: Light Switching
一直線に並んだ100000個以下のスイッチがある.最初は全部OFF.
100000個以下の操作を行う問題.
操作は,
 1) ある区間のスイッチを全部反転させる
 2) ある区間のONのスイッチの数を求める
の2つ.

segment tree.

GOLD 4問目: Toys
D日間に渡って,各日に必要なおもちゃの数が与えられる.
おもちゃは新しく買っても良いけど,消毒することで使いまわせる.
消毒業者が2つあってそれぞれ1つ消毒するのに必要なコストと,消毒に必要な日数が与えられる.(何個でも同時進行で消毒できる).
費用を最小化する問題.

TJUでWAばっかりもらうので,USACOにID登録してサブミットしてみたらUSACOでは通った.
おもちゃを何個買うかを決めてしまった場合は,適当にgreedyにやればO(D)で最小コストが求まる(単純でもないのだけど…).
おもちゃを何個買うかというのは三分探索したら良さそうな気がしたのでそうしてみた.

SILVER 1問目: Buying Hay
x_i個でy_i円みたいな感じで商品が買えるので,H個以上買うために必要な最小金額を求める問題.
典型的DP.

SILVER 2問目: Guarding the Farm
2次元グリッドで各座標の標高が与えられるので,hilltopの個数を求める問題.
hilltopは連結なグリッドの集合で,まわりは自分より低い.

座標を標高ごとにソートして高いほうからなぞっていく.
まだ塗りつぶされていないなら,答えに1を加えて,自分から標高が同じか低くなる連結な部分を塗りつぶしていく.

SILVER 3問目: Time Management
各仕事にかかる時間と,その仕事を仕上げなければいけない時間が与えられるので,いつから仕事に取り掛かればよいか,もっとも遅い時間を求める問題.

デッドラインが速い順に仕事をすれば良いので,ソートして,後は必要な時間を適当に計算するだけ.

BRONZE 1問目: Switching Lights
GOLD 3問目の制約が緩くなったもの.
単純にシミュレーションするだけで良い.

BRONZE 2問目: Guarding the Farm
SILVER 3問目の制約が緩くなったもの.
かといって,SILVER 3問目より単純な解法が良く分からない….

BRONZE 3問目: Going Once, Going Twice, Gone!
商品を持っている数と,その商品を買いたい人のリストが与えられる.
買いたい人は買うために幾らまでお金を出すかが与えられる.
商品の価格をうまく設定して,得られるお金を最大化する問題.
得られるお金が等しいなら,できるだけ商品の価格を安くする.
買いたい人の数は1000人以下.

買いたい人リストをソートして,全部調べるだけ.

CUET Easy Contest (この記事を編集する[管理者用])

今更書くほどのことじゃなかった気がするけども….
TJU Online Judgeで日本時間で2008年06月01日20時から4時間で行われたコンテスト.

ref: http://acm.tju.edu.cn/toj/contest/contest96.html

総評としては,名前通り簡単な問題ばっかりのコンテスト.
問題文読んで実装するのみ,で殆ど終わり.
ただ,問題の文章というか内容自体は,まぁまぁ面白いと思ったものも.BとかIとか.
というか,Iの問題文は読んで感心した.

計 11問
参加人数: 41人
11 solved: 3人
10 solved: 3人

Appendix

Recent Articles

ブログ内検索

Ads


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