Entries

スポンサーサイト (この記事を編集する[管理者用])

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

SPOJ 16282 - Horace and his primes [TAP2013H] (この記事を編集する[管理者用])

Source

SPOJ 16282 [TAP2013H]
Argentinian Programming Tournament 2013

問題概要

正整数 $n$ に対して,$f(n)$ を $n$ を割り切る素数の和で定義する.
$n$ を $f(n)$ に置き換えていく手順を繰り返すといずれ $n$ は素数になる.
$n$ から始めた時,素数になるまでに必要な手順の数 $+1$ を $g(n)$ とする.
$P$ 個のテストケースが与えられる.
各テストケースでは $A \leq n \leq B$ かつ $g(n) = K$ を満たす $n$ の個数を求める.
$1 \leq P \leq 10^5$
$2 \leq A \leq B \leq 10^6$
$1 \leq K \leq 10^6$

解法

$g(n)$ の最大値は $12$ 程度なので,$1\leq K \leq 12$ に対して,$g(n)=K$ となる $x$ 以下の $n$ の数を前計算しておく.
$f(n)$ の値は篩っぽく求めて,$n > f(n)$ なので,$g(n)$ の値はDPで計算できる.

Timus 1998 - The old Padawan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1998

問題概要

$n$ 個の石の重さ $w_1,w_2,\ldots,w_n$ が与えられる.
これらの石を順番に空中に浮かすお仕事を行う.
$1$ 秒ごとに $1$ 個の石を空中に浮かべることができる.(まだ浮かべていないうち,番号の若い石から浮かべていく)
ただし,悪友が $m$ 回邪魔してくる.
邪魔してくるタイミングはわかっており, $t_1, t_2, \ldots, t_m$ 秒目に邪魔してくる.
邪魔されると,その秒は石を浮かべることができず,更に,浮かべた石のうち新しい方から
 落とした石の重さが $k$ を厳密に超えるまで(もしくは浮かんでいる石がなくなるまで)
石が落とされる.
全ての石を浮かべるまでにかかる時間を求める問題.
全ての邪魔が行われる前に浮かべ終わることもある.
$1 \leq n, m \leq 10^5$
$1 \leq w_i \leq 10^4$
$1 \leq k \leq 10^9$
$1 \leq t_1 < t_2 \cdots t_m \leq 10^9$ $(t_i < t_{i+1})$

解法

まず,どの段階で邪魔されたらいくつ石が落とされるかをしゃくとりメソッドか二分探索などを用いて求めておく.
後は,イベントが起こるまでの時間を端折りつつシミュレーションすれば良い.

Timus 1997 - Those are not the droids you're looking for (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1997

問題概要

とある店に客が入ってきた,出て行ったというログが $n$ 個与えられる.
どの客が入ってきて,出て行ったかは分からないが,その時間 $t_i$ と,入ってきたのか出て行ったのかがわかる.
すべての客は,$a$ 秒以上滞在するか,$b$ 秒以下しか滞在しないかのどちらかである.
また,必ず $1$ 秒以上滞在する.
また,ログをとる前にいた客や,ログを取った後にいた客などはいない.
ログに矛盾がないかを調べ,矛盾がないなら各客の滞在した時間帯のうち,考えられるものを $1$ つ出力する問題.
$2 \leq n \leq 1000$
$1 \leq a,b,t_i \leq 10^9$
$b+1 < a$

解法

入ってきた回数,出て行った回数が一致しないなら矛盾.
後は,それぞれ入ってきたログと出て行くログが対応付けられるかどうかを調べて2分グラフの最大マッチング.

