2017-10

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1073: Round and Round We Go


n 桁の整数 (leading zero もあり) が与えられる.1, 2, ..., n 倍したとき元の数を 10 進法で書いて桁をサイクリックに回した数がすべて出てくるかを判定する.
n <= 60.

掛け算して n 桁を超えたらアウト,そうでなければ set に入れていった.

ZOJ

ZOJ 1066: Square Ice


氷分子たちの配置を考える問題.(2m-1) * (2m+1) のグリッドで,O が m * m 個,H が m * (m+1) + (m-1) * m 個並んでいる.各 O に対してそれを含む H20 分子が縦ならば -1,横ならば 1,折れ線ならば 0 としたm * m 行列が与えられる.各行各列の和が 1 かつ 0 以外の同じ数が隣接しないようなものと,配置の間に全単射があるので,行列から配置を求めて絵を描く.
m <= 11.

縦や横のものをまず繋いで,使った H と O にフラグを立てる.その後各行各列に対して,左あるいは上からなめて,フラグが立っていない H や O を 2 つずつ組にして結んでいく.これで全単射性の証明にもなる.

縦と横を独立に考えてフローを流せばあまり考察せずに解ける.容量は 1 ± (行列の値) になる.

空行の入れ方を誤って PE した.

ZOJ 1067: Color Me Less


色が RGB で 16 色与えられる.それ以降に与えられる色に対して,16 色のうち最も近いものを答える.距離は RGB を R^3 とみて Euclid 距離.

毎回 16 個調べてよい.距離最小が複数あったらどうなるか書いていないがとりあえず最初のものを選んだら通った.

ZOJ 1068: P,MTHBGWB


Morse 信号にしてポーズを詰め,各文字の長さの情報を逆から読む,という形式の暗号を復号する.

経由する Morse 信号を生成してしまうのが楽.サンプルに THE_QUICK_BROWN_FOX_ ... があり安心.実は問題名もサンプルで,復号すると PROBLEM_B.

ZOJ 1070: Bode Plot


RC 直列交流回路について,R と C の間の電位を求める.

問題文に書いてある式に従うと,三角関数の合成が出てきて,位相は要らないので hypot をとる.

計算を間違えたがデータに C = 1 しかないようで通ってしまった.

ZOJ 1072: Microprocessor Simulation


1 word (4 bit) のアキュムレータ 2 個と 256 word のメモリを持つプロセッサをシミュレーションして,実行が終了したときのメモリを出力する.

特に例外処理などせずシミュレーションした.

入力の最後は 8 で始まる文字列として与えられることを読み飛ばした.サンプル入力が書いていないのでわかりづらい.

ZOJ

ZOJ 1061: Web Navigation


ウェブブラウザの BACK, FORWARD, VISIT url, QUIT をシミュレーションする.

2 本のスタックを vector で持った.

ZOJ 1062: Trees Made to Order


ノード 0 個以上の二分木に非負整数の番号を付ける.まずノード数が優先,同じノード数のときは (根の左, 根の右) の番号を pair として比較する.番号 n の二分木を出力する.
1 <= n <= 5000,000,000.

DP でノード数 i の二分木の個数を求め,ノード数 i の二分木の最小の番号を求めると,番号からノード数が復元できる.DP の過程と似たようにして番号から左と右が復元できるので,再帰的に呼ぶ.

DP 書いて出力させてみるまでカタラン数であることを忘れていた.

ZOJ 1063: Space Station Shielding


立方体のブロックが 3 次元グリッド上にいくつか置かれている.外から到達できる表面積を求める.
グリッドは 60 * 60 * 60 まで.

座標は 1 からにして,(0, 0, 0) から BFS をかけた.

DFS で適当に組んだらスタックオーバーフローと思われる判定を食らった.

ZOJ

ZOJ 1045: HangOver


台の上に,台からはみ出すようにカードを置いていく.すると n 枚のカードでは最大 1/2 + 1/3 + ... + 1/(n+1) はみ出る.長さ c はみ出すには何枚のカードが要るか求める.
0.01 <= c <= 5.20

調和級数の部分和を作って lower_bound.サンプルに c = 5.19 があり,たとえば n <= 1,000 で余裕であることがわかる.

ZOJ 1047: Image Perimeters


グリッドは X と . からなる.斜めで接する X を繋がっているとして,X たちの連結成分を考える.ある X が指定されるので,それを含む連結成分の周の長さを求める.穴が空いていたりはしない.
(縦), (横) <= 20.

