2017-07

Latest Entries

スポンサーサイト

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

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.

SRM 511 DIV 1

1000 から開き,バグが取れず残り 10 分になりとりあえず 250 を片づけ,1000 に戻ったがあと少しのところで間に合わず.撃墜は 1 成功.

250: Zoo


うさぎとねこがあわせて N 匹いて,全員の身長は異なる.N 匹それぞれに対して,「同じ種類で自分より高いのは何匹か」という情報がある.どの動物がうさぎでどの動物がねこか,のパターンが何通りあるか求める.
N <= 40.

うさぎが x 匹,ねこが y 匹であれば (0, 1, ..., x - 1; 0, 1, ..., y - 1) となるのでこれをソートして入力の vector と比較.一致したとき答に 2^min{x, y} を足せばよい.

500: FiveHundredEleven


511 以下の非負整数が書かれたカードが N 枚あり,2 人でゲームを行う.最初場の数は 0 で,交互に 1 枚ずつカードを使う.カードを使うと場の数に bit の or で足される.カードがなくなるか,511 を作った方が負け.先手勝ちか後手勝ちか答える.
N <= 50.

場の数と,場の数を変えないカードが何枚残っているか,を状態にして DP.場の数を変えるカードはすべて使っていないことからこれで状態が表せることがわかる.計算量は 512 * N * N^2.

場の数を変えないカードを使う,という場合を実装し忘れて WA を出した.

1000: GameOfLifeDivOne


ライフゲームの変種.0, 1 が 1 次元円形上に N 個並ぶ.時間が 1 経つと,各セルはそれと隣の 3 セルのうちの多数派になる.'0', '1', '?' からなる文字列が与えられるので,時間 T が経ったときに少なくとも K 個の 1 があるような '?' の埋め方は何通りあるか求める.
N <= 50,T <= 1,000.

同じものが隣接していれば変わらない.00 と 00 に挟まれた部分は 1 が 1 つずつ減り,11 と 11 に挟まれた部分は 1 が 1 つずつ増え,00 と 11 あるいは 11 と 00 に挟まれた部分は 1 の個数は変わらない.2 個以上同じものが隣接する場所をどこにするかを決めればよい.
円形なのでどこかできる.全体で 0, 1 が交互のケースは特別処理し,2 個以上同じものが隣接しているブロックのうち左端が最も左にあるものの位置と 0/1 で場合分け.それぞれのケースは,最後に作ったブロックの位置と 0/1,時間 T の後の個数,を状態にして DP すればよい.
元から書かれている 0, 1 については,0000..., 1111..., 0101..., 1010... のそれぞれに一致しない箇所の部分和をもっておけば適合するか判定できる.2N くらいまで作っておく.
全体で O(N^5).

SRM 410 DIV 2

練習.

250: ContiguousCacheEasy


n バイトのメモリがある.一度に k バイトキャッシュでき,最初 [0, k - 1] を持っている.addresses[i] に順にアクセスする.このとき新たなキャッシュが必要になったら現在の場所に近い場所を持ってくる.新しく読み込むメモリの合計を求める.

各回に読み込むのは min{(移動量), k}.

500: AddElectricalWires


N 個のノードがあり,その wire での接続関係 (無向単純グラフ) が隣接行列で与えられる.いくつかのノードは main grid に直接繋がっていて,main grid に繋がっている 2 ノードは wire で直接にも間接にも繋がってはいない.この条件を保ちつつ wire を増やすとき最大何本増やせるか.
N <= 50.

main grid に直接繋がっているノードを含む連結成分のサイズを列挙し,それぞれを完全グラフにできるので増やせる辺がわかる.main grid に間接的にも繋がっていないノードたちは最大の連結成分につ繋げるのがよい (nC2 が凸なので).

1000: ClosestRegex


文字列 text と正規表現 regex が与えられる.ここで regex が含む特殊な文字は '*' のみであり,すなわち regex の各単位は「文字 X 1 個にマッチ」「文字 X 0 個以上にマッチ」のいずれかである.text の何文字かを書き換えて regex にマッチするようにしたい.書き換える文字数を最小化した上で,得られる辞書順最小の文字列を求める.
|text| <= 50,|regex| <= 50.

text[x .. $] を regex[y .. $] にマッチさせるための,最小書き換え数とできる辞書順最小の文字列の pair を求めていく.regex[y + 1] == '*' ならば y を 2 つ進められる.text[x] を必要ならば regex[y] に書き換え,次は (x + 1, y) あるいは (x + 1, y + 1) を見ることになる.string を比較するので計算量は O(|text|^2 |regex|).
計算量に余裕があり string を比較できるので,最小値だけ求めてから復元,とするより楽.

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

Codeforces Beta Round #76 Div. 1

