2017-10

Latest Entries

スポンサーサイト

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

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 であることを見た.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/35-fbfaec96

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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