Entries

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

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

SRM483 DIV1 参加記録 (この記事を編集する[管理者用])

2010年09月26日01時02分から.

Assignment

寝過ごして5分遅れぐらいで参加.
日本人1人部屋率が高くて寂しい.

EASY

小数点以下6桁の数字Fと1000以下の整数LIMが与えられる.
 A/B (ただし A < B <= LIM)
の小数表示とFと何桁まで合ってるか調べる.
最もたくさんの桁数があっているA, Bの組と,桁数を求める問題.
複数回があるならBが最小のもの,その中でAが最小のものを求める.

5分ぐらい遅れたのに,誰も提出してない,難しいらしい!
問題文が結構ごちゃごちゃ書いてる気がする.
頑張って読む.
全部試すだけで良いのでは.
あれ,難しくないじゃん,書く.
がりがり.
ちょっとバグる.
すぐ直る.
提出.
あれ,点数低い,意外と時間かかってる….
問題文が長いのと,意外と実装が手間取るせいか.
てか,900ptがすごい高い点数で何人か提出してるんだけど….
でも,順番通りMEDIUMに行く.こういうときHARDに行くと後悔するはず.というか昔後悔した.

MEDIUM

50人以下の人が直線上に並んでいて,それぞれの人のHPと攻撃力が与えられる.
何人か選んで,k番目の人を選んだら,
 i番目の人のHPを floor(攻撃力[k] / 2^|i-k|) だけ減らす.
最小で何人選べば,全員のHPを0以下にできるか求める問題.できないならそれを指摘する.
HPと攻撃力は500以下.

問題文がごちゃごちゃしてる.
50人….
greedyで行ける…ような気はしない.
全探索で,効率的に枝刈ったら…,オーダーの落ちる枝刈りができない限り無理,TopCoderらしくない.
どうやるの?
全くわからない….
あれ,HPと攻撃力が500以下だ.なんで小さいの?
高々隣9マスしかダメージが通らない!
19ビットぐらい覚えておく感じのビットDPで行けるんじゃない?
いけそう.
メモリは51*2^19*4 = 107MBぐらい…ぇ.
intで保持する必要はないか….
いや,隣8マスまでだ.17ビットで.51*2^17*4だから大丈夫,
書く.
うりゃー.
書いた.サンプル通過.
サブミット.

HARD

重さ1以上2000以下のアイテムが2000個以下ある.
船に載せることのできる上限の重さがある.
全てのアイテムを運びたい.
greedyに載せる方法を取る.つまり,
 まだ運んでないアイテムで,船に載せれるアイテムの中で,最も重いものから詰め込んでいく.
船は最大でK往復しかできない.
無事全部のアイテムを運ぶことができる船の上限の重さの最小値を求める問題.

900点なので簡単なはず.
凄い速く,とても多くの人が解いているので簡単なはず.
てか,これに時間かけると致命傷になりそう.
問題を読む.
ぎゃー,予想してたけど問題文長い.
読んだ.
2分探索でいいんじゃね?
書く.書いた.segmentation fault.あれ.
うーん.
配列の範囲外アクセスしてるところ発見,修正.
あれ,seg. fault治らない….
なんで,なんで?
コンパイルエラーでてるじゃん…,コンパイルできてなかった.
今度は,全部の答えが1だけずれる.
なにこれ….
1だけ最後に修正して送ればいいか?
いや,そんなことしたら落ちる…,原因を追求すべき.
うーん,どこだどこだ.
1箇所枝刈りの等号が抜けてた.てか枝刈りしなくていいでしょ,消す.
サイズ高々2000だし,余裕なはず.
通った.サブミット.
最大ケース試す.間に合う.

Challenge

見てるだけでした.

System tests

HARDが続々落ちてるので怪しいと思ったらHARD落ちた.
単調性が成り立たないので2分探索できない.なるほど.それはそうだ.なぜ気づかない.
一度間違えてしまったとしても,間違いに気づくかもしれなかったポイント:
 1. rng先生とpetr先生の苦戦度合いを見る
 2. サイズがやたら小さかったこと.もっと早くできるのに愚直に書いて間に合うのが怪しい
で,解法は,2分探索の値から2000ぐらい下まで調べれば良いので,愚直に書いたら2000^3で間に合わないようになってる.

