2017-10

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1094: Matrix Chain Multiplication


行列積計算の式が与えれる.変数はアルファベット大文字.x * y 行列と y * z 行列を掛けるときに x * y * z 回乗算するとして,乗算回数を求める.途中で型が合わなければ指摘.

再帰降下で構文解析.返り値は行列サイズを表す pair にして,乗算回数はグローバルにおいた.

ZOJ 1095: Humble Numbers


素因数が 2, 3, 5, 7 のみである正の整数で小さい方から n 番目を求める.ついでに,「n 番目」を序数で出力する.
1 <= n <= 5842.

「数列中の数を p 倍して作れる次の数」を各 p についてもっておけば次の数は 4 つの候補のうちどれかで,等しいものを次に進める,として数列が生成できる.
序数はまず mod 100 にし,10 台なら -th,他は 1 の位を見る.

ZOJ 1097: Code the Tree


n 頂点の木に対して,葉のうち番号が最小のものを取り除き隣接していた頂点の番号を記録,というエンコードを行う.入力は pre-order のような構造で書かれているので構文解析する.
1 <= n <= 50.

構文解析する前に括弧の個数を数えると頂点数があらかじめわかる.
次数 1 になるたびに priority queue に入れる.O(n log n).辺は頂点ごとの set で管理した.

ZOJ 1098: Simple Computers


メモリ 32 byte,アキュムレータ 8 bit,プログラムカウンタ 5 bit のコンピュータをシミュレーション.命令は メモリ[プログラムカウンタ] で,上 3 bit が種類,下 5 bit が引数という形.プログラムカウンタは命令が読み込まれた後実行される前に 1 増える.停止は保証されていて,停止時のアキュムレータを出力する.

シミュレーション.オーバーフロー時は自然に mod をとったら通った.

ZOJ 1099: HTML


タグ <br> と <hr> のみを処理する HTML ブラウザを書く.入力は単語 (80 文字以下) 区切りで与えられ,
・<br> : 強制的に改行.
・<hr> : 現在の行が 0 文字でなければ改行,80 個ハイフンを出力,改行.
・その他の単語 : 現在の行に入れて 80 文字以内ならば入れる,そうでなければ改行して出力.
出力の最後は改行 1 つで終わる.

現在の行の文字数を持ちながらシミュレーション.0 文字のとき各種場合分けが要る.

ZOJ 1100: Mondriaan's Dream


h * w のグリッドを 1 * 2 (or 2 * 1) の長方形で敷き詰める方法は何通りあるか求める.
1 <= h, w <= 11.

h * w が奇数のときは 0 通り.二部平面グラフの完全マッチングの個数なので,すべての閉路を奇数的に向きづけて 二部隣接行列を作れば,その行列式の絶対値が答.

DP してもよい.あらかじめ,2^h 個の座標の集合について隣り合う 2 つずつで組にできるかを求めておく.x と x において長方形が切られる y 座標の集合を状態とすれば,O(w 3^h) (もう少し良い評価ができるかも).

ZOJ 1101: Gamblers


n 個の異なる整数からなる集合が与えられるので,この集合の異なる 4 元 a, b, c, d に対して a + b + c = d となる最大の d を求める.
1 <= n <= 1,000.

a + b と d - c を作り方とともにすべて列挙 (n(n-1)/2 個,n(n-1) 個) してソート.d - c の昇順になめていき a + b が d - c と同じ値になる区間を考えて a, b, c, d が異なるかどうかチェックする.ここで,a + b が同じ値である {a, b} たちは共通部分をもたないので,区間のうち最初の 3 個を考えれば a, b, c, d が異なるものが見つかることがわかる.見つかったら break というコードを書けばよい.O(n^2 log n).

a, b, d が異なる,のみしか判定していなくて WA.
「見つかったら break」というコードの前に区間の長さを正確に求めることをしてしまい,通ってしまったが最悪 O(n^3) だった.

ZOJ 1103: Hike on a Graph


無向完全グラフの各頂点にループを付けたグラフがあり,各辺にはアルファベット小文字で表される色が塗られている.駒が 3 個あり,頂点に乗っている.1 回の動きで,1 個の駒を,残り 2 個の駒を結ぶ辺と同じ色の辺を辿って動かすことができる.何回の操作で駒を 1 頂点に集められるか求める.
1 <= n <= 50.

状態 O(n^3),それぞれ遷移 O(n) の BFS.

ZOJ 1105: FatMouse's Tour


線分の道路がいくつかあり,それぞれの両側を進まなければならない.出発点から道路に沿ってどの道路の点へも行ける.初めて訪れる側では 20km/h,そうでないときは 50km/h で進める.出発してすべての道路の両側を進んで帰ってくるまでの最短時間を求める.

すべての辺を二重にすれば次数から Euler 回路が存在.よってすべての道の長さの 2 倍を 20km/h で進むことになる.

入力形式がやや面倒,1 行ずつ読み込む必要あり.ケース終了の目印を全体終了だと思い込んで 1WA.

ZOJ 1107: FatMouse and Cheese


n * n のグリッドの各マスにチーズがいくつかある.ねずみが (0, 0) からスタートして,一度に 4 方向のいずれかにまっすぐ高々 k マス進める.滞在するマスにおいてチーズをすべて食べられるが,チーズの個数が真に増えていかなければならない.チーズを食べられる最大個数を求める.
1 <= n, k <= 100.