同じ連結成分の X について,4 方向のうち X でない個数を足していけばよい.

ZOJ 1048: Financial Management


12 個の金額が小数第 2 位まで与えられるので,それらの平均を求める.

誤差を気にせずに通った.

ZOJ 1049: I Think I Need a Houseboat


(0, 0) を中心として y >= 0 の領域に収まる半円が,1 年に面積 50 ずつ増える.与えられた点 (x, y) が半円に入るのは何年目か求める.境界になるような入力は来ない.

ceil(π * (x^2 + y^2) / 2 / 50) が答.

ZOJ 1051: A New Growth Industry


20 * 20 でセルオートマトンをシミュレーションする.状態は 4 通り,遷移時は周囲 4 マスに依存.

ループ回数の上限が書いていないが愚直にやって通った.

ZOJ 1053: FDNY to the Rescue!


N 個の交差点があり,道路の様子が隣接行列で与えられる (有向重み付き).目的地が 1 つあり,出発地の候補がいくつかあるので,所要時間順にソートし,出発地・目的地・所要時間・経路の情報を出力する.経路は最短時間なら任意のものでよい.
N <= 20.

Floyd-Warshall して経路復元.経由点を覚えておいて再帰的に呼び出した.

出発地と目的位が同じときに経路に 2 回出力してしまった.また,テストケース間の空行を忘れていた.

ZOJ 1056: The Worm Turns


20 ブロックからなる虫が 50 * 50 上を動く.動きは,頭が指定された方向に進み,続くブロックたちが追従する.
・自分に重なる動きをしたら何番目の動きかとともに報告する.ただし尻尾が消えるところに頭が動くのはよい.
・盤からはみ出たら何番目の動きかとともに報告する.
以上にひっかからずに最後までいったら報告する.
(動きの数) <= 100.

現在虫がいるセルたちを,deque と bool 2 次元配列で保持した.

ZOJ 1057: Undercut


2 人が 1 枚ずつ数が書かれたカードを出し合うゲーム.差が 2 以上なら大きい方が大きい数の得点,差が 1 なら小さい方が 2 枚の和の得点を得る.ただし 1 と 2 なら 1 の人に 6 点.2 人の得点を求める.
(ターン数) <= 5.

swap したことを覚えつつの swap を用いて場合分けを減らした.

ZOJ 1058: Currency Exchange


レートの表と変えた貨幣の順が与えれるので,両替をシミュレーションする.両替するたびに 0.01 単位に四捨五入される.

100 倍して floor(x + 0.5) のような扱いをした.誤差を気にせずに通った.

ZOJ 1060: Sorting It All Out


最初の n 個のアルファベットで表される異なる実数について,"A・n 個の順序が決定したら何番目かと結果を報告する.
・矛盾したら何番目かとともに報告する.
最後までいずれも起こらなかったらそれを報告する.
2 <= n <= 26.

毎回トポロジカルソートできる.失敗したら矛盾.ソートした列について順番が一意である条件は,任意の j に対して j 番目の頂点から j+1 番目の頂点に直接辺があること.

最初一意性に悩み,辺に -1 して全頂点間最短路を更新していくコードとともに書いていた (更新は O(n^2) でできる).

ZOJ

提出して WA をもらってすぐに気付く間違いが多い.気を付けよう.

ZOJ 1009: Enigma


暗号を解読する.問題文の図のように,a から m 文字目までの置換が回る (巡回置換によって共役な置換に変わる),というような機械 3 つの合成で,1 つ目の機械は暗号化 1 文字に 1 回,2 つ目は m 文字に 1 回,3 つ目は m^2 文字に 1 回回る.

3 つ目の機械から順に,x |-> σ^(-1)(x - (回った回数)) + (回った回数) という写像に通せばよい.

最初暗号化だと思ってサンプルが通らなかった.問題文的には大文字小文字でわかりやすい.
WA をもらったので,次の文字列を暗号化するときに初期位置にリセットしないのでは,m + 1 回目は 1 つ目の機械は回らないのでは,などを疑ったが,暗号化だと思っていたときの名残で機械を通す順番を逆にしていなかっただけだった.

ZOJ 1016: Parencodings


適切に対応がつく括弧の列 (2n 文字) について「i 番目の右括弧より前にある左括弧の個数」が与えられるので,「i 番目の右括弧と対応する左括弧の間 (inclusive) には何個の右括弧があるか」を求める.
n <= 20.