SPOJ 7322 - Prime Pattern [CHEFJUN] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2009
SPOJ 7322 [CHEFJUN]

問題概要

2次元に問題文の図のようにぐるぐると数字を小さい方から書いていく.
ある座標が与えられるので,そこから一番近い素数が書かれたマスまでの距離を求める問題.
距離はマンハッタン距離.
座標の絶対値は2000000以下.

解法

近くの数字から素数かどうか判定する.

SPOJ 7231 - Homework [HOMEW] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2009
SPOJ 7231 [HOMEW]

問題概要

10^18以下の自然数Nが与えられる.
 √N = A √B
という形でAを最大化する.
AとBを出力する問題.

解法

素因数分解する.

SPOJ 7212 - Find String Roots [FINDSR] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2009
SPOJ 7212 [FINDSR]

問題概要

長さ100000以下の文字列Sが与えられる.
文字列Xをn回繰り返すとSになるようなXが存在する最大のnを求める問題.

解法

nは長さの約数なので,nを決めつけて全部調べる.

SPOJ 7192 - Integral Maximization [INTEGMAX] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2008
SPOJ 7192 [INTEGMAX]

問題概要

x座標とy座標がN個与えられる.
N個の座標同士を自由にペアにして良い時,問題文の図で表されるような図形(できる折れ線とx座標で囲まれるような図形)の面積の最大値を求める問題.
Nは10000以下.

解法

各x座標に,高さが1大きいy座標を割り当てると,面積がどれだけ増えるかは簡単に計算できる.
後は増分が大きいものからy座標の大きい物を割り当てればよい.

SPOJ 7190 - Guess the Number [GUESSTHE] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2008
SPOJ 7190 [GUESSTHE]

問題概要

YとNからなる20文字以下の文字列が与えられる.
以下の条件を満たす最小の正整数を求める問題.
 k文字目がYならばkの倍数
 k文字目がNならばkの倍数ではない
存在しないならそれを指摘する.

解法

a,b,c,...文字目がYならばLCM(a,b,c,...)倍じゃければならない.
X=LCM(a,b,c,...)として,d文字目がNでXがNで割り切れるならば答えは存在しない.
そうでなければ答えが存在するので,X, 2X, 3X,...が条件をみたすか調べていく.

SPOJ 7169 - Pizza [EGYPIZZA] (この記事を編集する[管理者用])

Source

Croatian Highschool Competitions in Informatics 2004
SPOJ 7169 [EGYPIZZA]

問題概要

N人の友達が食べたいピザの量が与えられている.Nは10000以下.
ピザの量は1/4, 1/2, 3/4のどれかである.
ただし,細切れになっていてはいけなくて,1つのピザ(大きさ1)を分割して構成する.
必要なピザの枚数の最小値を求める問題.

解法

greedy.
3/4のピザを作って余ったのを1/4を欲しがっている人に割り当てる.
1/2のピザを作って余ったのを1/2を欲しがっている人に割り当てて,もういなければ1/4を2個にする.
後は1/4を欲しがっている人(残っていれば)を処理する.

