2011-07

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1269: Coconuts, Revisited


m 人がいて,n 個のココナッツを分配する.まず 1 人ずつ,1 個を除いて猿にあげ,残りが m 等分できたので 1 人ぶんを受け取る,ということを行う.すると m の倍数個余った.n が与えられるので,これが起こり得る最小の n を求める.

細かい制約が書かれていないが,m は int に収まり,n > 1 でなければならず,最後の m の倍数個は 0 でもよい.
m は n - 1 の約数なので調べる個数が O(√n) 個になり,おそらく十分枝は刈れるのでそれらについてすべて調べる.

ZOJ 1270: Nonstop Travel


帰り道に信号が N 個あり,それぞれの青,黄,赤の周期が与えられる.30 - 60 mph (mile/h) の整数 mph であって,一度も赤信号にひっかからずに帰れるような速度をすべて求める.青になった瞬間・赤になる瞬間は通れる.
N <= 6.

サイズが小さいのですべて試す.出力 (区間ごとに答える) がやや面倒だが無限ループに気を付けて実装する.

ZOJ 1274: Getting Chorded


3 音が与えられるので,どのコードか判定する.コードは Major と Minor のみ扱う.オクターブは無視.入力は大文字小文字や #, b が混在するが,出力は大文字,# 表記.

サイズ 12 の配列で入力を管理し,12 * 2 通りのコードをすべて試した.

ZOJ 1276: Optimal Array Multiplication Sequence


N 個の行列の積の計算回数を結合順を変えて最小化する.括弧を付けて出力.解が複数あるときは任意.
N <= 10.

O(N^3) の範囲 DP をした.DP を更新しつつどこで切ったかも記録.
計算は 64-bit で通った.

ZOJ 1278: Pseudo-Random Numbers


線形合同法による疑似乱数.初期値が与えられるので,そこから入る周期の大きさを求める.

得た数に対して何番目かを map で覚えた.
計算は 64-bit で通った.

ZOJ 1279: Cowculations


数字が 'V', 'U', 'C', 'D' で表記される 4 進法.与えられる 2 変数 x, y に対して y <- x + y,y <- y / 4,y <- y * 4 のいずれかの操作を行い y が z になるか否か判定する.

文字列で読み込んだものを整数に変換すれば普通に計算してよい.

ZOJ 1280: Intersecting Lines


2 直線が通る 2 点で与えられるので共有点の座標を求める.無限個や 0 個ならばそれを指摘.

幾何の計算.簡単だが丁寧めに点構造体を書いた (加減,実数倍,dot,det).1 点と方向ベクトルで表すと少し楽.

ZOJ 1282: Call Forwarding


時刻 C[i] から C[i] + D[i] までは,番号 A[i] にかかってきた電話は B[i] に転送する,という情報が M 個ある.同時刻に A[i] は被らない.その後,時刻とかかる電話番号が与えられるので,繋がる番号を答える.ループがあれば指摘.
M <= 100,0 < (番号) < 9,999.

各クエリに対して M 個の情報をすべて見てリンクを張った.そのリンクを辿っていき答を求める (この部分が結局 O(M)).変数の初期化はやや気を使って O(M) で行った.

ZOJ 1284: Perfection


M が完全数か過剰数か不足数か判定する.
1 <= M <= 60,000,(ケース数) < 100.

それぞれ O(√M) で約数の和を求める.

出力形式で 2 個の空白を 1 個だと思って PE.

ZOJ 1286: Slurpy


文字列が Slump であるとは,'D' か 'E' で始まり,1 個以上の 'F' が続き,'G' で終わること.
Slimp であるとは,'A' で始まり,2 文字ならば 'H' で終わり,そうでなければ次のいずれかであること:
・'B' が続き,Slimp が続き,'C' で終わる.
・Slump が続き,'C' で終わる.
Slurpy であるとは,Slimp 1 個と Slump 1 個がこの順に並んでいること.
与えられる文字列が Slurpy であるかを答える.
(文字列の長さ) <= 60.

多少余計だが,Slump, Slimp, Slurpy のそれぞれについて [a .. b] が条件を満たすかをメモ化再帰した.
サンプルが弱いので問題文中の例を使う.

Slump の最後の 'G' (1 個) を 1 個以上だと勘違いして WA.

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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