2017-06

Latest Entries

スポンサーサイト

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

ZOJ

ZOJ 1300: Border


グリッド上を東西南北に距離 1 ずつ移動して閉曲線を書いた様子が与えられるので,その境界となっている外側のマスを塗ったビットマップを 32 * 32 で出力する.

各進行方向に対して 45 度のマスを塗っていった.座標を 2 倍して処理.

'X' で出力すべきところを '#' で出力して WA.

ZOJ 1301: The New Villa


r 個の部屋があり,各部屋には電灯がついている.d 組の接続がある.s 個のスイッチがあり,場所とコントロールする電灯がある部屋が与えられる.電灯がついていない部屋にはいられないとして,部屋 1 のみの電灯がついている状態から部屋 r のみの電灯がついている状態への最短行動数を求める.行動はスイッチの on/off と移動をそれぞれ 1 と数える.可能な場合は行動も出力する.
r <= 10.

スイッチの状態といる部屋の位置を状態として BFS して経路復元.状態 O(2^r r),遷移 O(r) で書いた.

行動を出力する際,on/off をすべて on と書いていて WA.

ZOJ 1307: Packets


1 * 1, 2 * 2, ..., 6 * 6 の正方形が何枚かずつある.これらを 6 * 6 の正方形に詰めるとき,最小何枚に入るか求める.

6 や 5 は貪欲に使ってよい.4 も 2 をつけることを優先して貪欲に使ってよい.1, 2, 3 の 3 を含む極大な使い方は (7, 5, 1), (6, 3, 2), (5, 1, 3), (0, 0, 4) で,これらをいくつずつとるかをすべて調べた.余った 1, 2 は貪欲に使える.

スポンサーサイト

ZOJ

ZOJ 1292: Integer Inquiry


正の整数がいくつか与えられるので,それらの和を出力する.
(個数) <= 100,(桁数) <= 100.

各桁ごと配列に足しこんでから繰り上がりを処理した.

ZOJ 1293: Floppies


あるデータのサイズが与えられる.半分になり,+50% され,62 個に分割し,30000 個に分割し,それぞれをフロッピーに入れる.何枚のフロッピーが必要か答える.

分割するときは ceil を計算する.

問題解釈に苦しみ WA を出した.書かれていないが,丸めは 0.5 を切り上げる.

ZOJ 1294: Golf


ゴルフで,par p のホールで s 打だったときの結果の呼称を出力する.ただし "Double Bogey" より酷いときはごまかして "Double Bogey" とする.

s = 1 かを見たあと,s - p で switch した.

ZOJ 1295: Reverse Text


入力の文字列を逆にした文字列を出力する.

gets でとってきて reverse した.

ZOj 1298: Domino Effect


ドミノを倒す.n 点が key domino とされていて,m 組の key domino 2 つの間にはドミノが並んでいて,一方から他方へ倒れるときの時間が与えられる.key domino 1 から倒したとき最後に倒れるドミノの時刻と位置を答える.key domino であるか key domino 2 つの間であるかを区別して出力する.複数ある場合は任意.
n < 500.

まず最短路を求める.Dijkstra を書いた.その後頂点 u に対する d[u] + d[u] / 2.0 と辺 i = uv に対する d[u] + d[v] + C[i] の中から最大のものをとる.最後に 2 で割る.

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.

ZOJ

ZOJ 1237: Fans and Gems


N * M のグリッドがあり,周囲と内部のいくつかのマスは壁.宝石 ('1', '2', '3') と flyer ('@') がいくつかのマスにある.1 回の操作で,4 方向のいずれかに風を吹かすことができる.宝石あるいは flyer は風で動き,風の方向のマスに進めなくなるまで一瞬で動く.その後,同種類の宝石はくっついていたらすべて同時に消え,再び風で一瞬で動き,ということを繰り返す.すべての宝石を消すまでにかかる最小操作回数の手順をもとめ,'U', 'D', 'L', 'R' で辞書順最小のものを答える.不可能ならそれを指摘.
1 <= N <= 12,1 <= M <= 20,(可能な場合の最小手数) <= 18,(ケース数) <= 50,TL 10 秒.

直前とは異なる方向に風を吹かす,ということを用いて全探索すると少なくとも 4 * 3^17 かかり終わらない.
ID + DFS を行いつつ,同じ盤面がよく現れるので枝を刈る.盤面を vector にエンコードし,盤面に対しそれに至る手数を map で保持.手数が依然訪れたときより更新されなければ無視.
風を吹かす操作と宝石を消す操作は 1 ステップ O(NM) で書いて通った.4 秒弱.