手を付けた順は D → E → A → B.E はすぐ書いたものは TLE で一旦放置して最後に解いた.Hack は残り 10 分で部屋の E をすべて落とした.4 問通って 2 位.

A: Frames


Windows のエクスプローラ.n 個のアイコンが 1 行に m 個ずつ並んでいる.a 番目から b 番目までを選択したい.1 回の操作で選択できるのは長方形領域で,二重に選択されると選択が解除される.最小操作回数を求める.
n, m <= 10^9.

場合分け.
・a と b が同じ列にあれば 1 回.
・「a が行の先頭」かつ「b が行の末尾 or b = n」ならば 1 回.
・「a が行の先頭」または「b が行の末尾 or b = n」ならば 2 回.
・a の行の 1 つ下が b の行であれば 2 回.
・a の列の 1 つ左が b の列であれば 2 回 (これのみ縦に区切る).
・その他は 3 回.

4 つ目と 5 つ目を忘れていて pretest で何回か WA を出した.

B: End of Exams


n 個のミルクの瓶があり,それぞれに w 入っていて,これらを m 人で等分したい.同じ瓶からは高々 2 人までに配るとするとき,可能かどうか判定し,可能ならその方法を出力する.
1 <= n <= 50,2 <= m <= 50.

「長さ m の棒が n 本あり,それぞれを高々 2 つの整数長さに分割し,m 人に長さ n ぶんずつ配れるか」という問題として考えられる.
n < m かつ n が d = m - n で割り切れないときを考える.m の分け方として (n, d), (n - 1, d + 1), ... が考えられるが,たとえば (n - 1, d + 1) を使うと n - 1 に対応して長さ 1 が必要になるが 1 は作れないのでこれは使えない,といったようにしていくと,(n - kd, (k + 1)d) しか使えないことがわかる.すると各棒からは d で割り切れない断片は高々 1 つしか生じず,m 人には与えられない.よって不可能.
一方,その他の場合は 1 人目から順番に貪欲に使っていけば可能であることがわかるのでそうする.

コンテスト中は証明をせず,貪欲に配り途中で棒が 3 分割されたら不可能,というコードを出した.

C: Azembler


26 箇所のメモリがある.最初,1 つ目のメモリにある数が入っていてそれを n 倍してどこかに保存したい.他のメモリは最初 0.可能な演算は,x <- kz or x <- ky + z (x, y, z はメモリ,k = 1, 2, 4, 8).最短操作数を求めて操作を 1 つ求める.
1 <= n <= 255.

26 個も使わないことはすぐわかるので,今まで作った数をすべて記憶できているとしてよい.また演算は数を減らさないので,昇順に作っていくとしてよい.これをもとに探索する.
作った数の vector からの map で,最短手数と次に作るべき数,を pair にしてメモ化再帰したら通った.
より単純には,iterative deepning + DFS で見つけることもできる.

D: Flags


白・黒・赤・黄の 4 色からなる 1 * n の旗を作る.満たすべき条件は,
・同じ色は隣接しない.
・白と黄は隣接しない.
・赤と黒は隣接しない.
・黒,白,赤あるいはその逆の順に並ばない.
裏返しを同一視するとき,L <= n <= R において何通りあるか mod 1,000,000,007 で求める.
1 <= L <= R <= 10^9.

行列累乗.直前 2 文字のパターンと,「終了した」という状態を考えれば,n <= N の場合の数がわかる.裏返しを除くには線対称な旗の個数を足して 2 で割ればよいが,線対称で条件を満たす旗は必ず n が奇数で,n = 2m + 1 で線対称な旗が条件を満たすことは,中央までの n = m の旗が条件を満たすことと同値なので,これも数えられる.

E: Lostborn


a[1], ..., a[k] は互いに素.n 以下の正の整数であって,a[1], ..., a[k] のいずれでも割り切れないものの個数を求める.
1 <= n <= 10^13,1 <= k <= 100,1 <= a[i] <= 1,000.

包除原理.ただし愚直に DFS を書くと 100^4 以上回るので間に合わない.
包除原理の DFS を呼ぶとき,x / y / z = x / (y * z) (除算は切り捨て) を用いると最初に N で呼んで割り算で再帰していくことができる (互いに素であることを使っている).よってそれ以降の結果は「n について a の i 番目以降で解く」のような形になるので,小さい値についてのメモ化ができる.a をソートしておけばこれで間に合う.

コンテスト中は,「メモ化」という考えに至らず,n が小さいときに (n, i) に関して直接問題を解く,ということを行った (テーブルのサイズの計算量).素数を並べたケースで間に合うことを確認して提出したが,1 と素数たち,というケースで TLE する様子 (ジャッジデータには入っていないと思われる).a に 1 があれば答 0 なのでその処理は加えるべきだった.

TCO11 Round 2

