2017-09

Latest Entries

スポンサーサイト

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

POJ

過去に送って通らなかったらしい問題たちに再挑戦.

POJ 2968: Necklace


平面上の N 個の点が与えられるので,それらを中心に円を描く.i 番目と i + 1 番目あるいは 1 番目と N 番目は交わり,その他の組は交わらないように半径 (0 以上 10^4 以内) を決める.外接する距離から 10^(-5) 以内の場合は都合よく判定される.
2 <= N <= 100,-10^3 <= (各座標) <= 10^3.

半径を変数,目標関数を 0 として LP を解かせたら通った.

LP の式 Ax <= b において b に加える微小な値を 1e-6 としたら TLE し,1e-8 としたら WA し,1e-7 としたら通った.原因は不明.TLE は LP が誤差に弱いための無限ループの可能性あり.

POJ 1311: Doing Windows


4 個の長方形があり,サイズは W[i] * H[i] である.これらを縦横の長さが整数であるように相似に拡大あるいは縮小し,あるサイズの長方形に隙間なく敷き詰めることが可能かどうか判定する.

まずサイズを最大公約数で割っておく.長方形が 4 個以下なので,縦または横に割ることで,ある 1 個か 2 個が切り離される配置のみがありうる (5 個だとこれは偽).どちらの場合も拡大比は定まるため,再帰で全部の切り離し方を試せばよい.
計算は 64-bit で通った.

POJ 1508: Skyscraper Floors


F 階建ての建物があり,E 個のエレベーターがある.エレベーター i は Y[i] + k X[i] (k は非負整数) に止まる.A 階から B 階までエレベーターのみで行けるかどうかを判定する.
1 <= F < 50,000,000,0 < E < 100,X[i] > 0,Y[i] >= 0.

エレベーター i, j が同じ階に止まるかは連立方程式を解いて max{Y[i], Y[j]} 以上の最小の解に注目すればわかる.あとは BFS などをすればよい.

b に m の倍数を加えて y (> b) 以上にする際,b += (y - b + m - 1) / m * m; の * m を忘れて WA.また,0 階から F - 1 階が使えるように思える問題文だが,F 階も使える.

POJ 1639: Picnic Planning


いくつかの家と Park があり,それらを結ぶ n 個の距離付きの道がある.何人かの家から車を出し,何人かを連れて Park へ行く.どこかの家で集まって,車を 1 台以外放置して合流することもできる.車の容量は無制限.Park へ行ったら戻れない.Park には高々 s 台の車が入れる.全員が Park へ行くための運転距離の総和の最小値を求める.解の存在は保証されている.
(家の個数) <= 20.

Park の次数が s 以下という制約付きの最小全域木を求めればよい.まず辺をコストでソートし,Park に接続する辺に印をつける.s は必要ならば小さくし,使用を許すちょうど s 個の辺の組み合わせすべてに対して Kruskal 法を行う.

POJ 2124: Crankshaft


N 個の多角形状の十分薄い均一な板が重なっている.重心の座標を求める.
1 <= N <= 100,3 <= (多角形の頂点数) <= 200.

分割したときの重心は座標の加重平均で求まる.符号付き三角形分割をしてよく,三角形は単体なので重心は座標の平均.

-0.0000 出力で WA.

POJ 3164: Command Network


平面上の N 個の点が与えられ,M 個の組 (i, j) に対して点 i から点 j への単方向の道がその距離のコストで作れる.1 番目の点からすべての点へ行けるようにするための最小コストを求める.不可能ならば指摘.
N <= 100,M <= 10,000.

最小根指定有向木.隣接行列で実装して O(N^3).

入ってくる辺で最小コストのものを求める際に,隣接行列の対角も見てしまった.入力時に INF を入れておいても,気にしないで書くと 0 の強連結成分縮約後に対角に 0 が入る.

POJ 3530: A Modular Arithmetic Challenge


正の整数 M, D, L, R に対し,L <= (Dx mod M) <= R なる最小の非負整数 x を求める.存在しなければ指摘.
1 <= M, D, L, R <= 2,000,000,000.