ZOJ 1239: Hanoi Tower Troubles Again!


N 本の棒がある.正の整数が書かれたボールを 1 から順にいずれかの棒に通す.2 つのボールが隣り合うときはそれらの和は平方数でなければならない.最大何個のボールを入れられるか求める.
N <= 50.

ボールの個数が与えられたとき必要な棒の最小本数は DAG の最小パス被覆なので二部マッチングで求まる.これを用いて解を埋め込める.
埋め込んだ結果を見るとわかるが,答は N の式で書ける.
実はボールを入れる場所は一意に定まる.0 もボールとみなすと,新しい棒が必要となるのは 2k^2, 2k(k + 1).[2k^2, 2k(k + 1)] が見えているときはこれらの上に [2k(k + 1) + 1, 2(k + 1)^2 - 1] が乗り,[2k(k + 1) + 1, 2(k + 1)^2] が見えているときはこれらの 2(k + 1)^2 以外の上に [2(k + 1)^2 + 1, 2(k + 1)(k + 2) - 1] が乗るので,帰納的に言える.

最初,二分探索 + 二部マッチングを submit したが TLE した.

ZOJ 1240: IBM Minus One


アルファベットを 1 文字前にずらした暗号を解読する.
(文字数) <= 50.

int にしてから +1, %26 した.

ZOJ 1241: Geometry Made Simple


直角三角形の 3 辺の長さ a, b, c (c が斜辺) のうち 2 つが与えられる (残り 1 つは -1 と書かれる).残り 1 つの辺の長さを求める.矛盾があればそれを指摘.

a を求めるとき c <= b,b を求めるとき c <= a であれば矛盾.他は sqrt で求まる.

ZOJ 1242: Carbon Dating


半減期 5730 年のものが最初 810 * w あり d になった.年数を求める.10,000 年以下なら 100 年単位に丸め,それ以降は 1,000 年単位に丸める.

まず log で年数 x を求める.a 単位にまとめるには x = (int)(x / a + 0.5) * a; とすればよい.

ZOJ 1243: URLs


URL を構文解析して protocol,host,port (optional),path (optional) を答える.

':', '/' および null が区切り文字としての役割のみを持つのでそれを見つけるまでいてイテレートしつつ出力.

ZOJ 1244: Definite Values


variable1 = variable2 という形の式が n 個与えられる.最初変数 a のみが初期化されており他の変数は不定.n 個の式を順に実行したときに,値が定まっている変数名をすべて出力する.なければ指摘.
変数名はアルファベット小文字 1 文字.

a を 1,他を 0 として実行して 1 のものを答えればよい.

行末に空白を入れるのを読み落として 1PE.

ZOJ 1247: There's Treasure Everywhere!


"3N,1N,10NW." のような形式で移動量と移動方向が与えられるので,(0, 0) からスタートして到達した点の座標と直線距離を答える.
(入力の長さ) <= 200.

区切り文字までの 'E', 'N', 'W', 'S' で (dx, dy) を数え,斜めに進んでいたら √2 で割り,足す."-0.000" 出力を避けるため,sprintf して "-0.000" になったら 0 代入,とした.

"-0.000" で 3WA を出した.1, √2 で進む回数を数えて最後に掛け算する方が安全と思われる.

ZOJ 1251: Box of Bricks


場所が n 個あり,場所 i には箱が h[i] 個積まれている.箱の個数の合計は n の倍数.すべての場所の高さを等しくするために移動させる必要がある箱の個数の最小値を求める.
n <= 50.

平均との差の絶対値の和の半分,あるいは平均よりあふれた分の和.

ZOJ 1259: Rails


1, 2, ..., N の順にやってくるので,1 本のスタックを用いて指定された順序に出していくことができるか否か判定する.
N <= 1,000.

操作方法が一意なのでシミュレーションすればよい.出力したいものがスタックの先頭に来るまで入力から push し,入力が空のときに失敗.O(N).

ZOJ 1260: King


整数列 a[j] (1 <= j <= n) があり,(a[s[i]] + ... + a[s[i] + n[i]]) o[i] k[i] (o[i] は不等号 < or >) という形の条件が m 個与えられる.これらが矛盾するか否かを判定する.
n <= 100,m <= 100.

