Entries

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

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

Aizu 2288 - Oh, My Goat! (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2288

問題概要

日本語なので略.

解法

各のグラフの今どこのノードにいるか,まだ使い切ってない文字列を状態としてDPする.
ある状態にいるとき,使う枝を決めると次の状態に移行できる.
使いきってない文字列は,たかだか片方のグラフにしかなく,4文字以下.
愚直にメモリを取ろうとするとMLEしそうだったので,map<string,int>を使った.

Aizu 2286 - Farey Sequence (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2286

問題概要

日本語なので略.

解法

オイラーのφ関数をエラトステネスのふるいのような感じで全部求めた.

Aizu 2285 - Anipero (アニペロ) (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2285

問題概要

日本語なので略.

解法

シークレットアーティストは全探索する.
スタンダードアーティストは,選んだ人数,そのコストの総和を状態としてDPで,満足度最大の組み合わせを求める.
後は,シークレットアーティストとスタンダードアーティストの組み合わせを全部試す.
(自分は,DP処理を使いまわして,シークレットアーティストもDPした)

Aizu 2284 - The Legendary Sword (伝説の剣) (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2284

問題概要

日本語なので略.

解法

数字の書いてあるマス,各場所にたどり着くまで距離をDPで求める.

Aizu 2283 - Seishun 18 Kippu (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2283

問題概要

日本語なので略.
要するに,無向グラフが与えられるので,ノード0からノード1までの最短距離+ノード1からノード2までの最短距離を求める問題.

解法

ノード1をダイクストラをする.

Aizu 2282 - Problem B (B問題) (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2282

問題概要

日本語なので略.

解法

素直に気をつけてシミュレーションする.
実は,ちょっと考えると,全ての人は常に嘘がばれない最大時間を申告することがわかり,それに気づくと楽になる.

Aizu 2281 - Swap Cipher (スワップ暗号) (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2281

問題概要

日本語なので略.

解法

最後の操作から順番に復元していく.

Aizu 2251 - Merry Christmas (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2251

問題概要

ノード数100以下,枝数1000以下の無向グラフが与えられる.
枝は移動するための時間が書かれている.あるノードでしばらくじっとしていることも可能.
とあるサンタさんが,あるノードにある時間丁度にいなければならないという条件が1000個以下与えられる.
最小で何人のサンタさんがいれば,条件をみたすことができるかを求める問題.

解法

べたべたのDAGの最小パス被覆.最大流で解ける.

Aizu 2250 - Operator (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2250

問題概要

各顧客 (顧客数Nは1000以下) は,最初時間0に電話をかけてきて,1回電話をかけると,L[i]だけ電話がつながるまで待ち,電話が繋がらなかったら,切ったK[i]だけ後に再度電話を掛ける.
電話が繋がったら,所要時間はM[i]だけかかり,もう電話をしない.
M[i],L[i],K[i]は顧客ごとに設定されたパラメータ.
オペレーターは待ってる人のうち,顧客番号の最も小さい人から繋げて処理をする.
時間T (1000以下) までに全員処理が完了するための最小のオペレーターの人数を求める問題.

解法

オペレーターの人数を1人から順番に調べる.
答えは最大でもNで,制限時間Tが1000以下なので,時間1ずつシミュレーションすることでO(N^2 T)時間で求まる.
実際はこれだとTLEだけど,枝刈りすれば通る.
オペレーターの人数で2分探索すると,単調ではないのでWAになる.(サンプルに単調でない例が入っている)

Aizu 2249 - Road Construction (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2249

問題概要

ノード数10000以下,枝数20000以下の有向グラフが与えられる.
枝には距離とコストが設定されていて,ノード0から他の任意のノードまで行くパスがある.
ノード0から他の任意のノードまで行く最小距離を保ったまま枝を減らしたい.
最終的なグラフの枝のコストの和の最小値を求める問題.

解法

ダイクストラして使える枝を列挙して,DAGに落とし,自分に入ってくる枝のうちコストが最小のものを採用する.

Aizu 2247 - Two-Wheel Buggy (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2247

問題概要

長さ2Dの棒でつながれた2つの車輪が,最初,片方は(-D,0),もう片方は(D,0)の座標に置かれている.
各車輪の角速度と,その角速度でどれくらいの時間移動したか,という情報が与えられるので,最終的な重心の場所を求める問題.
車輪の半径は1.

解法

2次元幾何シミュレーション問題.
移動経路は,どこかを中心とした円周上になる.

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

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2245

問題概要

各面が3*3の領域に分けられているサイコロが与えられる.
各領域は穴が開いているか開いていないかの情報が与えられる.
手前の面の一番下の行と,奥の面の一番下の行に,それぞれ少なくても1箇所穴が開いている状態にするには最小で何回転がせばよいかを求める問題.
答えは存在することは保証されている.

解法

状態数は24しかなく,答えは大きくならず,探索してもどうやっても基本的には計算量は間に合う.
頑張って実装する.

Aizu 2244 - Dungeon Quest II (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2244

問題概要

罠のあるマップと,移動したい経路が与えられる.通るマスの数は1000以下.
罠のあるマスを通ると罠の種類に応じてHPが減る.
回復薬をP個 (12以下) 持っていて,使うと体力を回復できる.
最大HP (1000以下) も与えられていて,HPは最大HPを超えたら最大HPになる.
HPが0以下になると死ぬ.
最後まで移動可能かどうかを判定する問題.

解法

今何マス移動したか,残ってる回復薬を状態として,現在HPの最大値を記憶するDP.
O(N*P*2^P)時間で,領域はO(2^P)でできる.

Aizu 2243 - Step Step Evolution (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2243

問題概要

同時押しのないDDRの譜面が与えられて,左足は右足より右にいけないという制約のもと,同じ足で連続して押す回数を最小化したい.
最小値を求める問題.譜面のノート数は100000以下.

解法

DP.最後に使った足,右足と左足はどこにいるかを状態とする.
どうやらgreedyでも行けるらしい.

Aizu 2242 - Era Name (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2242

問題概要

西暦何年が何の元号何年かという対応関係が1000個以下与えられる.
西暦何年が元号で言うと何年か?というクエリが1000個以下与えられるのでそれに答える問題.
判定できないならunknownと返す.
元号が変わるのは必ず年の切れ目であることを仮定して答える.

解法

全部のクエリに対して,各元号になるかどうか,与えられた情報全部なぞってもO(1000*1000)なので大丈夫.

Aizu 0225 - Kobutanukitsuneko (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0225

問題概要

10000個以下アルファベット小文字からなる文字列が与えられる.
全部の単語を使ってしりとりして,最初の単語の先頭の文字が,最後の単語の最後の文字にできるかどうかを判定する問題.

解法

アルファベット26種類のノードをもつグラフに落として,次数(入次数-出次数)が0であること,枝があるノードは全部連結であることを調べればよい.

Aizu 0224 - Bicycle Diet (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0224

問題概要

ノード数108以下ぐらいで,枝数256以下の無向グラフが与えられる.枝には通ると消費されるカロリーが与えられる.
ケーキ屋さんが6個以下あり,ケーキ屋さんを通過すると,カロリーが増え,同じケーキ屋さんは2回以上通れないとする.
出発地点から目的地まで移動する最小消費カロリーを求める問題.

解法

それぞれのケーキ屋さんに訪れているかどうか,それぞれのノードを2^6個に分裂させてダイクストラする.

Aizu 0223 - Stray Twins (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0223

問題概要

50*50以下のグリッド上に2人いる.
片方が,右左上下に移動すると,もう片方は,左上下上に移動する.
ただし,片方だけがグリッドの外に出る場合と,壁にぶつかって移動できない場合は,片方のみその場に留まる.
2人が同じセルに移動するまでの最小時間を求める問題.
ただし,時間100以上かかる場合は,NAを出力する.

解法

2人の位置を状態にBFSする.

Aizu 0222 - Prime Quadruplet (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0222

問題概要

(a-8, a-6, a-2, a)が全部素数の時,四つ子素数といい,aを四つ子素数の大きさという.
13以上10000000以下の整数nが与えられるのでn以下で最大の四つ子素数の大きさを求める問題.

解法

最初に四つ子素数の大きさを全部求めてしまい,2分探索する.(四つ子素数は少ないので線形探索でも十分な気がする)

Aizu 0221 - FizzBuzz (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0221

問題概要

1から順番に数字を言っていくが,3の倍数ならFizz,5の倍数ならBuzz,両方の倍数ならFizzBuzzと言わなければいけないゲームを行う.
間違えた人から脱落していく.
参加人数と発言ログが与えられるので,最後まで残っている人の番号を求める問題.
また,最後の1人になったら,その後の発言には関わらず,その人は生き残る.

解法

シミュレーションするだけ.

Aizu 0220 - Binary Digit A Doctor Loved (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0220

問題概要

整数部8桁以下,小数部4桁以下の実数が与えられるので,小数点以上8桁,以下4桁の2進数に直す問題.
不可能なら(桁が足りないなら)NAと出力する.

解法

整数部と小数部に分けてやるだけ.
丸め誤差が怖いが,double使えば分けずにできるかも.

Aizu 0219 - A Popular Ice-cream Shop (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0219

問題概要

10種類のアイスクリームの販売履歴が与えられるので,販売個数のヒストグラムを出力する問題.

解法

やるだけ.

Aizu 0218 - Dividing Students (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0218

問題概要

3科目の試験結果に基づいてAクラス,Bクラス,Cクラスに分ける.
分け方は問題文に与えられている.
試験結果が与えられたとき,どのクラスに属するか求める問題.

解法

やるだけ.

Aizu 0217 - Walking in the Hospital (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0217

問題概要

1日2回ウォーキングを行う.
 人番号,1回目の歩いた距離,2回目の歩いた距離
が与えられるので,最も長く歩いた人の人番号と歩いた合計距離を求める問題.
答えは一意に定まる.人の数は10000以下.

解法

やるだけ.

Aizu 0216 - Cutting Down Water Bills (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0216

問題概要

水道料金を計算方法が書かれている.
10m^3までは基本料金で,その後段階的に単位水量あたりの価格が変わっていく.
今月使った水量が与えられるので,先月との今月との差額を出力する問題.
先月の水道料金は4280.

解法

やるだけ.

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

Source

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

問題概要

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

解法

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

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の立方体を作れるかどうかを判定する問題.

解法

全探索+枝刈り.

Aizu 0153 - Triangle and Circle (この記事を編集する[管理者用])

Source

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

問題概要

日本語の問題文があるので簡単に書く.
2次元平面上の三角形と円が与えられたとき,その関係が
 包含関係になっているか,共通部分を持つか,共通部分がないか
判定する問題.

解法

二次元幾何,頑張る.
接する場合は,面積0でも共通部分を持つことに注意.

Aizu 0109 - Smart Calculator (この記事を編集する[管理者用])

Source

PC Koshien 2005 (パソコン甲子園2005)
Aizu 0109

問題概要

日本語の問題文があるので簡単に書く.
数字と四則演算とカッコからなる数式が与えられるので,評価する問題.割り算は整数の割り算.
文字数は100文字以下.

解法

書くだけ.オーバーフローするかと思ったらしなかった.

Appendix

Recent Articles

ブログ内検索

Ads


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