互除法の類似で再帰的に解ける.
R を M - 1 以下し,L > R ならば解なし.D は予め mod M をとってよい.D = 0 のときは L = 0 かで判定.L <= Dx <= R なる x が存在するときはそれが解.
そうでないときは k = floor(L / D) として Dk < L <= R < D(k + 1) である.y = x - k とおいたとき,L - Dk <= (Dy mod M) <= R - Dk なる最小の y を求めればよいが,これは Dy = Ma + b としたときの a の最小化であるため,Ma = Dy - b = D(y - 1) + (D - b) と書いて,D(k + 1) - R <= (Ma mod D) <= D(k + 1) - L なる最小の a を求めることに帰着される.これは元の問題と相似なのでよい.

スポンサーサイト

SRM 525 DIV 1


配点は気にせず,950 → 525 → 300 と解いた.全部通ったが,950 の速度が足りず 4 位.

300: DropCoins


M * N のマス目があり,いくつかのマスにはコインが置かれている.4 方向のいずれかを選び,コインを一斉にその方向へ 1 マス動かすという操作ができる.盤からはみ出たコインは落ちる.盤上のコインをちょうど K 個にするための操作の最小回数を求める.不可能ならば指摘.
1 <= M, N <= 30,1 <= K <= 900.

残せる区画は長方形領域.上下から x0 行,x1 行,左右から y0 行,y1 行削るときの最小操作回数は x0 + x1 + min{x0, x1} + y0 + y1 + min{y0, y1} と求まる.全体で O(M^2N^2).

525: Rumor


N 匹のうさぎがいて,A, B 2 つの噂を流す.最初各うさぎは両方とも知っているか両方とも知っていないかのいずれかである.各うさぎは各日に,知っている噂から 1 つを選び,信用してくれるうさぎすべてに伝達する.信用関係は有向グラフとして与えられる.全員に両方の噂が伝わるまでの最短日数を求める.不可能ならば指摘.
1 <= N <= 16.

各うさぎは同じ噂を 2 回流す必要がないので,行動としては A と B のどちらを優先させて流すかの 2 通り.よって 2^N 通りシミュレーションを行えばよく,N 日あれば終わることから各シミュレーションは O(N^2) で実装できる (拡散を計算する際ビット演算を用いる).

950: MonochromePuzzle


N * N (N は偶数) のマス目があり,各マスは白か黒である.i, j を選び,第 i 行と第 j 行を入れ替え,第 i 列と第 j 列を入れ替える,という操作ができる.目標の盤面は,黒いマスが |i - j| = 1 or i + j = N - 1 or {i, j} = {0 , N / 2 - 1} or {i, j} = {N / 2, N - 1} にあるものであり,これに至るまでの操作の最小回数を求める.不可能ならば指摘.
6 <= N <= 50.

グラフの同型を求める問題.置換が与えられたとき操作の最小回数は N - (巡回の個数).
グラフは N / 2 角柱の形状をしている.まずグラフの無向性と各頂点の次数が 3 であることを確認した.N = 8 はすべての置換を試す (実際は N <= 8 でそうした).N != 8 のとき,ある辺が底面の辺か否かはその辺を含む長さ 4 のサイクルが 1 個か否かで判定できる (適当に書いて O(N^4),存在する辺を辿れば O(N^2)).その結果により長さ N / 2 のサイクルを 2 つ見つけ,どちらのサイクルから回るか,どの場所から回るか,どちら向きに回るか,の組み合わせをすべて試し判定する (適当に書いて O(N^3),自己同型は 2N 個なのでちゃんとやれば O(N^2)).

ある四角形の面の 3 点を固定すれば残りの頂点は決まっていく,という方針でも解ける.

平面で考えており,N / 2 角柱である,という言い換えができなかった.また,自己ループの有無を判定するときに u と v を書き間違えたが,十分に条件を重ねて判定を行っていたため最初に影響はなかった.

COOK16: November Cookoff

初参加.BUYING が解けず 4 完で 3 位.

BUYING: Buying Candles


箱が N 個あり,箱 i には A[i] 個のキャンディーが入っている.ちょうど M 個の箱を選び,キャンディーの個数の合計が K の倍数になるような方法を考える.個数の合計の最小値を求める.不可能ならば指摘.
1 <= M <= N <= 50,000,1 <= K <= 20,1 <= A[i] <= 10^9.

