2011-06

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1045: HangOver


台の上に,台からはみ出すようにカードを置いていく.すると n 枚のカードでは最大 1/2 + 1/3 + ... + 1/(n+1) はみ出る.長さ c はみ出すには何枚のカードが要るか求める.
0.01 <= c <= 5.20

調和級数の部分和を作って lower_bound.サンプルに c = 5.19 があり,たとえば n <= 1,000 で余裕であることがわかる.

ZOJ 1047: Image Perimeters


グリッドは X と . からなる.斜めで接する X を繋がっているとして,X たちの連結成分を考える.ある X が指定されるので,それを含む連結成分の周の長さを求める.穴が空いていたりはしない.
(縦), (横) <= 20.

同じ連結成分の X について,4 方向のうち X でない個数を足していけばよい.

ZOJ 1048: Financial Management


12 個の金額が小数第 2 位まで与えられるので,それらの平均を求める.

誤差を気にせずに通った.

ZOJ 1049: I Think I Need a Houseboat


(0, 0) を中心として y >= 0 の領域に収まる半円が,1 年に面積 50 ずつ増える.与えられた点 (x, y) が半円に入るのは何年目か求める.境界になるような入力は来ない.

ceil(π * (x^2 + y^2) / 2 / 50) が答.

ZOJ 1051: A New Growth Industry


20 * 20 でセルオートマトンをシミュレーションする.状態は 4 通り,遷移時は周囲 4 マスに依存.

ループ回数の上限が書いていないが愚直にやって通った.

ZOJ 1053: FDNY to the Rescue!


N 個の交差点があり,道路の様子が隣接行列で与えられる (有向重み付き).目的地が 1 つあり,出発地の候補がいくつかあるので,所要時間順にソートし,出発地・目的地・所要時間・経路の情報を出力する.経路は最短時間なら任意のものでよい.
N <= 20.

Floyd-Warshall して経路復元.経由点を覚えておいて再帰的に呼び出した.

出発地と目的位が同じときに経路に 2 回出力してしまった.また,テストケース間の空行を忘れていた.

ZOJ 1056: The Worm Turns


20 ブロックからなる虫が 50 * 50 上を動く.動きは,頭が指定された方向に進み,続くブロックたちが追従する.
・自分に重なる動きをしたら何番目の動きかとともに報告する.ただし尻尾が消えるところに頭が動くのはよい.
・盤からはみ出たら何番目の動きかとともに報告する.
以上にひっかからずに最後までいったら報告する.
(動きの数) <= 100.

現在虫がいるセルたちを,deque と bool 2 次元配列で保持した.

ZOJ 1057: Undercut


2 人が 1 枚ずつ数が書かれたカードを出し合うゲーム.差が 2 以上なら大きい方が大きい数の得点,差が 1 なら小さい方が 2 枚の和の得点を得る.ただし 1 と 2 なら 1 の人に 6 点.2 人の得点を求める.
(ターン数) <= 5.

swap したことを覚えつつの swap を用いて場合分けを減らした.

ZOJ 1058: Currency Exchange


レートの表と変えた貨幣の順が与えれるので,両替をシミュレーションする.両替するたびに 0.01 単位に四捨五入される.

100 倍して floor(x + 0.5) のような扱いをした.誤差を気にせずに通った.

ZOJ 1060: Sorting It All Out


最初の n 個のアルファベットで表される異なる実数について,"A・n 個の順序が決定したら何番目かと結果を報告する.
・矛盾したら何番目かとともに報告する.
最後までいずれも起こらなかったらそれを報告する.
2 <= n <= 26.

毎回トポロジカルソートできる.失敗したら矛盾.ソートした列について順番が一意である条件は,任意の j に対して j 番目の頂点から j+1 番目の頂点に直接辺があること.

最初一意性に悩み,辺に -1 して全頂点間最短路を更新していくコードとともに書いていた (更新は O(n^2) でできる).

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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