2017-08

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1074: To the Max


N * N に整数が並んでいる.長方形領域 (正の面積) の和の最大値を求める.
N <= 100.

行の範囲を固定すると,部分和を作っていけば max { sum[j] - sum[i] | i < j } = max { sum[j] - min { sum[i] | i < j } } であるから,min も作っていけばよい.
O(N^3).

最初,正である限り足していく尺取,という完全に誤りの方針をとってしまった.

ZOJ 1076: Gene Assembly


区間が n 個与えられ,交わらないように最大個数とりたい.そのときの取り方を区間の位置の昇順で番号で出力せよ.
n < 1000.

終点でソートして貪欲.

ZOJ 1078: Palindrom Numbers


palindrom とは b 進法で書いたときに回文になる整数.n が palindrom となる 2 <= b <= 16 をすべて求める.
n < 50,000.

余りを書き並べて判定した.

解がないときの出力を問題文からコピペしたとき,n の部分を 19 にしたままだった.

ZOJ 1082: Stockbroker Grapevine


人が N 人いて,人 u が噂を聞いたとき何分後に人 v に伝わるかが一部の u, v に対して与えられる.1 人だけに新しい噂を伝えて,全員に伝わるまでの時間を最小化し,誰に伝えるべきかとともに答える.不可能ならそれを指摘.

Floyd-Warshall した.誰に伝えるかは最小を選んだら通った.

ZOJ 1086: Octal Fractions


8 進法の小数 (0 以上 1 以下,小数点以下 k 桁) が与えられるので 10 進法で書く.

多倍長割り算だが,常に小数点位置からなので楽.1 を 8 で割っていき,必要なだけ答に加算足していく.k の上限はないと言われているが O(k^2) で通った.
入力に 1 があり得るかよくわからない問題文だが 1 の位をそのままにすることで対応しておいた.

ZOJ 1088: System Overhead


輪に n 人が並び,「最初の 1 人が消される,次の m - 1 が飛ばされる」を繰り返す.最初 2 番目にいる人が最後まで生き残るための最小の m を求める.
3 <= n < 150.

m を決めたとき誰が残るかは,1 人から順に人数を増やして解いていけば O(n) で求まる.m を順に試して計算させたところ n < 150 では m <= 513 で見つかった.

ZOJ 1089: Lotto


k 個の数が与えれるので,その 6 元部分集合を辞書順ですべて列挙する.
6 < k < 13.

bit の nextCombination を書いた.補集合を回すかつ reverse,で辞書順になる.

適当にやると辞書順にならない.計算量に影響がないので next_permutation を使う方法も.

ZOJ 1090: The Circumference of the Circle


三角形の 3 頂点の座標が与えられるので,外接円の周長を求める.

辺の長さを求めて 4RS = abc を用いた.

ZOJ 1091: Knight Moves


8 * 8 のチェス盤で 2 マスが指定されるので,ナイトの動き何回で辿り着けるか求める.

Floyd-Warshall した.辺を張るときは 8^4 回して距離 √5 で判定してみた.

ZOJ 1092: Arbitrage


n 種類の貨幣があり,両替のレートが与えられる.両替は手数料等なく比例.任意の貨幣からスタート可能で,金を増やせるか否か判定する.
n <= 30.

log をとって Bellman-Ford で正閉路の有無を判定.最初はすべてコスト 0 にして,N 周目で更新があるかないか.

ZOJ 1093: Monkey and Banana


n 種類の直方体がそれぞれたくさんある.直方体は 6 通りのうち好きな向きに使えて,積んでいく.積むときに縦も横も真に短くなければならない.作れる最大の高さを求める.
n <= 30.

6n 個用意して,x 昇順 → y 昇順 でソートしておき,O(n^2) の DP.

x 昇順 → y 降順 でソートすると,1 次元上の RMQ をすれば遷移が O(log n) で計算できて O(n log n) になる.この RMQ は BIT で書ける.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/21-6ab25620

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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