A[i] の小さい順にまず M 個とってしまい,そこから入れ替えることを考える.n 個除いて n 個加えたとすると,n >= 2K - 1 ならば「2K - 1 個の整数が与えられたとき,そのうち K 個を選んで和を K の倍数にできる」という事実を用いると除いたうち K 個と加えたうち K 個を打ち消すことができる.よって n < 2K - 1 を考えればよい.mod K で同じものは大きいものから除き,小さいものから加えるのがよいため,除く候補,加える候補の個数はそれぞれ高々 K(2K - 1) 個となり,O(K^4) の DP で最適値が求まる.
「」内の事実は,「和が K の倍数であるような 2K 個の整数が与えられたとき,」としても同値.K が素数のときに帰着でき,mod K でソートしたのち「i 番目または i + K 番目を選ぶ」と制限して,DP を想像すれば示せる.

除く候補,加える候補を正しく列挙できず WA.最初に vector などに入れるのではなく,大きい順,小さい順に見ていって,長さ K の配列をカウンタとして用いるのが楽だった.
コンテスト中は mod K で同じものをまとまるアイデアしかなく,遅いもの・嘘枝刈りを提出していた.

COLCHAIN: Colorful Chain


link を N 個並べる.各 link は M 色のうちどれかである.どの連続する M + 1 個の link にもすべての色が使われていなければならない.並べ方は何通りあるか mod 1,000,000,007 で求める.
1 <= M < N <= 10^5.

dp[n] = (n 個並べて,最後の M 個に重複を含まない並べ方の個数) として,この配列を計算したい.そうでない並べ方に対しては,最後の k 個で初めて重複を含むような k を状態とすれば,漸化式が立つ.すると dp の各要素は dp の以前の要素かいずれかの状態の初期値として定数時間で求まるので,全体で O(N) にできる.

GRAPLANE: Graph on a Plane


N 頂点の単純グラフが与えられる.各頂点を座標平面上の点に対応させる.各象限には均等に (最大と最小の差が 1 以下) 置かなければならない.辺が座標軸と交わる回数が最小である配置を 1 つ求める.点は座標軸に乗ってはならないが,重なってもよい.原点で交わったら 1 回と数える.
N <= 18,N は偶数.

直線 y = ±x 上に置けばよい.頂点集合 V を部分集合 S[i] (0 <= i < 4) に分割して,カット (S[i], V \ S[i]) のコストの和を最小化すればよい.S[i] のサイズが適切なものは 10,000 個くらいしかないため,まず 2 つの組み合わせを作って最後に合併させた.

MVCOIN: Moving Coins


直線状に並んだ 1,000 マスがあり,N 個のマスにコインが置かれている.コインを 1 つ選び,左に連続して並んでいるコインたちを飛び越した先のマスに動かす,という操作ができる.ただし,1 回で動ける距離は K 以下.最小何回で左に詰められるか求める.
1 <= N <= 1,000,1 <= K <= 1,000.

右から動かして集団をくっつけていくのが最適.長さ s の集団が全体として 1 マス動くのには ceil(s / K) 回かかる.

SUBANAGR: Subanagrams


N 個の文字列が与えられるので,それらのすべての「部分文字列の anagram」になっている,最長の文字列を答える.複数あるならば辞書順最小,空しかないならば指摘.
1 <= N <= 100,1 <= (各文字列の長さ) <= 100,文字はアルファベット小文字.

各文字の出現回数を数えて min をとり,a から順にその個数ずつ並べればよい.

SRM 520 DIV 1

1000 → 250 → 500 と解いた.点数に余裕があったのでちゃんと読まず撃墜 1 ミスしてしまった.全部通って初の 1 位.

250: SRMCodingPhase


SRM に参加する.問題 i (0 <= i < 3) は t 分で解くと points[i] - 2^(i+1) t 点得られる.問題 i を skills[i] 分で解く能力がある.ポイントを luck 点持っていて,1 点につき 1 分解く時間を減らせる (ただし整数分であり,1 分以上はかかる).75 分以内に獲得しうる得点の最大値を求める.

解く問題の集合を決めれば,後ろの問題から順に luck を貪欲に使えばよい.

luck の割り振りを全部試しても間に合う.

500: SRMIntermissionPhase


SRM のスコアボードで,1 位から N 位まで順に各問を提出したかどうかが与えられる.問題 i (0 <= i < 3) は 1 点以上 points[i] 点以下になる.同点がいないものとして,スコアボードが何通りあるかを mod 1,000,000,007 で求める.
points[0] <= 30,000,points[1] <= 60,000,points[2] <= 110,000,N <= 20.