850 人中 350 人が Round 3 へ進出.
1000 → 250 の順で解いて 500 が時間切れ.Challenge は何もせず.
1000 が落ちたが 250 の速度があってなんとか通過.

250: GuessTheNumberGame


ある整数が 1 から n で割りきれるか否かを 'Y'/'N' の列で表した長さ n の文字列は何通りあるか,mod 1,000,000,007 で求める.
1 <= n <= 10^6.

素因数で決まる.p^e <= n < p^(e+1) ならば,p の肩が 0, 1, ..., e-1 あるいは e 以上,の e + 1 通りに区別されるので,それらの積.

500: STable


s ~ t の文字がすべて異なる文字列 s, t に対して,
・table[i][0] = s[i - 1]
・table[0][j] = t[j - 1]
・table[i][j] = min(table[i - 1][j], table[i][j - 1]) ~ max(table[i - 1][j], table[i][j - 1])
により table を求める.table[|s|][|t|] の位置 pos から 50 文字 (あるいは末尾まで) を求める.
1 <= |s|, |t| <= 30.

table[i - 1][j] と table[i][j - 1] のどちらが小さいかをすべて知れば,(i, j) = (|s|, |t|) から辿って復元できる.
比較結果をメモ化することで,(a, c), (a, d), (b, c), (b, d) の大小を知ったうえで a ~ b と c ~ d を比較したい.ここで,table の異なる場所は文字の集合として異なるので,等しくなければ一方が他方の prefix になることはない.よって (a, b) と (c, d) を pair として比較すればよい.
メモ化されるのは斜めに揃ったところの比較なので,3 乗オーダ.

本番中は table に sort, unique をかけたものとして比較すればよいだろう,と思ってやったが誤りのようだった.

1000: CircuitDesign


二部グラフを平面に描きたい.辺は交差せず,外側を通らないようにする.上下の n 頂点ずつの並べ方が何通りあるか,mod 1,000,000,007 で求める.
n <= 50,(辺数) <= 50.

caterpillar tree (caterpillar forest) の問題.細かい条件をいろいろ処理する.
サイクルがあれば不可能.u の隣接点 v で deg(v) >= 2 なるものの個数を deg'(u) とする.deg'(u) >= 3 ならば不可能.
孤立点は後で任意の位置に挿入できる (場合の数も求まる) ので無視しておく.連結成分は左右を分離するので,各連結成分での場合の数をかけあわせて,並び順を考えればよい.
各連結成分については,基本的には葉の順序に対応する (deg(u) - deg'(u))! の積.さらに,連結成分内に葉でない頂点 (deg(u) >= 2) が 2 個以上あれば,左右の反転で異なるものができるので 2 倍する.

ミスした点は 2 倍できるかどうかの判定.deg' を使ってしまい混乱し,3 頂点の木を反転できるとしてしまった.

Next generation Contest 6

5 時間 10 問.
序盤は,2 問目以降は statistics 見て提出があるものを追いかけた.B (1WA) → D → J → I → A → G → H → C → F が 90 分で終わり,E に 3 時間かけて 11 回目の提出で通った.単独全完で 1 位.
問題文は短く,実装も軽め.典型アルゴリズムという感じの出題が多かったが,ちょっと考えるタイプも多かった.また,似た感じのが何組かあったという印象.

A: Again Lucky Numbers


N 桁の非負整数であって整数 M を文字列として含まないものの個数を mod 10,000,007 で求める.
1 <= N <= 100,1 <= M <= 10^100,(ケース数) <= 1,000.

M を文字列とみて KMP で状態遷移を作って状態数 O(N |M|) の DP.

B: BFS (Binary Fibonacci String)


BFS(0) = "0", BFS(1) = "1",BFS(n) = BFS(n - 2) ~ BFS(n - 1) (n > 1) で定まる文字列 BFS(n) を考える.BFS(N)[i .. j+1] を求める.
0 <= N, i, j <= 2^31 - 1,0 <= j - i <= 10,000,j < |BFS(N)|,(ケース数) <= 100.

長さは Fibonacci 数で,事前にテーブルを作る.n >= 60 で既に長さが 2^32 は超えているので,BFS(n) の代わりに BFS(n - 2) を考えればよい.あとは 1 箇所ずつループを回すか,全体を再帰に投げるか,などで求める.

BFS(n - 2) が先であることを意識せず,N >= 60 のとき単に N = 60 としてしまった.

C: Colorful Eggs


n 個のバスケットに卵が何個かずつ入っていて,卵を追加したり移動させたりの操作が定まっていて毎日行われる).d 日後の各バスケット内の卵の個数を mod 1,000,000,007 で答える.
1 <= n <= 60,1 <= d <= 1,000,000,000,(ケース数) <= 111.

操作による卵の個数の変化は線形.行列累乗.

D: Divisors