どうせ O(n) なので括弧の列を復元してしまうのが楽.

ZOJ 1024: Calendar Game


1990/01/01 から 2001/11/04 の日付で 2 人ゲームをする.行動は,「1 日後にする」「1 か月後の同じ日付の日にする」 (後者はときどき不可能).最初の日付が与えられるので先手の勝敗を判定する.

全部で 37198 日なのでメモリに乗る.
面倒なので日付ライブラリを貼り付けたが,日付が valid かの判定が若干怪しいし不便なので,numberOfDays(y, m) = dayCount(y, m + 1, 1) - dayCount(y, m, 1) を書いた.

12 月のとき (y+1)/1/d を見るべきところ (y+1)/m/d と書いていて WA.

ZOJ 1025: Wooden Sticks


棒が n 本あり,縦 l[i],横 w[i] が与えられる.これらを何らかの順で処理するが,
・初めの棒は 1 分かかる.
・前の棒 (l, w) の次の棒 (l', w') は,l <= l' かつ w <= w' のとき 0 分,そうでないとき 1 分かかる.
最小の時間を求める.
N <= 5,000.

Dilworth の定理より,片方でソートしたときの最長狭義減少列を求めればよい.

ZOJ 1026: Modular multiplication of polynomials


F_2 上の多項式 f, g, h が与えられるので fg mod h を計算する.
(次数) <= 1,000.

普通の 2 乗で通った.

ZOJ 1027: Human Gene Functions


ACGT からなる文字列が 2 つ与えられる.適当な位置に - を挟み同じ長さであり - 同士が対応しないようにする.文字と文字の対応にはスコアがあり,その和を最大化する.
(長さ) <= 100.

最長共通部分文字列と同じ DP.

ZOJ 1029: Moving Tables


部屋 2k - 1 と部屋 2k が廊下を挟み向かい合う形で,部屋 1 から部屋 400 までが並んでいる.部屋 A[i] から部屋 B[i] へ荷物を届けたいという N 個要求が与えられる.1 つの要求は 10 分で処理でき,通る廊下の部分を共有する場合は同時に行えない.最小時間を求める.
N <= 200.

Dilworth の定理より,最も重なっている部分の個数が答.

A[i] > B[i] の場合を無視していて WA,さらに適切に修正できず WA ((A[i] - 1) / 2 と (B[i] - 1) / 2 + 1 を swap していた).また,部屋が 200 番までだと思い込み WA.

ZOJ 1037: Gridland


m * n のグリッドを頂点とするグラフで巡回セールスマン問題.辺は長さ 1 または √2 のものがすべてある.

m * n が偶数ならくねくねとして mn で回れる.奇数のときは 1 本 √2 を使うので mn - 1 + √2.

見事に mn + √2 として 1WA.

ZOJ 1038: T9


携帯電話の T9.辞書が単語に優先度つきで与えられ,1 文字打つごとに,辞書で prefix がマッチするもののうち最もあり得る文字列を答える.
(辞書の単語数) <= 1,000,(単語の文字数) <= 100,(打つ文字数) <= 100.

打つ文字列を見たときに,辞書の各単語と何文字目までマッチするか計算しておく.各文字に対する処理のところで map に加えていって最大を求めたが,実行時間には余裕があった.

テストケース番号を出力し忘れて WA.

ZOJ 1039: Number Game


2 以上 20 以下の数を言い合う 2 人ゲームを行う.
・a が既に言われているとき a の倍数は言えない.
・a, b が既に言われているとき (a の倍数) + (b の倍数) は言えない.
まだ言える数の集合が与えられるので,勝ち手をすべて求める.

まだ言える数の集合から既に言われた数の集合は決定しないので勝敗やまして勝ち手は一意に定まるかは非自明に思ったが,assert をかけたらそれが正しいと言われたのでそういうコードを出した.2660MS かかった (手元より速い).

高々 2^19 個,実際はもっと少ない個数が入る map を 3 つ使ったら MLE と言われたので配列にした.

高速化したいならば,まだ言える数でない数はすべて大きい方から言われたと思って書けばよさそう.

ZOJ 1041: Transmitters


N 点がある.中心と半径を指定された半円を 1 つ置くとき,含む点の個数の最大値を求める.
N <= 150.