SPOJ 7132 - Headshot [HEADSHOT] (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northeastern Europe - 2009/2010 (NEERC 2009)
LiveArchive 4596
SPOJ 7132 [HEADSHOT]

問題概要

ロシアンルーレット.
最初に弾装に入ってる弾の状態が与えられる.
相手が不発だったとき,自分は,
 そのまま打つ
 ランダムに回転してから打つ
のどちらが弾が出る確率が小さいかを求める問題.等しいならそう答える.
弾装の容量の最大値は100まで.

解法

やるだけ.

SPOJ 7102 - Doing The Word Wrap [DTWW] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2007
SPOJ 7102 [DTWW]

問題概要

N単語の文章が与えられる.
単語の間で改行して良い.改行しないなら1つのスペースで区切る.
最大で使って良い行数Lが与えられる.
1行の文字数の最大値の最小値を求める問題.
Nは10^5以下,Lは10^8以下.

解法

2分探索.

Aizu 0213 - Subdivide The Land (土地分割) (この記事を編集する[管理者用])

Source

PC Koshien 2009, 2009-11-14 (パソコン甲子園2009)
Aizu 0213

問題概要

10*10以下のマスのいくつかの長方形の領域に分けた.
各領域に属する場所が1マス,その領域の面積が与えられるので,領域を復元する問題.
答えがない場合,複数ある場合はそれを指摘する.
領域の数は15以下.

解法

全探索 + 枝刈り.
UVa 11846 (blog) と同じような問題.

UVa 11848 - Cargo Trains (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11848

問題概要

ノード数100以下のグラフが与えられる.
枝には運輸会社Aのと,運輸会社Bのものがあって,それぞれ通るのに必要なコストが定められている.
ある場所からある場所に移動する最小コストを求める問題.
ただし,クエリは10000個以下与えられて,それぞれ0以上1以下のパラメータaが指定されている.
2つのノード間に1つの運輸会社しか枝がない場合はそのコストを,
2つの運輸会社が両方枝がある場合は, 運輸会社Aのコスト*a + 運輸会社Bのコスト*(1-a) を払わないといけない.
辿りつけることは保証されている.

解法

クエリの数だけグラフつくり直してダイクストラしても大丈夫だった.

UVa 11847 - Cut the Silver Bar (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11847

問題概要

長さnの銀の棒がある.
n日の間,毎日,長さ1だけある人に渡す.
ただし,ちょうど長さk分だけ渡して,長さk-1分返してもらうことも可能.
最小で,何回カットすれば,毎日渡すことができるか.

解法

長さ1,2,4,8,16,...とすればいいので,2進数での桁数を数える.

UVa 11846 - Finding Seats Again (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11846

問題概要

20*20以下のマスのいくつかに数字が書かれている.
長方形の領域に分けて,各領域には,数字の書かれているマスはちょうど1個であり,その面積はその数字と等しくしたい.
そのような分け方を1つ求める問題.

解法

枝刈り全探索.

UVa 11845 - Preferential Romance (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11845

問題概要

 A > B > C > D > E
と言った感じの規則がいくつか与えられる.
 それを満たす並び替えがあるか.
 上の形式で不等号を1個だけ消すと,矛盾ない並び替えがあるか.
 それともそれでも不可能か.
を判定する問題.出てくる要素の数は100個以下.
(ただし,同じ人のA > Bが複数出てきたら,同時に消しても良い?)

解法

どの不等号を消すか全部試して,トポロジカルソート.

UVa 11844 - The Melding Plague (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11844

問題概要

A→Bという形で規則1000個以下が与えられ,毎ターン左の物質が右の物質に変化する.
最初の物質の量と,目標の物質の量が与えられるので,それを達成する最小ターン数を求める問題.
ただし,nターン以下で達成できなければそれを指摘する.(nは1000以下)
また,
 A→B
 A→C (BとCは異なる)
というルールが両方存在するなら,それを指摘する.

解法

実際にシミュレーションするだけ.
 A→B
 A→B
と複数あっても,それは問題ないことに注意.

UVa 11843 - Guessing Game (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11843

問題概要

相手が1~Nの中から選んだ数字を当てるゲームをする.
自分は1つ数字を言い,それより大きいか小さいかあたったか教えてもらえる.
ただし,大きいとK回言われた時点で負け.
相手が選んだ数字にかかわらず,負けないように,数字を当てるための最小回数を求める問題.
Nは1000以下,Kは20以下.

解法

DP.状態は残りの可能性のある数字の幅と大きいと言われても良い回数,でやった.

UVa 11842 - Flatland (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11842

問題概要

2次元平面の長方形上を100人以下の人が同じスピードで歩いている.
長方形の端にきたら死ぬ.
また,2人がぶつかると,互いに反射したように向きを変える.
3人以上が同時にぶつかると,その場でぶつかった人が全員死ぬ.
最後に死ぬ人の名前を求める問題.同時に死ぬなら辞書順で最も遅い人の名前を返す.

解法

シミュレーションした.
直近の,淵にたどり着く or 衝突が起こるまでの時間を求めて,それだけ時間を進めて処理する,というのを繰り返す.
ぶつかって跳ね返る処理は,互いに移動方向を交換するだけで良い.

UVa 11841 - Y-game (この記事を編集する[管理者用])

Source

XXIV Colombian Programming Contest (2010-09-19) (blog)
UVa 11841

問題概要

サイズ20以下の三角形の形をしたグリッドが与えられる.
与えられた石からなる連結成分で,外周の辺を全部含むものが存在するかどうかを調べる問題.

解法

座標の差の絶対値の和が2のものがつながっている.
union findでつなげて,それぞれの座標が0になるものが存在してるかどうかを調べた.
サイズが0の入力もあるので注意.

XXIV Colombian Programming Contest (この記事を編集する[管理者用])

2010年09月19日18時から5時間,8問.
[ Link ]

問題がいろいろ読みにくかった.
取り敢えず全部解いた.
問題別.

・問題A
unionして各軸に乗っている領域があるかどうか調べた.
・問題B
愚直にシミュレーションした.
直近のイベントが起こる時間を調べて移動させる,を繰り返す.
ミラー反射は目的地の位置を入れ替えることによってできる.
名前でソートするのを忘れない.
バブルソートでミスってるとか悲しすぎた….
・問題C
単なるDP.
・問題D
やるだけ.
同じ変換規則が2つ以上あるかもしれないけど,それはvalidなのに1回やられた.
・問題E
問題文が意味不明だった.
preferenceの定義をちゃんと書いて欲しい.
どうやら,1つのブロックを消せるのではなく,1個の不等号を消せるらしい.
さらに,
 A > B > C > D → A > B, C > D
とかになるのであって,このときA>Cとかそういうのも消えるらしい.
問題自体は単なるトポロジカルソート.
・問題F
枝刈り探索.AOJで同じような問題見たような…,解いてなかったけど.
・問題G
問題文読むのに苦戦した.バーの長さは2の冪を作っておけばよい.
・問題H
ダイクストラを何回もやるだけ.

SPOJ 3890 - Rectangles Counting [MRECTCNT] (この記事を編集する[管理者用])

Source

BOI For Kid 08
SPOJ 3890 [MRECTCNT]

問題概要

問題文の図のように,長方形を1*1のマスに分けて,対角線の通るマスの数を考える.
対角線が通るマスの数がNとなるような長方形の数を求める問題.
Nは1000000未満.

解法

対角線が格子点を通る場合とそうでない場合で分けて考える.
そうでない場合は,縦 + 横 - 1個のマス目を通る.
格子点を通る場合は,通るマス目の数を分割して小さい問題に帰着させる.

SPOJ 3885 - Coins Game [MCOINS] (この記事を編集する[管理者用])

Source

BOI For Kid 08
SPOJ 3885 [MCOINS]

問題概要

Nim.(石取りゲーム)
2人でゲームを行う.
山の数は1個で,石が積まれている.
1回に取れる石の数は1個かK個かL個.
最後の石をとった人の勝ち.
先手必勝か後手必勝かを判定する問題.
同じKとLに対してクエリが50個まで来る.
山の石の数の最大値は1000000で,KとLは10未満.

解法

やるだけ.石の数が小さい方から先手必勝か後手必勝か埋めていく.

SPOJ 3881 - Majstor [MAJSTOR] (この記事を編集する[管理者用])

Source

COCI 2008/2009 - Croatian Regional
SPOJ 3881 [MAJSTOR]

問題概要

じゃんけん.ただし同時に複数の相手とする.
何回戦かやって,毎回,
 勝った相手の数 * 2 + 引き分けの相手の数
のポイントが貰える.
自分の出した手と相手の手が与えられるので,実際にもらえるポイントと,
相手の手がわかっていたときに,自分が最適な手を出すと最大でいくらポイントがもらえたかを求める問題.
最大で50回戦する.相手の数は50以下.

解法

やるだけ.1回戦ごとにわけて考える.

SPOJ 3878 - Rectangles Perimeter [MMAXPER] (この記事を編集する[管理者用])

Source

BOI For Kid 08
SPOJ 3878 [MMAXPER]

問題概要

1000個以下の長方形が与えられる.
長方形を与えられた順番で左から(重ねないように)詰めていく.
縦横どちらが長いように詰めても良い.
この時,上の辺(定義は問題文参照)の長さの最大値を求める問題.

解法

今何個目の長方形まで詰めたか,最後に詰めた長方形の向きを状態としたDP.

SPOJ 3877 - Cvjetici [CVJETICI] (この記事を編集する[管理者用])

Source

COCI 2008/2009 - Croatian Regional
SPOJ 3877 [CVJETICI]

問題概要

問題文の図のように,n日目には高さnの柵を書く.
各日にちに書く柵の左端・右端の座標が与えられる.
昔書いた柵と交わる場合,そこに花が咲く.
ただし,同じ場所には1回しか咲かないし,連続的に重なっている部分には咲かない.
1~N日目に咲く花の数をそれぞれ求める問題.
Nは100000以下,座標は1以上100000以下.

解法

Fenwick Tree.
毎回左端に+1,右端に-1しておいて,新しい左端より左の数字と右端より左の数字の和だけ交点がある.
すでに交わっている交点をカウントしないように,x座標ごとにすでに咲いた花の数を覚えておく.

SPOJ 3876 - Tablica [TABLIC] (この記事を編集する[管理者用])

Source

COCI 2008/2009 - Croatian Regional
SPOJ 3876 [TABLIC]

問題概要

N*Nのマス目に1~N^2が最初row-major orderで並んでいる.
問題文で定義されてる行の回転・列の回転(それぞれ片方向のみ)を用いて座標(R,C)に数字Xをもってきたい.
そのような操作をK回続けて行う.
問題文で与えられたアルゴリズムで回転するとき,各操作で必要な回転の数を求める問題.
Nは10000以下,Kは1000以下.

解法

クエリを全部読み込めば,着目する数字は高々K個で良くなるので,K個の数字がどこにあるかシミュレーションする.
計算時間量O(K^2).

SPOJ 3870 - Military Story [VMILI] (この記事を編集する[管理者用])

Source

SPOJ 3870 [VMILI]

問題概要

二次元平面上に4000個以下の点が与えられる.
その点を頂点として,多角形をいくつか作る.
多角形は共通点を持ってはいけない.
最大で何個ネストできるかを求める問題.

解法

凸包(それが一番外の多角形)を除いていくのを繰り返す.

SPOJ 3868 - Total Flow [MTOTALF] (この記事を編集する[管理者用])

Source

USACO JAN09 SILVER Division
SPOJ 3868 [MTOTALF]

問題概要

52ノードの有向グラフが与えられる.
ノードAからノードZに流れる最大流を求める問題.

解法

最大流.

Aizu 0172 - Doctor's Research Rooms (この記事を編集する[管理者用])

Source

PC Koshien 2007 (パソコン甲子園2007)
Aizu 0172

問題概要

15個以下の部屋が30個以下の通路で結ばれている.
部屋の電灯のスイッチはたくさんあるかも知れないし,他の部屋にあるかもしれない.
暗い部屋に入ることはできない.
出口以外の全ての部屋の電気を消灯して出口に向かう最短の方法を出力する問題.
電気のスイッチの切替,部屋の移動の両方共1ステップと数える.
不可能ならば,電気を消さなくていいから出口にたどり着くことができるか,それさえも不可能かを判定する.

解法

状態数が電灯が付いているかどうか,今どこにいるかの高々2^15*15なので,BFSする.

Aizu 0171 - Dice Puzzle (この記事を編集する[管理者用])

Source

PC Koshien 2007 (パソコン甲子園2007)
Aizu 0171

問題概要

8つのサイコロが与えられる.各面には大文字か小文字のアルファベットが書かれている.
接する面は同じアルファベットの小文字と大文字でなければならない.
2*2*2の立方体を作れるかどうかを判定する問題.

解法

全探索+枝刈り.

UVa 11840 - Tic-tac-toe (この記事を編集する[管理者用])

Source

Brazilian National Contest 2010 (2010-09-19)
UVa 11840

問題概要

2人で1次元Tic-tac-toeをプレイする.
nマスの空白があって,順番に1箇所選んでXを書いていく.
連続してXを3つ並べると勝ち.
まだ決着がついていない途中の盤面が与えられるので,先手必勝か後手必勝かを判定する問題.
nは10000以下.

解法

この状態で相手に渡すと次にXを3つ揃えられるという状態へ移動できないものとして,打つ手がなくなったら負け形式のゲームに再定式化する.
後は,連続する空白の数とその左右がXが書かれているか,盤面の端か,という小さいゲームに分けてgrundy数を求める.

Appendix

Recent Articles

ブログ内検索

Ads


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