Timus 1996 - Cipher Message 3 (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1996

問題概要

$n$ 個のバイト($8$ ビット)からなる列 $A$ と,$m$ 個のバイトからなる列 $B$ が与えられる.
何箇所か $A$ の要素のうち最下位ビットを書き換えて良い.
そうして,$A$ の連続する部分バイト列で, $B$ と一致する部分を作りたい.
書き換える最小ビット数と,それで一致させることができる場所を求める問題.
場所は複数あるなら,一番最初のものを求める.
$1 \leq n, m \leq 250000$

解法

$m > n$ なら不可能.
上位 $7$ ビットは全部一致しなければならない.
一致する場所は,ローリングハッシュやKMPを使って求める.
各場所で何文字置き換えなければいけないかはFFTすれば良い.
例えば,$B$ を逆順にして,最下位ビットが $0$ なら $-1$ とみなして,$1$ なら $1$ とみなすなどとすれば,$3$ 回のFFT($A$ で $1$ 回,$B$ で $1$ 回,逆変換 $1$ 回)で計算できる.
一致する場所は $1$,一致しない場所は $-1$ が出てくる.

Timus 1995 - Illegal spices (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1995

問題概要

$n$ 個の荷物があって,順番に重さを量る.
それぞれの荷物の重さ $w_i$ は正整数.
$2$ 個目以降の荷物は,今まで量った荷物で,より軽いものの割合が $p$ %以上あるなら破棄する.
破棄された荷物の数はちょうど $k$ 個であった.
$n,k,p$が与えられるので,重さの総和の最小値と,それを満たす $w_1,w_2,\ldots,w_n$ を $1$ つ求める問題.
$1 \leq k < n \leq 10^5$
$1 \leq p \leq 100$

解法

最初 $n-k$ 個の荷物は全部重さを $1$ にして,最後の $k$ 個は
 前の荷物と同じ重さで破棄されるなら,そうする
 そうでなければ,前の荷物の重さ + 1
とすれば良い.
重さの総和は32ビットに収まらないことに注意.

Timus 1994 - The Emperor's plan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1994

問題概要

$n$ 人の議員の中に $k$ 人のスパイが紛れ込んでいる.
各ターン以下の行動を行った時,最終的に残るスパイではない議員の人数の期待値の最大値を求める問題.
 1. 各スパイが,スパイでない議員を $1$ 人ずつ殺す
 2. 好きな人数を選び,その人数だけ議員をランダムに選び,議員資格を剥奪する
スパイがいなくなるか,スパイしかいなくなると操作を終わる.
議員資格が無いスパイは活動できない.
$1 \leq n \leq 200$
$1 \leq k \leq \min(20, n)$

解法

$n,k$ を状態にしてDPする.

Timus 1993 - This cheeseburger you don't need (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1993

問題概要

主語,動詞,目的語のみからなる文が幾つか","区切りで与えられる.
主語は()で,動詞は[]で,目的語は{}で囲まれている.
最初の文の最初の文字だけアルファベット大文字で,他のアルファベットは小文字.
ただし,","の後には主語,動詞,目的語以外が挿入されている可能性がある.(カッコで囲まれていない)
それぞれの文を目的語,主語,動詞の順番に並び替えて,最初の文の最初の文字だけ大文字で田を小文字で出力する問題.
文字列の長さは $100$ 以下.

解法

やるだけ.

Timus 1992 - CVS (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1992

問題概要

クエリが与えられるのでそれをこなす問題.
最初クローン $1$ のみがいて,クローンを作った順に $2,3,\ldots$ と番号を付ける.
クエリは以下の $5$ 種類がある.
 learn $c_i$ $p_i$ : クローン $c_i$ が授業 $p_i$ を学ぶ
 rollback $c_i$ : クローン $c_i$ が最後に受けた授業を忘れる
 relearn $c_i$ : クローン $c_i$ が最後に行ったrollbackを忘れる
 clone $c_i$ : クローン $c_i$ と全く同じ状況を持つクローンを新しく作る
 check $c_i$ : クローン $c_i$ が最後に受けた授業を出力する(受けてなければbasicと出力する)
授業を新しく受けた場合,rollbackしてたログは全て削除されrelearnできなくなる.
クエリの数は $5 \times 10^5$ 以下.

解法

クエリ先読みできるので,クエリをクローンの種類 $c_i$ 別に分けておく.
クローンが新しく作られない場合は,スタックとrollbackを何回行われたかを覚えておけば良い.
また,クエリを逆に遡ることは簡単なので,新しくクローンが作られたときは,そのクローンに対するクエリを処理して,逆にさかのぼって戻ってきて,もともとのクローンの処理に戻るといった感じのDFSをすれば良い.
永続データ構造っぽくやっても良い.

Timus 1991 - The battle near the swamp (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1991

問題概要

$n$ 個の場所のそれぞれに $k$ 体のロボットを配置した.
敵対勢力が,場所 $i$ に爆弾を $a_i$ 個送り込んだ.
爆弾 $1$ 個につき,ロボットを $1$ 体破壊できる.
使われなかった爆弾の数と,生き残ったロボットの総数を求める問題.
$1 \leq n, k \leq 10^4$
$0 \leq a_i \leq 10^5$

解法

各場所別々に求めて足す.やるだけ.

Timus 1990 - Podracing (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1990

問題概要

レースのコースが与えられる.
車は $x$ 軸に平行な長さ $W$ の線分として,回転はできず自由に平行移動できる.
スタートからゴールできる最大の $W$ を求める問題.
コースは,左端を表す頂点数 $n$ 折れ線と右端を表す頂点数 $m$ の折れ線が与えられる.
それぞれの折れ線は,$y$ 座標方向に厳密に増え,互いに触れたり交わらない.
また,最初の点と最後の点の $y$ 座標の値は一致しており,そこがスタートライン,ゴールラインである.
スタートラインのどこからスタートしてもよく,ゴールラインのどこにゴールしても良い.
また, $q$ 個のカメラの位置が与えられる.カメラはコースの中か外とかはわからない.
車はカメラにあたってはいけない.
$2 \leq n,m \leq 10^5$
$0 \leq q \leq 10^5$
座標の絶対値は$10^9$以下

解法

折れ線の頂点,カメラのある位置の全ての $y$ 座標について,それを通過できる最大の車幅を求める.
それは,その $y$ 座標での障害物の $x$ 座標の位置をソートして最大の幅の場所を抜ければ良い.
コースの外のカメラは無視することを忘れないようにする.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。