問題の集合に対して,合計 x 点とる方法が何通りかは DP で求まるので,それを利用して N 人分 DP を行えばよい.どちらの DP でも部分和をもっておけば遷移を O(1) で計算できる.

1000: SRMChallengePhase


SRM の撃墜の記録を考える.撃墜には成功か失敗かであり,2 つ以上の撃墜は同時には試みられない.N 人がいる.
・各人は高々 1 回撃墜を試みた.試みたか否かが与えられる.
・各人は高々 1 回撃墜成功された.成功されたか否かが与えられる.
・自分自身には撃墜を試みない.
・自分が撃墜成功された後は撃墜を試みない.
・撃墜失敗は自由に起こる.撃墜成功された後に起こることもある.
撃墜の時間順と成功・失敗の列が何通りあるかを mod 1,000,000,007 で求める.
N <= 2,500.

試みかつ成功された人たちを A,試みかつ成功されていない人たちを B,試みておらずかつ成功された人たちを C とする.撃墜を時間が後のものから順番に考えるとき,A の人が撃墜するときはそれ以前に撃墜されていなければならない.撃墜の対象は A の人かどうかのみが重要であり,A の人でない場合は C の人か失敗 (N - 1 通り) である.
よって,撃墜した人が A かどうか,撃墜された人が A かどうか,の順番を求めて適当な係数をかければよい.前者は DP で求まり,A を a 人,B を b 人既に使ったとき,A を使うならば撃墜されたタイミングが b 通りあるので b をかけて遷移させる.O(N^2).

POJ

POJ 3415: Common Substrings


文字列 A, B に対して,k >= K かつ A[i .. i + k] = B[j .. j + k] なる組 (i, j, k) の個数を求める.
1 <= K <= |A|, |B| <= 100,000,文字はアルファベット.

A ~ '!' ~ B の Suffix Array と高さ配列を構築.長さ k の部分文字列として共通なものは LCP の長さが k 以上で繋がっている各部分に対して,A 由来が a 個,B 由来が b 個であれば a * b 個カウントされる.k の降順に考えれば,Union-Find と同時に a, b も管理していくことができる.
Suffix Array の構築は O((|A| + |B|) (log (|A| + |B|))^2) を用いた.2.5 秒.
スタックを用いて O(|A| + |B|) でも解ける (たぶん).

Yandex.Algorithm 2011 Finals

Onsite と同時に参加.B → C → A で手を付けたが B は解けなかった.A と C は通った.

A: Domino


28 種の標準的なドミノのセットを並べた形状が与えられる (目のみが隠される).これを 2x2 の正方形 7 個に区切ったとき各正方形内では目の数が 4 つ揃っているようなドミノの配置が何通りあり得るか答え,さらにそのうち 1 通りを出力する.
(幅), (高さ) <= 30,解が 1 つ以上存在.

正方形への区切り方は左上から貪欲でよい.正方形への数の割り当て方は 14! / (2!)^7 通りで,最初の出現を順に 0, 1, ..., 7 としてして後で 7! 倍すれば間に合うサイズになるので,あとは探索.

B: Superset


平面上の n 個の格子点が与えられるので,それらを含む m 個の格子点 (m <= 200,000) であって,その中の任意の異なる 2 点 A, B に対して以下のいずれかを満たすようなものを 1 つ求める.
・直線 AB が x 軸または y 軸に平行.
・A と B の bounding box 上 (境界を含む) に A, B 以外の点が存在.
n <= 10,000.

分割統治.中央の縦線を引いて,現れる y 座標の箇所すべてに点を打ってしまえば残りは左右それぞれで満たされればよい.O(n log n) となり足りる.点は set に入れて管理.

定数がゆるい O(n) だろうと思って誤答を投げ続けてしまった.

C: Winning Strategy


ある大学から ICPC finals に無限回参加する.選手は無限に供給されるが,同じ選手は 2 回までしか参加できない.チームは n 人からなる.このうちの i 人が過去参加経験がある場合にメダルを得る確率を p[i] とするとき,派遣戦略を動かしてメダル獲得確率の平均値の最大値を求める.
3 <= n <= 100,0 <= p[0] <= p[1] <= ... <= p[n] <= 1.

