2017-09

Latest Entries

スポンサーサイト

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

SRM 509 DIV 1

1000 → 250 → 500 の順に解いた.
Challenge が始まると 500 がたくさん落ちていき,自分のも落とされる頃に 250 で 1 つ落とした.
1000 が単独正解で 2 位.

250: LuckyRemainder


整数 X に対して, X の桁の部分集合を消して詰めたもの全体を足した数を 9 で割った余りを求める.
X は文字列で与えられる.

mod 9 なので桁の和だけ見ればよい.長さ N として各桁は 2^(N-1) 回ずつ加算される.

500: PalindromizationDiv1


文字列に操作をして回文にしたい.操作は,
・文字 c を挿入
・文字 c を削除
・文字 c1 を文字 c2 に変更
のいずれかの形で,コストとともに与えれる.最小コストを求める.
(文字列の長さ) <= 50,(操作の個数) <= 50,(各操作のコスト) <= 100,000,考える文字はアルファベット小文字.

番兵 26 を用意して V = 27 文字で考えれば,挿入・削除・変更は統一的に扱える.
元の文字列を S,その長さ N として,状態を,(文字 u) ~ S[a .. b+1] ~ (文字 v) の O(N^2 V^2) 通りとして,それを回文にするための最小コストを Dijkstra で求める.遷移は,
・u = v = 26 で b - a <= 0 ならば終わり
・u = v のとき u = v = 26 にする
・u = 26 のとき u = S[a] にして a を増やす.v = 26 も同様.
・u や v をコストを使って変更.
の O(V) 個.やや計算量がきつそうだが 1 秒かかっていなかった.

状態を a, b のみにして DP で書くこともできる.ただし最初に Floyd-Warshall を回す.

本番は,Floyd-Warshall を忘れて再提出したが,そもそも add と erase を同じものとして認識していた (番兵を考えれば順序が逆の存在であることがわかる).
本番後においては,u = v のとき u = v = (任意の文字) としていて 1 回落とした.

1000: NumberLabyrinthDiv1


座標 (0, 0) から座標 (xFinish, yFinish) に行きたい.N 個の点 (X[i], Y[i]) には正の整数 val[i] が書かれていて,数が書かれていないマスのうち K 個まで選んで好きな正の整数を書ける.移動は,d が書かれているときに x 座標または y 座標を +d または -d した点へのジャンプのみが可能.
ジャンプの長さの合計が最小になるような行き方のみを考える.ジャンプの仕方が異なるものを違う行き方と数えるとして,何通りの行き方があるか mod 1,000,000,009 で求める.
0 <= N <= 40,1 <= X[i], Y[i], val[i], xFinish, yFinish <= 1,000,000,0 <= K <= 10,(X[i], Y[i]) たちと (xFinish, yFinish) はすべて異なる座標.

両方の座標を正にしなければ既に書かれている数を使ったりゴールしたりできないので,K <= 1 のときは不可能.
一方 K >= 2 のときは (xFinish, 0) 経由でゴールできるので,最短経路のためには座標を減らせない.よって (X[i], Y[i]) たちを pair でソートすれば,使いうる順番が定まる.
「地点 i にいて,後 k 回数を書ける」に至る場合の数を,(地点 i から地点 j まで k 回ちょうど数を書いて進む,ただし i < j' < j なる地点 j' は通らないような方法の数) を用いて求められる.
これは包除しつつな DP で,(i から他を通らず j' に行く) * (j' から他を気にせず j に行く) を除くイメージ.ただし k の要素があるので,これについても和をとる.
主に行う計算は (今いるところから k 回のジャンプを作って (x, y) 進む場合の数) だが,x 方向に何回進むかでループを回して二項係数を使えばこれは O(k) で求まる.
全体の計算量は O(N^3 K^2 + max{(座標)}).最も深いところで 64bit の掛け算と % を行っているが,1/12 の定数倍があり余裕で,実際は mod での逆元を求めたりするパートが時間を食っていた.畳み込みっぽい計算があるので実は O(N^3 K log K + N^2 K^2 + max{(座標)}) にできる (たぶん).

最初は K <= 1 でも可能な気がしていた.サンプルに K >= 2 のケースしかなく K >= 2 から実装したが,それを終えていざ K = 1 を書こうとしたときに無理なことに気付いた.K = 1 で座標に 0 が許されていたならば,最初のジャンプを選んだうえであとは Dijkstra して最短路 DAG 上で DP すればよい (たぶん).ただし座標に 0 があると K >= 2 で最短路長についての議論が危うい.

SRM 508 DIV 1

1000 → 250 → 500 の順に解いた.
3 完して 2 位.
1000 の実装中にマウスが効かなくなり電池切れが判明.こういうどうでもいいタイムロスはなくそう.
撃墜は同じ人に 1 失敗 1 成功.失敗原因は写して実行させたとき初期化を忘れたこと.

250: DivideAndShift


m mod n を (m + 1) mod n か (m - 1) mod n か m mod n/p (p は n の素因数) にする操作ができる.
M mod N を 1 mod (何か) にするための最小の操作回数を求める.
1 <= M <= N <= 1,000,000.

±1 をするのは最後だけでよい.
メモ化再帰で (N の約数) くらい呼ばれる.

±1 する必要をもう少し感じてしまったので無駄なコードが紛れた.

500: YetAnotherORProblem


長さ N の数列 R が与えられるので,
0 <= a[i] <= R[i] かつ a[0] + ... + a[N-1] = a[0] | ... | a[N-1]
なる数列 a が何通りあるか,mod 1,000,000,009 で求める.
2 <= N <= 10,1 <= R[i] <= 10^18.

言い換えれば,各ビットについて立っているのが高々 1 つ.
上の桁から作る DP.
状態として,自由に立たせられるか R[i] の制約が生きているかを覚えればいいので 2^N.
R[i] のビットが 1 かつビットを立てなかった,というときに自由化.

1000: BarbarianInvasion2


凸 M 角形の周上に等間隔に 1,000,000! 人がいる.内部に街が N 個.
人を N 個のサイズが等しいグループに分け,向かう街を 1 つずつ指定.
人と向かう街の距離の最大値を最小化する.
M <= 50,N <= 5.

1,000,000! は無限としてよい.
答を決め打って二分探索.
R を決めたとき,周上で各街から距離 R 以下な部分かどうかは,
円と直線の交点たちで区切った領域では等しい (ので判定時に適当に中点をとってよい).
周長の 1/N がちゃんと送れるかは最大流で求まる.
頂点は O(2^N) 個にまとめることもできるが,それをしなくても通った.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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