2017-10

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1188: DNA Sorting


ACGT n 文字からなる文字列が m 個与えられるので,逆転数の昇順にソートする.逆転数が同じ場合は入力の順.
n <= 50,m <= 100.

ACGT なのでサイズ 4 の配列で文字を数えていけば逆転数は O(n) で求まる.index と pair にしてソート.

ZOJ 1189: Numbers That Count


数字からなる文字列に対して,「何個の何がある」をそのまま並べた文字列に変える,という操作を繰り返す.15 回以内の操作でループが検出されるかどうかを判定し,検出された場合はループのサイズ等も答える.
(最初の文字列の長さ) <= 80.

長さは常に 80 を超えない.15 回先まで最初に作ってしまい,16C2 組の一致判定を行った.

ZOJ 1190: Optimal Programs


ADD, SUB, MUL, DIV, DUP 命令が使えるプログラムによって,入力 x[i] に対して出力 y[i] を得る (1 <= i <= N) ものを作る.メモリはスタックで,4 つの演算はスタックの上 2 つに対して行い,DUP はスタックの上 1 つをコピー.途中経過の絶対値が 30,000 を超えたり,0 除したり,空のスタックから取り出そうとしたらエラー.
長さ 10 以下のものが存在しなければ指摘,存在するならば長さ最小のものを,それでも複数あれば辞書順最小のものを求める.
N <= 10.

プログラムを動かしながら探索.スタックのサイズに注目すると,長さ 2m のプログラムは高々 4^m C[m] 通り (C[m] はCatalan 数) であり,合計で 50,000 通り未満となるのでこれで枝刈りを入れた.

答の初期化の際にサイズ N + 1 の vector を用いたが,M + 1 (= 11) の誤り.

ZOJ 1191: The Die is Cast


サイコロの目がいくつか平面に描かれた様子が 2 次元グリッドで与えられる.文字 '*' と 'X' による (縦横の) 連結成分を 1 つの面とみなし,目の個数はその中の 'X' の連結成分の個数とする.目の個数たちを昇順で出力する.
(グリッドの縦横) <= 50.

Union-Find を 2 本用いた.

ZOJ 1193: Reflections


平面上に円が n 個置かれている.円たちは共有点を持たない.光線がある点からある方向に出て,円に当たったら反射する.最初の 10 回の反射について,どの円に当たるかを求める.また,10 回以下の反射で反射しなくなるかどうかも判定.
n <= 25.

毎回円と直線の交点を求めて反射点の候補を列挙し,方向ベクトルとの内積をとって正で最小のものを選ぶ.

ZOJ 1195: Blowing Fuses


n 個の装置があり,それぞれの電流消費が与えられる.最初すべてスイッチがオフで,m 回のオンオフを切り替える操作が行われる.容量 c のヒューズが飛ぶかどうか判定し,飛ばない場合は最大の電流を求める.
n <= 20.

n が小さいのでオンかオフかは配列で持てる.最大値を最後まで求めてから c と比較した.

ZOJ 1196: Fast Food


n 個のレストランが直線状に並んでおり,k 個の車庫をいずれかのレストランに設置する.各レストランについての最寄りの車庫までの距離の和の最小値を求める.
n <= 200,k <= 30.

現在見ているレストラン,最後に車庫を設置したレストラン,設置した車庫の個数を状態にして O(n^2 k) の DP.レストラン i, j に車庫を設置した場合のコストとして i と j の間にあるレストランからの距離を考えるが,どちらが近いかの境目を O(log n) で求めれば,距離の部分和をもっておけば求まる.事前計算しておけば O(n^2 log n) で済む.

ZOJ 1199: Point of Intersection


2 円の共通外接線の交点を求める.存在しないならば指摘.

半径が等しければ存在しない.そうでないときは,2 つの中心の半径の比での外分点を求め,円の内部になければそれが答.

ZOJ 1200: Mining


ロボットが基地から鉱山へ向かうには時間 S がかかり,内部で時間 W かかって C 単位の資源を得て,基地へ戻るのに時間 S がかかる.内部には同時に 1 個までしか働けない.基地では K 個のロボットが 1 個あたり時間 M で作られる.10,000 単位を得るまでの時間を求める.

内部に入るところでロボットがたまると考え,そこに到達する時刻で priority queue を用いて管理.i 番目 (1-based) のロボットは最初は時刻 M * i + S で,その後は時刻を進めながら 1 個ずつ働かせ,時刻 (働き終わり) + S + S を再び push.

ロボットは K 回周期で働くと思い込んで WA.

ZOJ 1201: Inversion


n 元の置換 A に対し,B[A[j]] = #{ i | i < j, A[i] > A[j] } として数列 B を作る.A または B が与えられるので,もう一方を求める.
n <= 50.

A から B を求めるのは逆転数を求めるときと同様にできる.O(n^2) で書いた.
B から A を求めるには,j より大きい数が B[j] 個既に現れている最小の j を追加する,ということを繰り返せばよい.O(n^2) で書いた.

ZOJ 1202: Divide and Count


区別のつくダイアモンド A[0] + ... + A[N - 1] 個と区別のつかない箱 N 個がある.箱 i には A[i] 個のダイアモンドを入れるとき,ダイアモンドの入れ方の総数を求める.
N <= 12,A[i] <= 12,(答) < 2^32.

(A[0] + ... + A[N - 1])! を各 i に対して A[i]! で割り,サイズの j の箱が B[j] 個あるとして各 j に対して B[j]! で割る.
オーバーフローが不安だったので,割る数の方を素因数分解された形で持ち (11 までしかない),最後に (A[0] + ... + A[N - 1])! 割りながらかけていった.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/30-44f8d118

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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