平均を考えるので初年度まわりは無視してよく,さらに派遣戦略は周期的になるとしてよい (たぶん).各年度で (過去参加経験あり) - (過去参加経験なし) を足していくことを考えると,この値に対応する -n, ..., -1, 0, 1, ..., n を頂点として x から x + i - (n - i) への重み p[i] の辺があるグラフで最大平均長閉路を求めればよい.O(n^3).

右に行く辺と左に行く辺を選べば閉路が作れることから,i として 2 通り試せば解けることもわかる.

SRM 512 DIV 1

1024 → 256 → 512 と解いて撃墜なし.512 を落とした.

256: MysteriousRestaurant


レストランが N 日間開かれる.M 種類の料理があり,日付と種類により価格が与えられる.初日から連続して毎日 1 つずつ料理を食べるが,i 日目と i + 7 日目の料理は同じでなければならない.与えられる予算内で最大何日続けられるか求める.
N <= 50,M <= 50.

日数を決め打てば,各曜日について最安価な料理を選べばよく,可能かどうか判定できる.それを用いて日数をすべて試すか二分探索.

512: SubFibonacci


Fibonacci 数列とは正の整数の列であって,3 項目以降が前 2 項の和であるもの.長さ 0 以上 2 以下の場合も含める.整数の集合 S があり,
・S から元をいくつかの取り出しある Fibonacci 数列の部分列 (連続でなくてもよい) A を作る
・S の残りの元をいくつか取り出しある Fibonacci 数列の部分列 B を作る
・A ~ B は昇順に並んでいなければならない
という操作によって得られる A ~ B の長さの最大値を求める.
|S| <= 50,(S の元) <= 100,000,000.

S を昇順ソートして区切る場所を N + 1 通り考え,小さい方から A を,大きい方から B を作るとしてよいので問題を分割できる.Fibonacci 数列の部分列について,先頭の項は含まれると考えてよい.そこで,先頭の項と途中の項,途中の項が Fibonacci 数列の何番目にあたるか,をすべて調べる.これらを決めれば Fibonacci 数列は復元できる (標準的な Fibonacci 数は前計算).復元された数列で,先頭の項以上の値がいくつ集合に含まれるかをカウントすればよい.

A として [ 3, 1, 4, 5 ] を許してしまった.[ 3, 4, 5 ] が許されるので間違えやすい.また最初「昇順」を見落としていたのもミスに繋がった.

1024: PickAndDelete


長さ N の正の整数の列 S が与えられるので,適切に並べ替えると各 i で x[i] <= S[i] を満たすような長さ N の正の整数の列 x の個数を mod 1,000,000,007 で求める.
|S| <= 200,(S の元) <= 1,000,000,000.

数えるのは昇順に並べ替えたときに x[i] <= S[i] を満たすもの.S[0] = 0 として N 個の区間 (S[i - 1], S[i]] に分けて考えることができ,このうちの j 番目までで j 個以上選ぶことが条件となる.これで O(N^3) の DP で求まる.

i <= n まで x[i] <= S[i] を満たす長さ n の数列の個数を DP で O(N^2 log N) で求められる.x[i] > S[i] となる最小の i に注目して引いていけばよい.

TCO11 Round 3

350 人中 150 人が Round 4 へ進出.
1000 → 250 の順で解いて,500 が時間切れ.撃墜 1 つ.
1000 が簡単だったが,不安で丁寧にテストした.提出後早めに切り上げれば 500 が間に合ったかもしれない.

250: ArtShift


'B', 'W' からなる長さ N の文字列 sequence に対して N 元の置換を繰り返し作用させるとき,生じる異なる文字列の個数の最大値を求める.
N <= 30.

巡回ごとに考えると,'B' が x 個,'W' が y 個含まれるとき x == 0 or y == 0 ならば 1 通り,そうでなければ x + y 通り生じる.全体では (x, y) たちに分割したときに x + y の lcm を最大化することになる.sequence 内の 'B' を X 個,'W' を Y 個とすると,N の min{X, Y} 個以下への分割でパーツの lcm を最大化すればよい.N の分割数が十分小さいので全探索でよい.

500: PrefixFreeSuperset