半径より遠いところにあるものは無視.中心と一致するもの (実際には入力にはないらしい) は答に.残りは角度をソートして尺取など.

ZOJ 1042: W's Cipher


暗号を解読.[a-i] [j-r] [s-z_] の 3 つに分類したうえで,それぞれについて独立に (他の分類の文字を動かさずに),k[i] 文字ずらす.
(文字列の長さ) <= 80,k[i] <= 100.

3 回ループ回してずらす.うっかりしていると k[i] が大きくて負の index を見たりするので注意.

剰余が負になるトラップは回避できたが,0 除,すなわちある分類に 1 文字も含まれない場合で落ちた.適当に修正しすぎて continue を break と書いてさらに WA.

ZOJ 1043: Split Windows


長方形を分割する様子が二分木によって与えられる (入力では preorder).葉はアルファベットのラベル,その他のノードは縦に切るか横に切るか.極小領域のサイズが 2 * 2 以上になるように,全体の最小サイズを定める.その後分割するときは,最小サイズに比例するようにサイズを分ける (左または上を整数に丸める).できた図形を出力.
極小領域の個数が 1 以上 26 以下.

DFS して parse し,DFS して最小サイズを求める DP をし,DFS して絵を描く.最初は答はスペースで埋め,絵を描くときは手抜いて長方形領域全体を見る実装にした.

ZOJ

登録した.
可能な限り,ICPC World Finals 2011 の優勝者を追っかけてみる.

ZOJ 1001: A + B Problem


a と b が与えられるので a + b を出力する.

int で通った.
余分な改行を入れたら PE と言われた.

ZOJ 1002: Fire Net


いくつかのマスがふさがれた N * N のマス目がある.縦横に攻撃する駒を,互いに攻撃し合わないように最大いくつおけるか.間にふさがれているマスがあれば攻撃しない.
N <= 4.

恐らく全探索すれば通るけれど,フローの練習にした.縦に繋がったの極大成分と横に繋がった極大成分の二部マッチング.

ZOJ 1003: Crashing Balloon


1 から 100 までの風船を 2 人で取り合って,取った風船の数の積が得点となるゲーム.得点を報告し合った.
・得点が低い人が報告した得点があり得ないならば得点の高い人の勝ち
・そうでなくて,2 人の得点があり得ないならば得点の低い人の勝ち
・そうでなければ得点の高い人が勝ち
で勝敗を判定する.

int に収まった.
DFS で全探索した.同じ数を割っている場合は最後に使った約数も引数に持たせる.

得点が低い人があり得ないケースを正しく判定できていなかった.グローバルにフラグをおいて得点が高い方を割り始めるときにフラグを立てる,という方法で判定した.

POJ 1078 が同じ問題.

ZOJ 1004: Anagrams by Stack


文字列 S, T が与えられる.S の文字が先頭から 1 個ずつやってくると考えて,スタックを 1 個用いて,T を出力させたい.push を i,pop を o と書いて,可能な手順の列を辞書順ですべて出力する.

(S[a .. b], T[c .. d]) に対して解くことを考えると,S[a] == T[i] なる各 i に対して,(S[a+1 .. a+1-i-c], T[c .. i]) の解と (S[a+1+i-c .. b], T[i+1 .. d]) の解を組み合わせたものが解なので,再帰的に呼べばよい.

サイズが書いていないがこれで通った.解の最大値は長さに対してカタラン数なのですぐ爆発する.

出力の行末にも空白がいることに注意 (PE した).

ZOJ 1005: Jugs


容量 A, B の瓶がある.空にしたり満たしたり一方からもう一方へ注いだりできる.どちらかの瓶にちょうど N 入っている状態を作る操作列を出力せよ.
1 <= A <= B <= 1,000,A, B は互いに素な整数,N <= B.

ひたすら A から B に注いだ.実装上は,
・B が満杯なら空にする
・そうでなければ A が空なら満たす
・そうでなければ A から B に注ぐ
を繰り返した.

ZOJ 1006: Do the Untwist


可逆な暗号を解読する.使う文字は 0-27 にエンコードされる.
ciphercode[i] = (plaincode[ki mod n] - i) mod 28
による.n は文字列の長さ,k は与えられる.
n <= 70,k <= 300,n と k は互いに素.

与えられた式を plaincode の部分について解いて,i を回して全部埋める.

memset(T, 0, sizeof(N)); というのを書いて WA した (前のケースの答を消せていない).

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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