2011-06

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1151: Word Reversal


単語が空白で区切られて与えられるので,空白はそのままに各単語の文字を逆順にして出力する.

char の配列をなめていって部分部分に reverse.

ZOJ 1152: A Mathematical Curiosity


整数の組 (a, b) であって,0 < a < b < n かつ (a^2 + b^2 + m) / (ab) が整数となるようなものの個数を求める.
0 < n <= 100.

O(n^2) 通り調べる.

ZOJ 1154: Niven Numbers


N を b 進法で書いたとき各桁の和が N を割り切るかどうか判定する.N は b 進表記で与えられる.
2 <= b <= 10.

文字列で読み込んだ.N の値は 64 bit 符号付き整数には収まる様子.

ZOJ 1159: 487-3279


電話番号がいろいろな表記で与えられる.数字および大文字 (Q, Z 以外) はちょうど 7 文字ずつあり,それらを取り出し,大文字は T9 っぽく数字に変換して標準形とする.2 回以上現れたものたちを,番号の昇順に現れた回数とともに出力する.そのようなものがなければそれを指摘.

桁数固定なので自然に整数にエンコードでき,map で数えた.

2 回以上現れたものがないときの出力を見逃していた.

ZOJ 1160: Biorhythms


P, E, I のピークというものがあり,それらは 23 日,28 日,33 日ごとに訪れる.年の初めから p 日後は P のピーク,e 日後は E のピーク,i 日後は I のピークである.今年の初めから d 日後であるとき,翌日以降でピークが 3 つ重なるのは何日後か求める.

合同式を解く.23 * 28 * 33 = 21252 が小さいので,Z/23Z * Z/28Z * Z/33Z → Z/21252Z をメモリに持っておいても良さそう.

ZOJ 1163: The Staircases


N 個の箱を使って階段を作る.階段は 2 ステップ以上からなり,段の高さは狭義単調.何通りの階段ができるか求める.
3 <= N <= 500.

答は (distinct 分割数) - 1.「i を j 以下で分割する方法」を O(N^3) の DP で求める.
N = 500 で 7 * 10^14 程度.

ZOJ 1164: Software CRC


文字列のチェックサムを作る.2 byte 付け足して,先頭を最高位 bit としてみたとき 34943 の倍数になるようにする.

剰余をそろえればよいので,不足を求める.

ZOJ 1168: Function Run Fun


整数 3 つをとる関数 w の漸化式が与えれる.0 以下があれば値は 1,21 以上があれば w(20, 20, 20).w(a, b, c) を求める.

メモ化すればよい.値は負にもなるので,メモがとれたかどうかのフラグを別に持っておいた.

出力形式を無視し答えの値のみ出力していて WA.

ZOJ 1170: String Matching


文字列 S, T が与えられる.S と T を適切に横にずらして並べて揃っている文字の個数が最大になるようにする.その値を 2 / (|S| + |T|) 倍して分数 (整数なら整数) で出力.

ずらし方をすべて試して O(|S| |T|) で通った.

ZOJ 1171: Sorting the Photos


写真が N 枚重なっていて,上向きか下向きかになっている.向きをすべて揃えるためには,上から何枚かを選びそれらの上下をまとめて反転する,という操作を最小何回行えばよいか求める.
1 <= N <= 10^5.

上と下が隣り合っている箇所の個数が答.
入力が上の写真から与えられるか下の写真から与えられるかが書かれていないように思うが,答には関係ない.

ZOJ 1174: Skip Letter Code


N 個の単語を含む辞書が与えられる.その後文章が与えられるが,単語からはいくつかの文字が取り除かれている.空白や改行を保ちつつ,単語を復元して出力する.一意に定まらなければそれを指摘.
1 <= N <= 100,(単語の文字数) <= 5,(文章の長さ) <= 10^6.

各単語に対して,2^(長さ) - 1 通りの部分列を生成しておいてそこから引けるようにする.

ZOJ 1177: K-Magic Number


10 進法で,先頭の桁をとって末尾に付けると 1/K 倍になる最小の正の整数を求める.
1 < K <= 10^4.

10^e x + y とおけば (10^e - K) x = (10 K - 1) y となり,e の小さい方から 1 <= x < 10 を試し,剰余を調べて y が整数になるものを探す.このとき必ず y < 10^e となるのでこれで見つかることになり,多倍長割り算を行う.
少なくとも e = φ(10 K - 1) - 1 では 10 K - 1 | 10^e - K なので,O(K).

ZOJ 1178: Booklet Printing


n ページのパンフレットを印刷する.1 枚目表には 4k ページと 1 ページ,裏には 4k - 1 ページと 2 ページ,などとなり,これらを出力する.4 | n とは限らず,余る高々 3 ページは Blank とする.
n <= 100.

n の次の 4 の倍数 n' を求めて,n'/4 枚分順番にページ番号を求める.左右に印刷するページ数の和が n' + 1.

ZOJ 1180: Self-Numbers


入力なし.n + (n の各桁の和) と書けないような,1 以上 1,000,000 以下の整数をすべて出力する.

n の各桁の和は n/10 の結果を用いれば線形で求まる.1 <= n <= 1,000,000 で配列の [n + (n の各桁の和)] を埋めていく.

ZOJ 1181: Word Amalgamation


辞書が与えられ,続いて文字列のクエリたちが与えられる.辞書の単語であって文字を並べ替えるとそれになるものを辞書順ですべて出力する.存在しないならばそれを指摘.
(辞書の単語数) <= 100,(単語の文字数) <= 6.

辞書の単語 s に対して,(s をソートしたもの, s) を pair としてソートしておき,lower_bound,upper_bound で取り出す.

ZOJ 1184: Counterfeit Dollar


12 枚のコインがあり,1 枚だけが偽物で他と重さが異なる.天秤を 3 回使った結果が与えられるので,偽物がどれか,重いか軽いか,を求める.答えは一意に定まる.

12 * 2 通りの可能性をすべて試す.

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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