DAG になるのでメモ化再帰で解ける.O(n^2 k).

ZOJ 1108: FatMouse's Spped


ねずみの重さと速さの組が N 個与えられる.重さが狭義単調増加で速さが狭義単調減少になるような列 (元の順番は無視) のうち最長のものを,index の列として出力する.
n <= 1000.

重さ昇順 → 速さ昇順 でソートして速さの最長狭義単調減少部分列を求める.作るときに prev を張っていく.

ZOJ 1109: Language of FatMouse


英語とねずみ語の対として辞書が与えられる.その後,ねずみ語が与えられるので対応する英語を答える.辞書に存在しなければそれを指摘.
(辞書のサイズ) <= 100,005,(クエリ数) <= 100,005,(単語の長さ) <= 10.

Trie で書いてみた.ただし 100,005 * 10 * 26 はメモリに乗らないので,隣接リストにして,ラベルから辺にアクセスするときに 26 のループを回した.

ZOJ 1110: Dick and Jane


年齢は生まれてからの時間を 1 年で割って整数部分を見たものとして定義.
Spot は Puff が生まれたとき s 歳,Puff は Yertle が生まれたとき p 歳,Spot は Yertle が生まれたとき y 歳,現在の Spot と Puff と Yertle の年齢の和は 12 + j.3 人の年齢を求める.

3 人の年齢では切り捨てられた量の順序関係をすべて試す ({0, 1, 2}^3 を試せば十分).すると年齢の差 s', p', y' が求まるので,s' + p' + y' と mod 3 を判定して年齢を求める.
答は一意に定まる.

ZOJ 1111: Poker Hands


2 人のポーカーの手が与えられるので,どちらが強いか求める.ストレートは巡回せず,同じ役の比べ方は通常とやや異なる.

カードはソート.「数 j の枚数は as[j] 枚」なる配列 as と,「k 枚ある数の集合は bs[k]」なる set の配列 bs を作って利用する.また,ストレート・フラッシュ・ハイカード用の値を準備.ワンペアの強さ判定においては,ペアの数を見た後はハイカード用の値を使えばよい.

ZOJ 1113: u Calculate e


入力なし.sum { 1/i! | 0 <= i <= n } を 0 <= n <= 9 で計算する.n <= 4 の例が掲載されており,それに従う (原則小数点以下 9 桁だが,有限小数ならそこまでを出力する).

n <= 2 のみ表示桁数を printf の %.*f を用いて場合分けした.

すべて 9 桁出してサンプルが合ったと思い込んで提出してしまった.

ZOJ 1114: Problem Bee


一辺 R の六角形格子 ((0, 0) に中心があり,(±R, 0) に頂点がある) を考える.2 点 A, B が直交座標系で与えられるので,A → A のセルの中心 (→ セルの中心)* → B のセルの中心 → B と移動するときの最短路を求める.

問題文に書いていない仕様だが,A のセルと B のセルが一致するときに直線距離を出力する.
(±√3, 1) 方向に p, q 座標をとると,セルは (3/2)(p - q) = x, (√3/2)(p + q) = y を実数で解いてその周辺の整数で最も近いものとして求まる (ボロノイ図なので).

変数のタイプミス (qa と qb) で 1WA.

ZOJ 1115: Digital Roots


整数に対して,10 進法で書いて桁の和に変換する,ということを 1 桁になるまで行う.最後に得られた値を求める.

サイズが書いていないが文字列として読み込んだ.桁の和の mod 9 で,0 ならば 9 に.

ZOJ 1116: A Well-Formed Problem


XML が与えられる.以下をすべて満たすかを判定する.
・タグは木構造 (森でない).
・タグはその内部に同名のタグを持たない.
・タグの属性は,そのタグ内ですべて異なり,すべて値を持つ.
自己完結タグも存在.タグ名は英数あるいはハイフン.

入力がどのくらい整っているかわからなかったので,丁寧に構文解析した.グローバルに,根から辿っている段階でのタグ名の集合や見ているタグ内での属性名の集合などを置いた.ASSERT(x) を x が偽なら return 0; として define したり,空白文字の間読み飛ばす関数 skip を作ったりした.

ZOJ 1117: Entropy


与えられた文字列を prefix-free になるように最適にエンコーディングして何 bit になるか,と圧縮率を求める.

Huffman 符号にする.出現回数が少ないものから 2 つずつを merge していく.priority queue を用いた.

文字が 1 種類しかなかったときに 0 としていて WA.

ZOJ 1118: N-Credible Maze


n 次元空間の迷路.始点と終点と辺が与えられるので,到達可能か否か答える.
n <= 10.

map< vector,int > で頂点番号を振った.

ZOJ 1119: SPF


無向グラフが与えられるので,取り除くと連結成分が 2 個以上となる頂点をすべて指摘し,何個の連結成分になるかを出力する.辺のみで与えられるので孤立点はなし.
(頂点数) <= 1,000.

DFS して lowlink を求める.子のうち (lowlink で戻れないもの) + 1 個にわかれる (ただし根ならば +1 しない).全体が連結かどうかわからなかったのでそれに (連結成分) - 1 を足した.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/22-6191ee48

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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