d(n) = (n の約数の個数),σ(n) = (n の約数の和) とする.a <= i <= b なる k の倍数 i についての d(i) の総和,σ(i) の総和を求める.
0 < a <= b <= 10^5,0 < k < 2,000,(ケース数) <= 75.

d(n) と σ(n) を事前計算する.素因数が見つかればそれで割り切れるだけ割れば小さい n に帰着できる.√n までみて大丈夫だった.事前計算後は i をすべて見た.

E: Extreme Divisors


d(n) = (n の約数の個数),σ(n) = (n の約数の和) とする.a <= i <= b なる k の倍数 i についての d(i) の総和,σ(i) の総和を mod 2^64 で求める.
0 < a <= b <= 10^12,0 < k < 2,000,(ケース数) <= 75,TL 3 秒.

問題 D の a, b が大きいバージョン.
0 < i <= nk について 2 回解く.
d(n) や σ(n) の和を,約数視点で数える.すなわち,m に対して,nk 以下の k の倍数であって m の倍数でもあるものの個数を f(m) とすれば,f(m) あるいは m f(m) の和を求めればよい.ここで f(m) = floor( n * gcd(k, m) / m) となる.主要なアイデアとして,m が小さいところでは m について和をとり,m が大きいところでは f(m) について和をとる (Riemann 積分と Lebesgue 積分の使い分け,というイメージ).これで √(10^12) 程度の計算量が見える.
割り算して m = kq + r とおく.r で場合分けすれば gcd(k, m) は一定であるから,f(m) から q の範囲が求まる.これで O(k √b) で答が求まるが TLE.
高速化のために,gcd(k, m) が等しい r をまとめて扱う.f(m) から m の範囲が求まったときその範囲で gcd(k, m) = g なる m の個数や m の和を求める部分が厄介だが,サイズ k の配列いくつかで r の個数や r の和を表す部分和をもっておけば解決する.これで O(d(k) √b) になり通る.

TL が厳しく,通ったものも 2.9 秒台だった.手元で d(k) が大きいケースを並べると 4 秒台.行った高速化としては,
・r が 1 個のときに特別処理して定数倍高速化 (O(k √b) で TLE したコードを流用).
・Riemann 積分側で,m をループで回して mod k で適切な r になるかを見るのではなく,r たちの配列を用意.
・「√ くらい」で区切るの定数倍調整.
といったあたり.

TLE 解消後 WA をもらった.これは mod 2^64 をそのまま long long で計算してしまえばよいだろう (出力用には unsigned long long),とだけ思っていたため.x 以上 y 以下の整数の和を求める,という機会があり,2 除がでてくる.(x + y) と (y - x + 1) で 2 で割れる方を先に割る,として解決.

F: Fun with Strings


'a', 'b' からなるある文字列から初めて (1 番目とする),「'a' を "b" に,'b' を "ab" に」という置換を繰り返していったら,N 番目の長さが X,M 番目の長さが Y となった.可能かどうかを判定し,可能なら K 番目の長さを mod 1,000,000,007 で求める.
0 < N, M, X, Y, K < 10^9,N != M,(ケース数) <= 1,000.

最初の 'a' と 'b' の個数を a, b とすれば n 番目の長さは a, b の Fibonacci 係数 1 次式で書けるので,N や M が小さい方の係数より大きい場合は不可能としたのち,連立方程式 (常に full rank) の整数解 (a, b) を求めればよい.
大きい N, M を無視するにあたって,60 以上,などの決め打ちは連立方程式を解くステップでオーバーフローの危険があるので回避した.

G: Great Numbers


10 進法で N 桁の整数であって,桁に 6 以下のみが現れ,どの桁でも割り切れるようなものの個数を mod 1,000,007 で求める.
1 <= N <= 40,(ケース数) <= 40.

桁数,どの桁をもったか,mod 60 で DP.

H: Highest Paid Toll


頂点数 N,辺数 M の重み付き有向グラフが与えられる.s から t まで合計重み p 以下で行くとき,通る辺のうちの最大の重みの最大値を求める.
2 <= N <= 10,000,1 <= M <= 100,000,(ケース数) <= 50.

各辺に対してそれが使えるかどうか調べればよい.s から順方向と t から逆方向に Dijkstra しておけば各辺 O(1) で判定できる.

I: Inhabitants


凸 n 角形が与えられ,その後 Q 個の点が与えられるので,内部 (周上を含む) であるかを判定する.
3 <= n <= 10^5,1 <= Q <= 10,000,(ケース数) <= 10.

凸なので適当な内部の点から見た角度で二分探索できる.ライブラリそのまま.

J: Just Prune The List


2 つの多重集合が与えられるので,それぞれからいくつか取り除いて同一にする.取り除く最小個数を求める.
1 <= (多重集合のサイズ) <= 10,000,(ケース数) <= 100.

set で共通部分を数えて,要素数の和から 2 倍を引いた.

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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