2017-10

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1203: Swordfish


平面上の N 点を結ぶ Euclid 距離での最小全域木を求める.
N <= 100.

Prim 法を用いた.

ZOJ 1205: Martian Addition


20 進法で足し算をする.
(桁数) <= 100.

非負として通った.出力で leading zero を削るとき 0 + 0 に注意.

ZOJ 1206: Win the Bonus


いくつかの数字 3 文字の並びに対して,それを含むことで得られる得点が定まっている.n 個の数字の並びで,得点が最大であるものを求める.複数ある場合は辞書順最小.
n <= 10,000.

得点の情報は 10^3 の配列に入れた.状態 n * 10^2 で最大値を求める DP を後ろから行い,それを用いて復元.

ZOJ 1208: Roll the Die!


さいころの動きをシミュレーションする.最初の位置の上と正面の面が与えられ,これが適切でなければ指摘.動きは平面上で 4 方向のいずれかに転がることの繰り返し.最後の位置の上と正面の面と座標を出力する.
(操作回数) <= 35.

まずさいころを 24 通り生成して初期状態を探す.その後は上方向・右方向に転がす関数で転がす.

ZOJ 1209: April Fool's Joke


時計の短針と長針を入れ替えたらどう読めるかについて解析する.短針から求まる分の読みと長針から求まる分の読みを求め,差が 12 以下なら長針から求まる分の読みを採用する.

言われたものを 1 つずつ求める.0 時が 12 時と表記されるので,内部では 12 を 0 にして処理.

ZOJ 1216: Deck


机から長さ 1 のカードをはみ出させる.n 枚のときの長さを求める.
0 <= n <= 99999.

1/2 + 1/4 + ... + 1/2n の部分和をもっておいてそれを答える.

ZOJ 1218: Ratio


分数が与えられるので,それを近似する分数を求めていく.分母 1 から始め,精度が良くなる最小分母のたびに出力する.差が等しい場合は大きい方とする.
(分子),(分母) <= 5,000.

分母から分子が求まるので,分母をループさせて近くなったかを毎回判定.

ZOJ 1221: Risk


20 頂点の無向グラフに対して,最短路を要求するクエリがいくつかくる.
(辺数) <= 100.

Floyd-Warshall する.

ZOJ 1225: Scramble Sort


単語あるいは数が並んだリストが.コンマ + スペース区切り,ピリオド終端で与えられる.リスト中での単語たちの位置を保ったままアルファベット順 (たとえば 'a' < 'B') にソートし,数も同様に昇順にソートする.

単語は英字列,数は整数として通った.
早くはない比較関数を書いた.英字列はその場で小文字に変換して比較,数はまず負号を見て,両方負なら substr に対して再び比較関数を呼び,両方非負なら長さ → 辞書順で比較.

ZOJ 1234: Chopsticks


N 個の非負整数が与えられ,3 整数の組を K + 8 個とる.各組を (A, B, C) (A <= B <= C) としたときその badness を (B - A)^2 とする.badness の合計の最小値を求める.
0 <= K <= 1,000,3K + 24 <= N <= 5,000,(与えられる数) <= 32,000.

降順に処理をする.A と B は隣接させるのが良いことが示せる.
これを用いて DP をしていく.C として取れる数があるかは,今までにとった (A, B) の個数から判定できる.
状態 O(N K),遷移 O(1).64-bit なのでメモリに乗らないが,3 * K に節約できる.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/33-9e847e09

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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