部分和 S の条件に書き直すと,条件は S[v] <= S[u] + c の形に書けるので,(u, v) にコスト c の辺を張って Bellman-Ford で負閉路があるかを判定する.

条件の部分列の長さを n[i] と思って WA (正しくは n[i] + 1).

ZOJ 1262: Word


'a', 'b' からなる文字列を考える.i - 2 文字目が c1,i 文字目が c2,i + 1 文字目が c3 のとき i 文字目を c4 に書き換える (index はループする),という形の規則が 2^3 個 (すべて) 与えられるので,これに従って同時に書き換える.この操作を s 回行った結果を出力する.出力するものは cyclic に回して辞書順最小のもの.
(文字列の長さ) < 16,s <= 2,000,000,000.

2^15 回以内に周期に入る (cyclic に回して同じものを区別しなければもっと早いが不要).2 進数にエンコードして処理し,x が i 回目に現れたとき i から x,x から i 両方の対応を配列に保存すればよい.

ZOJ 1268: Is It A Tree?


木とは,0 頂点のグラフあるいは通常の意味の有向木 (辺は葉の方向).頂点には適当な整数のラベルがついているとして辺の集合が与えられるので,木かどうか判定する.

0 辺ならば木.その他については,Union-Find などでサイクルがないことを判定し,入次数が 1 頂点を除いて 1 であることを見た.

ZOJ

ZOJ 1203: Swordfish


平面上の N 点を結ぶ Euclid 距離での最小全域木を求める.
N <= 100.

Prim 法を用いた.

ZOJ 1205: Martian Addition


20 進法で足し算をする.
(桁数) <= 100.

非負として通った.出力で leading zero を削るとき 0 + 0 に注意.

ZOJ 1206: Win the Bonus


いくつかの数字 3 文字の並びに対して,それを含むことで得られる得点が定まっている.n 個の数字の並びで,得点が最大であるものを求める.複数ある場合は辞書順最小.
n <= 10,000.

得点の情報は 10^3 の配列に入れた.状態 n * 10^2 で最大値を求める DP を後ろから行い,それを用いて復元.

ZOJ 1208: Roll the Die!


さいころの動きをシミュレーションする.最初の位置の上と正面の面が与えられ,これが適切でなければ指摘.動きは平面上で 4 方向のいずれかに転がることの繰り返し.最後の位置の上と正面の面と座標を出力する.
(操作回数) <= 35.

まずさいころを 24 通り生成して初期状態を探す.その後は上方向・右方向に転がす関数で転がす.

ZOJ 1209: April Fool's Joke


時計の短針と長針を入れ替えたらどう読めるかについて解析する.短針から求まる分の読みと長針から求まる分の読みを求め,差が 12 以下なら長針から求まる分の読みを採用する.

言われたものを 1 つずつ求める.0 時が 12 時と表記されるので,内部では 12 を 0 にして処理.

ZOJ 1216: Deck


机から長さ 1 のカードをはみ出させる.n 枚のときの長さを求める.
0 <= n <= 99999.

1/2 + 1/4 + ... + 1/2n の部分和をもっておいてそれを答える.

ZOJ 1218: Ratio


分数が与えられるので,それを近似する分数を求めていく.分母 1 から始め,精度が良くなる最小分母のたびに出力する.差が等しい場合は大きい方とする.
(分子),(分母) <= 5,000.

分母から分子が求まるので,分母をループさせて近くなったかを毎回判定.

ZOJ 1221: Risk


20 頂点の無向グラフに対して,最短路を要求するクエリがいくつかくる.
(辺数) <= 100.

Floyd-Warshall する.

ZOJ 1225: Scramble Sort


単語あるいは数が並んだリストが.コンマ + スペース区切り,ピリオド終端で与えられる.リスト中での単語たちの位置を保ったままアルファベット順 (たとえば 'a' < 'B') にソートし,数も同様に昇順にソートする.

単語は英字列,数は整数として通った.
早くはない比較関数を書いた.英字列はその場で小文字に変換して比較,数はまず負号を見て,両方負なら substr に対して再び比較関数を呼び,両方非負なら長さ → 辞書順で比較.

ZOJ 1234: Chopsticks