'0', '1' からなる文字列の prefix-free な集合 cur が与えられる.cur の superset であって大きさが k であるものの,元の長さの和の最小値を求める.この最小値が 10^18 を超えるならば代わりにそれを指摘.そのような集合が存在しなければ指摘.
|cur| <= 50,(cur の各元の長さ) <= 50,k <= 10^12.

まず木を考えて空いているノードを探す.これは,cur の各元 s と各 x に対して,s[0 .. x] と (s[x] の反転) を結合させたものを候補として,別の cur の元と prefix 関係になっていないものを set に入れてしまえばよい.
空いているノードの「根」はその長さをコストとして集合に追加できる.また,既に追加した長さ c の文字列はコスト 2(c + 1) - c により子 2 つに置き換えることができる (結果として集合のサイズを 1 増やせる).これらの 2 パターンをコストをキーとする priority queue あるいは map で管理すればよい.指数爆発するので見ることになる文字列の長さの個数は十分少なく間に合う上,答が 10^18 を超えることもない.

1000: RowOfColors


h 行 w 列のマス目を k 色で塗る.1 行目は k 色すべてを含まなければならず,各色のマスは連結でなければならない.あり得る 1 行目のパターンの個数として考えられるものの個数を mod 1,000,000,007 で求める.
1 <= h, w, k <= 300.

1 行目の色を順に見ていくときに,初出でスタックに push し,ある色が現れたらそれが top になければならないとし,最後の出現で pop する,と考えると,満たすべき条件はスタックの最大サイズが w 以下であること.どこまで見たかとスタックのサイズをキーにして DP すればよい.

Codeforces Beta Round #77 Div. 1

B → C → E → Hack (4 成功 2 失敗) → A の順でやった.D は考えなかった.全部通って 4 位.

A: Hockey


n 個の禁止文字列と文字列 w が与えられる.w のうち禁止文字列の出現 (大文字小文字無視) と 1 回以上被る場所について,その文字を異なる文字 (大文字小文字は保つ) に書き換える (書き換えは一斉に行う).書き換え後の文字列について,文字 letter が最も多く現れるもの,同じならば辞書順で最小のものを求める.
n <= 100,(文字列の長さ) <= 100.

文字列とのマッチの判定は愚直に.文字ごとに独立に変えてよいので,letter か 'a' か 'b' かにこの優先順で変える.

B: Lucky Numbers


10 進法で書いて 4 と 7 を同数含みその他の数字を含まない正の整数を super lucky と呼ぶ.n 以上の最小の super lucky な整数を求める.
1 <= n <= 10^100000.

まず,n が奇数桁の場合,あるいは 7..74..4 より大きい場合,n の先頭に 0 を付けて桁を増やす.
その後は先頭から 1 桁ずつ,4 を使えるなら 4,使えないなら 7 としていく.下準備として,「ある場所から見ていき最初に 4 (7) と異なる箇所」を配列として持っておけばよい.

別解として,下の桁で負ける可能性は無視して並べて,失敗したら最後に使った 4 を 7 に変えてもう 1 回行う,という方法がある.繰り上がりが 1 回までなので計算量も問題ない (たぶん).

C: Volleyball


頂点数 n,辺数 m の無向グラフ (距離が重み) として表される街がある.各頂点にはタクシーがいて,「合計距離 t まで使えてコスト c」という情報が与えられる.タクシーはいまいる頂点から高々 1 度しか利用できない.出発地点から目標地点までの最小コストを求める.到達不可能ならば指摘.
n <= 1,000,m <= 1,000.

まずは各頂点から Dijkstra を行い全頂点間最短路を求め,各頂点からタクシーの行き先を O(N) 通り試す Dijkstra.

E: Lucky Country


頂点数 n,辺数 m の無向グラフが与えられる.辺を 0 本以上何本か加えて,いずれかの連結成分のサイズを桁が 4 か 7 のみからなる数にしたい.最小本数を求める.不可能ならば指摘.
n <= 100,000,m <= 100,000.

もとのグラフの各連結成分のサイズを求める.これらの中に異なるものは O(√n) 通りしかないので個数制限付きナップサック DP.O(n √n log n) で解いた (丁寧に解析すればこれより小さく抑えられるかもしれない).

h 個まとめたものを考えるとき DP の値に +h ではなく +1 しかしておらず 1WA.

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 は貪欲に使える.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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