Entries

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

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

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$ 座標の位置をソートして最大の幅の場所を抜ければ良い.
コースの外のカメラは無視することを忘れないようにする.

Timus 1884 - Way to the University (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1884

問題概要

歩くスピードは5km/h,車のスピードは20km/h.
車の幅は2m,長さは5m.道の幅は各車線2mで合計4m.
右から来る車と左から来る車までの距離が与えられる.車の数はそれぞれ300以下.
今の位置から左右に動かす,歩いて道路を横断したいが,途中で止まらず,道路に直交するように歩く.
車に轢かれないような最小の出発時間を求める問題.

解法

車の角に触れるのは可能らしい.
各車に対して,その車がちょうど通りすぎて,角に触れながら移動するための出発時間を列挙する.
それに0を加えたものが答えの候補.
後は,その答えの候補のそれぞれに対して,実際にその時間に出発して車に轢かれないか判定する.
奥の車線の場合,候補は負になり得るが,それは不正なので気をつける.

Timus 1883 - Ent's Birthday (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1883

問題概要

n個 (1000以下) の点が与えられる.
内部および周上にちょうどk点だけ含むような面積が正の凸多角形を1つ求める問題.(10000角形以下でなければいけない)

解法

点をx座標の値でソート,同じx座標はy座標の値でソートして,最初からk個の点を含むような凸包を作ればいい.
x座標の最小のよりもっと小さいところに適当に点をとったりして面積が0にならないようにした.

Timus 1882 - Old Nokia (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1882

問題概要

携帯に登録された,アルファベット順にN人の友人の名前が与えられる.文字数の合計は100000以下.
1つのキーを押すのに1秒かかるとして,N人それぞれの名前を選択するまでに必要な最小時間を求める問題.
最初はアルファベット順で最小の人を選択している.
上キー,下キーを押すと,リストに表示されてるうちで,次の人,前の人に選択を移せる.
リストはサイクリックで,最初の人の前は最後の人,という感じ.
また,文字を入力することができる.
aを入力するのには1秒,bを入力するには2秒,cは3秒,dは1秒,eは2秒,…,zは4秒かかる.問題文の表参照.
文字を追加したら,今まで入力した文字列をプレフィックスとする名前のみ表示される.
その際,選択は,表示されてるうちの辞書順最小の人が選択される.
文字を削除 (最後に入力した文字を1秒で削除できる) すると,リストはもの文字を入力する前の状態に戻るが,選択されている人は変化しない.
文字を入力したときに,表示される人が0人になるような入力は,ボタンを押しても入力できない.そして不快な音がなる.

解法

削除は高々1回しか行う必要はない.
まず,削除せずに上下キーのみで移動する場合,一文字入力して削除して上下キーで移動する場合を全部試す.
後は,一文字入力して,表示される範囲を区切って,同じ操作を再帰的に行う.

Timus 1881 - Long problem statement (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1881

問題概要

n個の単語が与えられる.単語の長さの合計は10000以下.
また,1ページに書くことができる最大の縦幅 (文字数),横幅 (文字数)が与えられる
同じ行に2つ以上の単語を書く場合は,間に半角スペースを一文字挟む必要がある.
1つ単語は複数の行にまたがってはいけない.
できるだけ詰めて書くとして,与えられた単語を順番通りに書くためには何ページ必要かを求める問題.

解法

シミュレーションする.
各単語の文字数を+1,各行にかける文字数を+1するとスペースを挟むことを考えなくてよくなるので少し楽.

Timus 1880 - Psych Up's Eigenvalues (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1880

問題概要

3つの整数列が与えられる.
各整数列は,要素数4000以下で,各要素は全て異なる.
全ての整数列に登場する数字の数を求める問題.

解法

ハッシュなりセットなりマルチセットなりを使って,全体で3回登場した数字をカウントすれば良い.

Timus 1879 - GOV-internship 2 (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1879

問題概要

整数列s1とs2が与えられる.各要素0以上100000以下.
s1の要素数をn1,s2の要素数をn2とする.n1, n2は100000以下.
最初に,s1の各0要素と,s2の各0要素を好きな数字に変更することができる.
s1はサイクリックと考え,各場所から長さn2の連続する部分列をn1個考える.
その部分列と,s2との差を,異なっている文字数とする.(ハミング距離)
その差の和の最小値を求める問題.

解法

すべての要素がすべての要素と当たるので,答えは
 n1*n2 - マッチする文字数の最大値.
マッチする文字数は,
 Σ s1に含まれるkの個数 * s2に含まれるkの個数 (kについての和)
なので,各文字列にある0は全て同じ数字に変えるのが最適で,
 s1に含まれる0は,s2に含まれる最も多い数字に変更.s2に含まれる0は,s1に含まれる最も多い数字に変更.
 s1,s2に含まれる0はすべて同じ数字に変更
だけを試せば良いことがわかる.

Timus 1878 - Rubinchik's Cube (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1878

問題概要

パズル.問題分の図参照.
4枚の板が重なっていて,各板は1回の操作で90度回転できる.透明な部分は透ける.
初期状態が与えられるので,下の図のいずれかになるまでに必要な操作の回数を求める問題.

解法

各板の回転の仕方は4通りしかないので,4^4パターン全部試してみる.

Timus 1877 - Bicycle Codes (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1877

問題概要

4桁の数字を合わせれば開くタイプの鍵を2個持っている.
自転車に鍵をかけるが,奇数日目は1個目の鍵を,偶数日目は2個目の鍵をかける.
泥棒が毎日来て,1日目は0000,2日目は0001,…,と小さい順に試していく.
そのうち自転車が盗まれるかどうかを求める問題.

解法

1個目の鍵が奇数,または,2個目の鍵が偶数,のどちらかならば盗まれる.

Timus 1876 - Centipede's Morning (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1876

問題概要

あるムカデは右足が40本,左足が40本あって,スリッパを履こうとしている.
最初a個の右足用スリッパ,b個の左足用スリッパがある.(a, bは40以上100以下)
まだ履いていない右足があるうちは,右足で1つのスリッパをランダムに選び,
 右足用だったら履く.この操作は1秒かかる.
 左足用だったら,左足でまだスリッパを履いていない足があればそれにパスして履く.この操作は2秒かかる.
 左足用で,もうすべての左足がスリッパを履いていたらスリッパを捨てる.この操作は2秒かかる.
履いていない右足がないなら,右足で1つのスリッパをランダムに選び,
 左足用だったら履く.この操作は1秒かかる
 右足用だったらスリッパを捨てる.この操作は2秒かかる
すべての足にスリッパを履くのにかかる時間の最大値を求める問題.

解法

右足を先に履き終わる場合と左足を先に履き終わる場合の最大値をそれぞれ求めて大きい方を返す.

Timus 1875 - Angry Birds (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1875

問題概要

y軸の正の方向が上,つまり,重力はy軸の負の方向に働く.
5匹の猿の座標が与えられる.x座標y座標共に正.
原点からボールを投げて全ての猿に当てたい.(あたっても軌道は変わらない)
最小で何回ボールを投げればいいか求める問題.
ボールは,x軸方向に等速度,y軸方向に重力の力によって等加速度運動を行う.
原点と2匹の猿が同一直線上にあることはないとする.

解法

原点を通り,上に凸な2次関数を何個書けば点を覆えるかという問題.
原点と2点を選んだ時,2次関数は一意に定まるので,それで当てれる猿を列挙する.
後は,例えばDPして,各部分集合に対応する猿を全部当てるのに必要なボールの数を求める.

Timus 1874 - Football Goal (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1874

問題概要

無限に長い2本の棒が直角に交わっている.
また,長さaの棒と長さbの棒を自由に配置できる.
作れる四角形の最大面積を求める問題.

解法

棒aと無限に長い棒(1つ目)のなす角をA,棒bと無限に長い棒(2つ目)のなす角をBとすると面積は
 ab sin A sin B + 0.5 a^2 sin A cos A + 0.5 b^2 sin B cos B
となる.
各Aに対して3分探索して,その中で各Bに対して3分探索する.

Timus 1873 - GOV Chronicles (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1873

問題概要

Team.GOV (とその前身のAlarm) のヒストリーが与えられる.
メンバーの変更やどんなコンテストに参加したなど.
各登場する人物に何回コンテストに出場したのかを求める問題.

解法

問題文読解.

Appendix

Recent Articles

ブログ内検索

Ads


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