2017-06

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1122: Clock


時刻が 2 つ与えられる.その間 (12 時間以内) に時計の長針と短針が何回重なったかを求める.12:00 は入力にない.

11 倍して,60 * 24 の倍数の個数を数える.

ZOJ 1123: Triangle Encapsulation


三角形が与えられるので,その内部に含まれる格子点をすべて求める.出力は座標に対応する位置に書く.
-9 <= (座標) <= 9.

内部条件は 3 辺に対して det が同符号.

trailing space を出力しない,という部分を読み間違え 1PE.

ZOJ 1128: Atlantis


平面上の n 個の長方形 (軸に平行) が与えられるので,その和集合の面積を求める.
n <= 100.

座標圧縮して塗る.4 隅に ±1 を書いて部分和.

ZOJ 1129: Erdos Numbers


p 個の論文があり,それぞれの著者たちと論文名が与えられる.その後 n 人の名前について Erdos 数 (共著を距離 1 として Erdos からの距離) を求める.
p <= 32,000,n <= 3,000,(登場する異なる著者数) <= 10,000.

行の長さの条件などから,(1 つの論文の著者数) <= 41 (たぶん).
論文と著者を頂点にした二部グラフで BFS すれば,距離の半分が Erdos 数.
人名に空白が入り得るため入力をとるのがやや面倒 (',' が入らないのでそれを利用).

ZOJ 1136: Multiple


N の倍数である正の整数であって,10 進法で書いたとき桁に X[1], ..., X[M] のみが現れる最小の数を求める.存在しなければ 0 を出力.
0 <= N <= 4,999.

N = 0 は例外処理.そうでないときは N 頂点での BFS.mod N で,X[i] に対応する辺を使うと u -> 10u + X[i] となり,昇順に使えば最小が求まる.prev と pree を記録した.

memset の sizeof に違う変数を書いて 1WA.

ZOj 1139: Rectangles


平面上の N 個の長方形 (軸に平行) が与えられるので,他のいずれかの長方形に含まれているものの個数を答える.

N の上限が書いていないが,O(N^2) で調べて通った.

長方形の 4 次元の点とみなせば,いくつに含まれるかを求める部分が領域和になるので, segment tree を動的に作って O(N (log N)^4) で解ける.実行時間は却って長くなった.

いろいろ試すなかで入力の xmax と ymin の順序を何回か間違えた.また,多次元の領域木を書くときは幅は同じかつ 2 の冪にしておかないとサイクリックに回したとき危ない.

ZOJ 1140: Courses


P 個の授業と N 人の生徒がいて,各授業を受けている生徒の集合が与えられる.各授業の代表者を 1 人ずつ選び,それらが被らないようにできるかどうか求める.
P <= 100,N <= 300.

二部グラフであり,最大マッチングが P であればよい.

各種の方法を試したが,実行時間はあまり変わらなかった.

ZOJ 1144: Robbery


W * H のグリッドで強盗が動き回る.時刻 t[i] には [L[i], R[i]] * [T[i], B[i]] には強盗はいなかった,という情報が与えられる (1 <= i <= n,1 <= t[i] <= t).
強盗は単位時刻に高々 1 動ける.W * H 内に居続けることがあり得ないならばそれを指摘.そうでないならば,W * H 内に居続けたと仮定して,いた場所を特定できる時刻とその場所をすべて答える.
1 <= W, H <= 100,1 <= t <= 100,1 <= n <= 100.

時刻と場所をキーとして DP.まず時間を進める方向に行って,時間を戻す方向に行うと可能な場所の候補がすべて求まる.動かなくても良いことに注意.

ZOJ 1146: LC-Display


整数 n を一辺の長さ s の 7-segment で描く.

空白で埋めてから描いていく.7-segment の上手い埋め込み方・描き方が思いつかない.

ZOJ 1149: Dividing


価値 i のマーブルが n[i] 個ある (1 <= i <= 6).価値の和が等しくなるように 2 つの集合にわけられるかどうか判定する.
(n[i] の和) <= 20,000.

いわゆる 0-1-2 ナップサック.n[i] を 1 + 2 + 4 + 8 + ... と残り,と分割する.

価値の和が奇数のときにもそのまま sum / 2 を見てしまい WA.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/23-07cf1c26

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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