N 個の非負整数が与えられ,3 整数の組を K + 8 個とる.各組を (A, B, C) (A <= B <= C) としたときその badness を (B - A)^2 とする.badness の合計の最小値を求める.
0 <= K <= 1,000,3K + 24 <= N <= 5,000,(与えられる数) <= 32,000.

降順に処理をする.A と B は隣接させるのが良いことが示せる.
これを用いて DP をしていく.C として取れる数があるかは,今までにとった (A, B) の個数から判定できる.
状態 O(N K),遷移 O(1).64-bit なのでメモリに乗らないが,3 * K に節約できる.

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])! 割りながらかけていった.

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 通りの可能性をすべて試す.

ZOJ

ZOJ 1122: Clock


時刻が 2 つ与えられる.その間 (12 時間以内) に時計の長針と短針が何回重なったかを求める.12:00 は入力にない.

11 倍して,60 * 24 の倍数の個数を数える.

ZOJ 1123: Triangle Encapsulation


三角形が与えられるので,その内部に含まれる格子点をすべて求める.出力は座標に対応する位置に書く.
-9 <= (座標) <= 9.

内部条件は 3 辺に対して det が同符号.

trailing space を出力しない,という部分を読み間違え 1PE.

ZOJ 1128: Atlantis


平面上の n 個の長方形 (軸に平行) が与えられるので,その和集合の面積を求める.
n <= 100.

座標圧縮して塗る.4 隅に ±1 を書いて部分和.

ZOJ 1129: Erdos Numbers


p 個の論文があり,それぞれの著者たちと論文名が与えられる.その後 n 人の名前について Erdos 数 (共著を距離 1 として Erdos からの距離) を求める.
p <= 32,000,n <= 3,000,(登場する異なる著者数) <= 10,000.

行の長さの条件などから,(1 つの論文の著者数) <= 41 (たぶん).
論文と著者を頂点にした二部グラフで BFS すれば,距離の半分が Erdos 数.
人名に空白が入り得るため入力をとるのがやや面倒 (',' が入らないのでそれを利用).

ZOJ 1136: Multiple


N の倍数である正の整数であって,10 進法で書いたとき桁に X[1], ..., X[M] のみが現れる最小の数を求める.存在しなければ 0 を出力.
0 <= N <= 4,999.

N = 0 は例外処理.そうでないときは N 頂点での BFS.mod N で,X[i] に対応する辺を使うと u -> 10u + X[i] となり,昇順に使えば最小が求まる.prev と pree を記録した.

memset の sizeof に違う変数を書いて 1WA.

ZOj 1139: Rectangles


平面上の N 個の長方形 (軸に平行) が与えられるので,他のいずれかの長方形に含まれているものの個数を答える.

N の上限が書いていないが,O(N^2) で調べて通った.

長方形の 4 次元の点とみなせば,いくつに含まれるかを求める部分が領域和になるので, segment tree を動的に作って O(N (log N)^4) で解ける.実行時間は却って長くなった.

いろいろ試すなかで入力の xmax と ymin の順序を何回か間違えた.また,多次元の領域木を書くときは幅は同じかつ 2 の冪にしておかないとサイクリックに回したとき危ない.

ZOJ 1140: Courses


P 個の授業と N 人の生徒がいて,各授業を受けている生徒の集合が与えられる.各授業の代表者を 1 人ずつ選び,それらが被らないようにできるかどうか求める.
P <= 100,N <= 300.

二部グラフであり,最大マッチングが P であればよい.

各種の方法を試したが,実行時間はあまり変わらなかった.

ZOJ 1144: Robbery


W * H のグリッドで強盗が動き回る.時刻 t[i] には [L[i], R[i]] * [T[i], B[i]] には強盗はいなかった,という情報が与えられる (1 <= i <= n,1 <= t[i] <= t).
強盗は単位時刻に高々 1 動ける.W * H 内に居続けることがあり得ないならばそれを指摘.そうでないならば,W * H 内に居続けたと仮定して,いた場所を特定できる時刻とその場所をすべて答える.
1 <= W, H <= 100,1 <= t <= 100,1 <= n <= 100.

時刻と場所をキーとして DP.まず時間を進める方向に行って,時間を戻す方向に行うと可能な場所の候補がすべて求まる.動かなくても良いことに注意.

ZOJ 1146: LC-Display


整数 n を一辺の長さ s の 7-segment で描く.

空白で埋めてから描いていく.7-segment の上手い埋め込み方・描き方が思いつかない.

