2017-08

Latest Entries

スポンサーサイト

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

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 して絵を描く.最初は答はスペースで埋め,絵を描くときは手抜いて長方形領域全体を見る実装にした.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/10-ad895300

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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