ZOJ 1149: Dividing


価値 i のマーブルが n[i] 個ある (1 <= i <= 6).価値の和が等しくなるように 2 つの集合にわけられるかどうか判定する.
(n[i] の和) <= 20,000.

いわゆる 0-1-2 ナップサック.n[i] を 1 + 2 + 4 + 8 + ... と残り,と分割する.

価値の和が奇数のときにもそのまま sum / 2 を見てしまい WA.

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 を足した.

ZOJ

ZOJ 1074: To the Max


N * N に整数が並んでいる.長方形領域 (正の面積) の和の最大値を求める.
N <= 100.

行の範囲を固定すると,部分和を作っていけば max { sum[j] - sum[i] | i < j } = max { sum[j] - min { sum[i] | i < j } } であるから,min も作っていけばよい.
O(N^3).

最初,正である限り足していく尺取,という完全に誤りの方針をとってしまった.

ZOJ 1076: Gene Assembly


区間が n 個与えられ,交わらないように最大個数とりたい.そのときの取り方を区間の位置の昇順で番号で出力せよ.
n < 1000.

終点でソートして貪欲.

ZOJ 1078: Palindrom Numbers


palindrom とは b 進法で書いたときに回文になる整数.n が palindrom となる 2 <= b <= 16 をすべて求める.
n < 50,000.

余りを書き並べて判定した.

解がないときの出力を問題文からコピペしたとき,n の部分を 19 にしたままだった.

ZOJ 1082: Stockbroker Grapevine


人が N 人いて,人 u が噂を聞いたとき何分後に人 v に伝わるかが一部の u, v に対して与えられる.1 人だけに新しい噂を伝えて,全員に伝わるまでの時間を最小化し,誰に伝えるべきかとともに答える.不可能ならそれを指摘.

Floyd-Warshall した.誰に伝えるかは最小を選んだら通った.

ZOJ 1086: Octal Fractions


8 進法の小数 (0 以上 1 以下,小数点以下 k 桁) が与えられるので 10 進法で書く.

多倍長割り算だが,常に小数点位置からなので楽.1 を 8 で割っていき,必要なだけ答に加算足していく.k の上限はないと言われているが O(k^2) で通った.
入力に 1 があり得るかよくわからない問題文だが 1 の位をそのままにすることで対応しておいた.

ZOJ 1088: System Overhead


輪に n 人が並び,「最初の 1 人が消される,次の m - 1 が飛ばされる」を繰り返す.最初 2 番目にいる人が最後まで生き残るための最小の m を求める.
3 <= n < 150.

m を決めたとき誰が残るかは,1 人から順に人数を増やして解いていけば O(n) で求まる.m を順に試して計算させたところ n < 150 では m <= 513 で見つかった.

ZOJ 1089: Lotto


k 個の数が与えれるので,その 6 元部分集合を辞書順ですべて列挙する.
6 < k < 13.

bit の nextCombination を書いた.補集合を回すかつ reverse,で辞書順になる.

適当にやると辞書順にならない.計算量に影響がないので next_permutation を使う方法も.

ZOJ 1090: The Circumference of the Circle


三角形の 3 頂点の座標が与えられるので,外接円の周長を求める.

辺の長さを求めて 4RS = abc を用いた.

ZOJ 1091: Knight Moves


8 * 8 のチェス盤で 2 マスが指定されるので,ナイトの動き何回で辿り着けるか求める.

Floyd-Warshall した.辺を張るときは 8^4 回して距離 √5 で判定してみた.

ZOJ 1092: Arbitrage


n 種類の貨幣があり,両替のレートが与えられる.両替は手数料等なく比例.任意の貨幣からスタート可能で,金を増やせるか否か判定する.
n <= 30.

log をとって Bellman-Ford で正閉路の有無を判定.最初はすべてコスト 0 にして,N 周目で更新があるかないか.

ZOJ 1093: Monkey and Banana


n 種類の直方体がそれぞれたくさんある.直方体は 6 通りのうち好きな向きに使えて,積んでいく.積むときに縦も横も真に短くなければならない.作れる最大の高さを求める.
n <= 30.

6n 個用意して,x 昇順 → y 昇順 でソートしておき,O(n^2) の DP.

x 昇順 → y 降順 でソートすると,1 次元上の RMQ をすれば遷移が O(log n) で計算できて O(n log n) になる.この RMQ は BIT で書ける.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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