Entries

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

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

North America - East Central - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

A. Bordering on Madness
読んでない.

B. Jack of All Trades
物々交換.
自分が出すものと自分が欲しいものが与えられる.
また,50人以下の人が出すもの,欲しいもの,その交換比率が与えられる.
9回以下の交換で,自分が欲しいもの1個当たりに,何個出すものを差し出せばよいか,最小値を求める問題.
また,そのレートを達成できる交換手順の数も求める.

基本的にはやるだけ.
出力の形式が有効数字5桁で出力せよというのが意外と面倒.

C. LCR
シミュレーション.
10人以下のプレイヤーが輪になってゲームをする.
皆,最初コインを3枚持っている.
順番にサイコロを3つずつ振る.
サイコロはCとLとRと.の4種類が書いてあって,Cが出ると自分のコインを中央の捨て場に捨てる.
L,Rが出るとそれぞれ自分の左,右の人にコインを1枚あげる.
ただし,コインを持ってる数が3枚より少なければ,持っているコインの数だけサイコロを振る.
1人を除いて誰もコインを所持していない状態になればゲーム終了で,コインを持っている人が勝者.

サイコロの出目が与えられたとき,ゲームをシミュレーションして最終状態を求める問題.
やるだけ.

D. Party Party Party
ある日に行われたパーティーの時間が与えられる.
パーティーの数は100個以下で,X時からY時まで開催したという形式で与えられる.
パーティーにいくと必ず30分は滞在しないといけない.
移動時間が0のとき,最大で何個のパーティーに参加できるかを求める問題.

Greedyにやればできると思うけど,問題サイズが小さいし,何も考えずに最大流した.

E. Su-Su-Sudoku
数独でまだ埋まっていないところが5箇所あるので数独を完成させてくださいという問題.
答えが存在しない場合はそれを指摘する.答えは存在するなら必ず1通りに定まる.

9^5通り全探索すれば良い.
プログラミングコンテスト系で良く見かけるし,数独解くライブラリでも作っておいても良いのかもしれない….

F. Tanks a Lot
円周上のサーキットがある.
いくつかの場所に燃料が落ちている.燃料の持てる量は無限.
最初燃料が全く無い場合,時計回り,反時計回り,それぞれに対して1周回ることができる初期位置を全部求める問題.

UVaで同じ問題があったような気がする….因みに当時出くわしたときは解けなかった.
燃料の落ちている位置をソートしておく.
後,適当に始点を決めておく.
1回燃料が落ちている位置をなぞって,始点からそれぞれ燃料が落ちている地点に行くためには,始点で幾ら燃料があれば良いかを求めておく.
今度は逆順になぞって,始点に燃料切れをおこさずに辿り着けるか,始点に辿りついたときに,さっき計算した自分の位置に戻ってこれるだけの燃料がたまっているかを判定する.

G. The Worm Turns
m*nのグリッドが与えられる.m*nは625以下.
グリッドの上には食べ物が落ちているグリッドがある.

あるグリッドから初めて,ある方向に食べ物が落ちている限り直進して食べる.
自分の前のグリッドに食べ物が無いなら左右どちらかに曲がる.
ということを繰り返して,食べることができる食べ物の数を最大化したい.
食べることができる食べ物の数の最大値,それを達成できる初期位置と方向を求める問題.
初期位置,方向はたくさんあれば辞書順最小のものを求める.

H. You'll be Working on the Railroad
枝数が50以下のグラフで,ある地点からある地点に辿り着くまでの最小コストの単純な路を求める問題.
ただし,最大2つまで通った枝のコストを0にすることができるが,最低1つの枝は正規のコストを払って通らなくてはいけない.
最小コストの路が2通り以上ある場合は,通るノードの数を最小にして,それでも複数あるなら辞書順最小のものを求める.
枝のコストは正.

適当にノードを分裂させてグラフを作ってやろうと思ったんだけど,それだと単純な路にならなかったりしてうまくいかなかった.
例えば
3
0 2 100
2 1 100
2 3 1
とかで
答えは0 2 1,cost 100のところを,0 2 3 2 1,cost 2としてしまったら駄目.

枝が高々50しかないので,O(枝数^2)のループを回して,どの枝をコスト0にするかを決めて,それぞれのグラフでダイクストラする.
ただし,コストが0になったら採用しないという風にすれば上手くいく.
1つのみ枝のコストを0にする場合とか,1つも枝のコストを0にしない場合とかを忘れてはいけない.

USACO 2008 NOVEMBER (この記事を編集する[管理者用])

GOLD 4問,SILVER 3問,BRONZE 3問.
Link先はTJU.
[ Link ]

GOLD 1問目: Mixed Up Cows
16匹以下の牛たちのIDが与えられるので,牛を並び替えて,隣会う牛のIDの差がkより大きくなるような並べ方は何通りあるか求める問題.
DPするだけ.

GOLD 2問目: Cheering Up the Cows
連結な無向グラフが与えられる.
枝を移動するのにかかる時間,ノードに訪れるたびにすごさなければいけない時間が与えられる.
目的は,枝をいくつか切り捨てて,連結な木を作って,何処か始点を決めて,その木にそって全部のノードを最低1回以上訪れて始点に戻る時間を最小化したい.

残された枝は2回ずつ通って,基本的にノードには次数だけ訪れることになる.
ただし,始点のみ1回訪れる回数が大きい.
なので,枝の重みを2倍して,繋がっている2つのノードの時間を足してMSTを求める.
後は,ノードの時間が最小のを1個分足したら答え.

GOLD 3問目: Light Switching
一直線に並んだ100000個以下のスイッチがある.最初は全部OFF.
100000個以下の操作を行う問題.
操作は,
 1) ある区間のスイッチを全部反転させる
 2) ある区間のONのスイッチの数を求める
の2つ.

segment tree.

GOLD 4問目: Toys
D日間に渡って,各日に必要なおもちゃの数が与えられる.
おもちゃは新しく買っても良いけど,消毒することで使いまわせる.
消毒業者が2つあってそれぞれ1つ消毒するのに必要なコストと,消毒に必要な日数が与えられる.(何個でも同時進行で消毒できる).
費用を最小化する問題.

TJUでWAばっかりもらうので,USACOにID登録してサブミットしてみたらUSACOでは通った.
おもちゃを何個買うかを決めてしまった場合は,適当にgreedyにやればO(D)で最小コストが求まる(単純でもないのだけど…).
おもちゃを何個買うかというのは三分探索したら良さそうな気がしたのでそうしてみた.

SILVER 1問目: Buying Hay
x_i個でy_i円みたいな感じで商品が買えるので,H個以上買うために必要な最小金額を求める問題.
典型的DP.

SILVER 2問目: Guarding the Farm
2次元グリッドで各座標の標高が与えられるので,hilltopの個数を求める問題.
hilltopは連結なグリッドの集合で,まわりは自分より低い.

座標を標高ごとにソートして高いほうからなぞっていく.
まだ塗りつぶされていないなら,答えに1を加えて,自分から標高が同じか低くなる連結な部分を塗りつぶしていく.

SILVER 3問目: Time Management
各仕事にかかる時間と,その仕事を仕上げなければいけない時間が与えられるので,いつから仕事に取り掛かればよいか,もっとも遅い時間を求める問題.

デッドラインが速い順に仕事をすれば良いので,ソートして,後は必要な時間を適当に計算するだけ.

BRONZE 1問目: Switching Lights
GOLD 3問目の制約が緩くなったもの.
単純にシミュレーションするだけで良い.

BRONZE 2問目: Guarding the Farm
SILVER 3問目の制約が緩くなったもの.
かといって,SILVER 3問目より単純な解法が良く分からない….

BRONZE 3問目: Going Once, Going Twice, Gone!
商品を持っている数と,その商品を買いたい人のリストが与えられる.
買いたい人は買うために幾らまでお金を出すかが与えられる.
商品の価格をうまく設定して,得られるお金を最大化する問題.
得られるお金が等しいなら,できるだけ商品の価格を安くする.
買いたい人の数は1000人以下.

買いたい人リストをソートして,全部調べるだけ.

North America - Rocky Mountain - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先は基本的にLiveArchive.
[ Link ]
[ Official website ] : Judgeデータなど

A. Combination Lock
North America - Mid Atlantic - 2008/2009の問題Fと殆ど同じ問題.
ただし,最悪の場合ではなくて,初期値がランダムのときの平均値を求める.
やるだけ.

B. Lawrence of Arabia
North America - Mid Atlantic - 2008/2009の問題Dと同じ.

C. Close Enough Computations
North America - Mid Atlantic - 2008/2009の問題Aと同じ.

D. Walk in the Park
2次元平面上にN本の木とM本の道が与えられる.
木は点で道はx軸またはy軸に平行な直線.
道から見ることができる木の数を求める問題.
ただし,道からは上下左右の4方向しか見ることができなくて,間に木があると向こうの木は見えない.
NとMはそれぞれ10万以下.

やり方は色々ありそうだけど,例えば縮小座標に落として,x座標ごとにソートしてなぞっていって,y座標ごとにソートしてもう1回なぞっていく感じ.
とりあえず頑張って O( (N+M) log(N+M) ) 程度でやれば良いはず.

E. Dance
文字列処理実装問題,やるだけ.
与えられた文字列が,問題文で与えられた条件を満たしているかどうかを調べる問題.

F. Trucking
union + ダイクストラ.
ノード数1000以下の無向グラフが入力.
枝には,距離と通れる車高制限がある.車高制限のない枝もある.
出発地と目的地が与えられるので,最大で車高いくらの車が目的地に辿り着けるかを求めて,
更に,その車高の車が目的地に辿り着く最短距離を求める問題.
ただ,車高は制限があってそれ以上の車高の車は考えなくて良い.
(ここで書いてる説明は適当なので詳細は問題文を読むべし)

まず,車高制限のゆるい枝を付け加えていって出発地と目的地が連結になる最初の枝の車高制限が1つ目の答え.(クラスカルみたいな感じ)
後は,それよりゆるい枝のみを使ってダイクストラして最短距離を求める.
注意点は,道の車高制限が,最後に与えられる考える車高制限を超えてる場合もあって,最後に与えられる車高制限を越える値を出力しないように注意.

G. When
読んでない.

H. Prime Bases
素数進数みたいな感じの形式が問題文で定義されているので,10進数で与えられた数字をその形式に直す問題.
やるだけ.

SRM433 DIV1 (この記事を編集する[管理者用])

2009年01月22日01時から.
[ Match Overviews ]

寝起きでSRMは駄目だと再認識した.

EASY (250pt)
8個以下の文字列が与えられる.各文字列は20文字以下.
T(i)を文字列Tに対してiだけシフトした文字列とする.
8個の文字列を適当に繋げてT(k)=Tとなるkが厳密にK個となるつなげ方は何通りあるかを求める問題.

単純に実装すると計算量は最悪で 8! * (8*20)^2 程度で微妙にTLE.
TLEを回避する方法は幾らかある.
例えば,T(i)=SとするとT(k)=TならばS(k)=Sなので,最初の文字列を固定して 7! * (8*20)^2 にしたり,
T(k)=Tかどうかをチェックするとき,kはnを割り切るものだけチェックするとか.

MEDIUM (500pt)
100以下の自然数M, Nが入力.
0 <= x <= M, 0 <= y <= N の格子点から4つ選んで菱形を作る方法は何通りあるかを求める問題.

2辺のx方向の長さ,y方向の長さごとに,その菱形全体のx方向の長さとy方向の長さを求めて,それがN×Mのグリッドに幾つはいるかというのを足していくだけ.

HARD (1000pt)
50*50以下のグリッドが与えられる.
通れないマスと自分の初期位置,各マスを壊すのに必要なコストが与えられる.
自分の初期位置からグリッドの外にでれなくするように各マスを壊したいのだけど,
 1) 壊すマス目の数を最小化する
 2) その中で,壊すマス目のコストの和を最小化する
コストを答える問題.

単に,壊すのに必要なコストに十分大きな数字を足しておけば,壊すマス目のコストを最小化するだけの問題になる.
後は,最大流を流せば良い.

PKU 3212 - Rescue Alice (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
2次元平面上に100000個以下の点がある.
その中から1点を選んで,選んだ点とその他の点との距離の和を最小化する問題.
ただし,距離は無限大ノルムで定義される.つまりx座標の差とy座標の差の大きいほう.

[ 解法 ]
座標軸45度回転させると無限大ノルムはマンハッタン距離に帰着させることができる.
後は,適当にx座標,y座標ごとにソートして,ある値以下のx座標の和とかを計算しておけばよい.

PKU 3493 - Chessboard Puzzle (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
16×16以下のサイズのグリッドが与えられ,それぞれのマスに1000以下の数字が書かれている.
各マスを白か黒に塗るのだけど,スコアは隣り合ったマスが違う色に塗られていたら,その2つのマスに書かれている数字の積がスコアに足される.
スコアを最大化する問題.

[ 解法 ]
Ad-hoc.
後で (行番号+列番号) mod 2 が 0 のグリッドに塗られている色を反転させると思えば同じ色に塗られていればスコアが足されると思ってよい.
後は,マイナスの数字が書かれたマスを全部白に,プラスの数字が書かれたマスを全部黒に塗れば良い.
隣り合ったマスの積がプラスならば確実にスコアに足されるし,積がマイナスならスコアに足されないので,これ以上に良い塗り方はない.

(2009/01/22 10:15修正)

PKU 3045 - Cow Acrobats (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
50000匹以下の牛がアクロバットなことに挑戦する.
それぞれの牛は重さと強さが与えられている.
タワーを作るんだけど,それぞれの牛に対しての危険度は
 自分よりの上にいる牛の重さの合計 - 自分の強さ
で定義されるので,牛の順番を考えて,最も危険度が高くなる牛の危険度を最小化する問題.

[ 解法 ]
Greedy.
重さ + 強さ の値が大きい牛ほど下に配置すれば良いことが少し考えればわかるはず.

PKU 3139 - Balancing the Scale (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
1以上1024以下の異なる16個の整数が与えられたとき,それらを
 x1 * 4 + x2 * 3 + x3 * 2 + x4 = x5 + x6 * 2 + x7 * 3 + x8 * 4 (1)
 y1 * 4 + y2 * 3 + y3 * 2 + y4 = y5 + y6 * 2 + y7 * 3 + y8 * 4 (2)
を満たすような割り当ての数を求める問題.
ただし,自明な対称性があるので,それらは重複して数えてはいけない.

[ 解法 ]
16個から8つ選んで,それぞれに対して,式(1)を満たす割り当ての数を求めておいて,後はそれらを適当にかけたり足したりして答えを求める.
16個から8つ選んで(1)を満たす割り当ての数は基本的に全探索する.
計算量はラフに見積もって (16C4)^2 * 4! / 2 × 定数 程度では抑えることができるはず.

SPOJ 3725 - Taming a T-REX [TREX] (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
ある街からDだけ離れた街に牛たちを運びたい.
T-REXに運ばせるんだけども,こいつは距離1移動するたびに牛を1頭ずつ食ってしまい,同時にC頭まで牛を積むことができる.
途中,最初の街からの距離が整数の場所に牛をいったん置いておくということが許される.
ただし,T-REXを移動するときに,T-REXが食べる牛がいないのは許されない.
最初の街にI頭の牛がいるとき,目的の街まで最高で何頭の牛を運ぶことができるかと求める.
IとCは10^6以下,Dは10^5以下.

[ 解法 ]
シミュレーション.
距離1で最適に運ぶ方法をD回繰り返せば良い.
距離1での最適方法は以下の通り.
 まず,載せれるだけ乗せてT-REXを目的地に移動させる.乗せて牛は1匹食われる.
 もし,最初の地点に牛が3匹以上残っているなら,生贄用に1匹牛を乗せて帰って,また乗せれるだけ乗せて目的に移動する,ということを繰り返す.
もちろん,距離1でのシミュレーション結果はO(1)で計算できる.

SPOJ 3723 - Snooker [SNOOKER] (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
横の長さM,縦の長さNのビリヤード台がある.
角でない四辺の整数点から斜め45度の方向にボールを転がして,最終的に穴に入るのは何パターンあるかを求める問題.
MとNは10^5以下.

[ 解法 ]
対称性から右上の穴に入るパターン数を求めて,それを4倍すれば良い.
ちょっと考えると,右上の穴から逆に辿るとそのうち別の穴に入ることが分かる.
なので,右上の穴から初めて,別の穴に入るまでの軌跡をシミュレーションして,そのとき跳ね返った回数の4倍を出力すれば良い.

Asia - Manila, Singapore - 2008/2009 (この記事を編集する[管理者用])

10問.
Jakarta.
Link先はLiveArchive.
[ Link ]

A. Anti Brute Force Lock
4桁の数字を1桁ずつ回転させて目的の数字に一致させることを考える.
最初は0000で,目標の数字は500個以下.
目標の数字に一致させる順番は任意でよくて,一度でも一致させたならその数字には回転無しで戻すことができる.

ちょっと考えれば,答えは0000から一番近い数字までの距離 + 最小木の重みの和になる.

B. Bonus Treasure
文字列を以下のように定義する:
 S[1]=(),S[k]=(S[1]S[2]...S[k-1])
S[N]のK文字目からM文字を出力する問題.
Nは31以下,Mは10000以下.
やるだけ.

C. Panda Land 7: Casino Island
ディーラーは1~Nまでの数字を並び替える.
各参加者iはディーラーの数字の最初からM_i個を予想する.
予想が当たっていたら参加者はお金をC[M_i]だけもらえる.

支払金C[1], C[2], ..., C[N]と各参加者の予想が与えられたとき,支払う金を最小とするようなpermutationを求める問題.
ただし,答えが複数あるならば辞書順で最初のものを求める.
Nは30以下,参加者の数は100000以下.

D. Disjoint Paths
ノードが60以下の木が与えられる.枝には距離が定義されている.
同じノードを2回以上使わずに,K個以下のパスを取ってきて,そのパスの長さの和を最大化する問題.

E. Expert Enough?
各自動車メーカーが過去に販売した車の最小金額と最大金額が与えられる.
今,販売価格の分かっている車が1000台以下あるので,それらを作っているメーカーを求める問題.
ただし,該当メーカーがない場合,2つ以上あって特定できない場合はその旨を出力する.
自動車メーカーの数は10000以下,車の価格は100万以下.

Fenwick Tree.

F. Free Parentheses
非負整数とその間に+か-の演算子が与えられる.
適当に括弧をつけて良いとき,得られる結果は何通り考えられるか.
項の数は30以下,各数字は100以下.

(プラスの後に括弧があっても意味無くて)マイナスの後に括弧があると思って,
 今何項目,今まで出てきた括弧で閉じてないものの数,今までの和
を状態としてメモ付探索というかDPというか.
状態数は最大で30*30*6000だけど,全ての状態に辿りつけるわけじゃないので,そこまで大きくないはず.

G. Greatest K-Palindrome Substring
与えられた文字列をまず最初にK文字以下変更しても良い.
その結果,文字列に含まれる回文の長さを最大化する問題.

全探索.
まず回文の中心を決めて,それから左右に1文字ずつ見ていって違う文字だったら片方を変更したと思って,最大長を求める.

H. Hyper-Mod
問題文で定義されている関数を mod M で計算する問題.
アッカーマン関数みたいなの.

I. ICPC Team Strategy
ICPC.(3人1チームで問題数Pのプログラミングコンテストに参加する)
各メンバーが各問題を解くのに必要な時間が与えられる.
制限時間280分で最大で何問解けるかを求める問題.
ただし,同じ人が2回連続で問題を解くことはできない.
Pは12以下.

ノード数3*2^Pのグラフを作って何も考えずにダイクストラした.

J. Jollybee Tournament
2^N人でトーナメント戦を行う.Nは10以下.
第1回戦で最初に現れなかった人のリストが与えられるので,不戦勝が起こる試合の数を求める問題.
シミュレーションするだけ.

North America - Greater New York - 2008/2009 (この記事を編集する[管理者用])

9問.
Link先は基本的にLiveArchive.
[ Link ]
[ official site (problems) ] ジャッジ解答,ジャッジ入出力など.

A. Sixth Grade Math
GCDとLCMを求める問題.
GCDはユークリッドの互除法,LCM=a*b/GCD.

B. Cryptoquote
AをGに置き換えて…系の1文字を別の1文字に置き換える暗号をデコードする問題.
書くだけ.

C. Binary Clock
何時何分何秒を2進数表示して縦や横に並べてたらどうなるかを求める問題(問題文参照).
書くだけ.

D. Recursively Palindromic Partitions
1000以下の自然数が入力.それの再帰的回文分割の数を求める問題.
27の回文分割とは例えば27=1+3+19+3+1のようなもの.
再帰的回文分割は,回文分割で,分割に含まれている自然数の,その左半分だけみても再帰的回文分割の形をしているもの(もしくは27=27みたいに1つのみからなる).
例えば27=1+3+1+17+1+3+1みたいなもの.1+3+1も再帰的回文分割.
もしくは,16=2+4+2+2+4+2みたいなもの.2+4+2も再帰的回文分割.

単純にO(n^2)のDPでもOKだけど,うまく考えるとO(n)のDPでも解ける.

E. Text Messaging Improvement?
各アルファベットの出現頻度が与えられたとき,携帯の文字の割り当てを変更して,1文字を入力するのに必要なボタンを押す数の平均を最小化する問題.
ただし,1つのボタンには1個以上8個以下の文字を割り当てなければいけない.

DPで良いと思うのだけども….
公式のジャッジ入力はとりあえず壊れているっぽい.出現頻度を足すと101%とかなる.

F. Extended Normal Order Sort
文字列処理 + 実装問題.
直感的なソートを実装したいので,2つの文字列の大小を比較せよという問題.
アルファベットは全て大文字に置き換えて考える.
数字っぽいところは数字だと思ってソートする.
数字は全ての1文字よりも小さい.
数字の定義は0~9の文字の連続.ただし,先頭に1つの+か-の符号がつくかもしれない.
ただし,+や-の前に数字があるならそれは符号ではない.

G. Area of Polycubes
3次元上に1個ずつ1*1*1の立方体を配置していく.(100個以下)
連結の定義は面で接していること.(中心間のマンハッタン距離が1)
もし,連結でなくなるときがあるなら,それが起こるときを指摘する.
もしくは,既に配置した場所に配置した場合もそれを指摘する.

最終的にできた物体の表面積を求める問題.
6nから接した面の数を引いていけば良い.

H. The Two Note Rag
2^Pで10進数で下R桁が1か2のみからなる最小のPを求める問題.
Rは20以下.

下1桁が2となるのは周期4で起こる.( 1→2→4→8→6→2→4→8→… )
なので,Rが2以上のとき,4飛ばしで調べていけば良い.
下2桁が1と2のみとなるのは周期20で起こるので20飛ばしで調べていけば良い…,
下3桁だと周期100,以下周期は5倍5倍になっていくらしい.
詳しくはofficial siteからリンクが張られている論文(pdf)を参照.

I. Joe's Triangular Gardens
読んでない.

North America - Mid Atlantic - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

A. Close Enough Computations
ある食品に含まれる脂肪,炭水化物,たんぱく質,カロリーが四捨五入した状態で与えられるので,矛盾がないか調べる問題.
脂肪は1グラム9カロリー,その他は1グラム4カロリー.
単に,考えられる区間を計算するだけ.

B. I-Soar
区間[x1,x2]に障害物があるといったような情報が与えられるので,区間[0,L]の間に障害物がない部分の長さの合計を計算する問題.
計算量は障害物の数の2乗オーダーで十分通る.なのでやるだけ.

C. Trie, Trie Again
読んでない.

D. Lawrence of Arabia
DP + 枝刈り.
一直線に1000個以下(n)の1以上5以下の数字が並んでいる.
1000回以下(m),並んでいる数字を区切ることができる.
各ブロックのスコアは,ブロックから2つの数字を選んでその積の和.
最終的にスコアを最小化する問題.

単純にDPすると O(m*n^2) となるのでTLE.
数字が1から5までしかないのと,ブロックのサイズが増えれば,そのブロックのスコアが飛躍的に上がるので,適当に等分割に分けてもそれほど悪い解ではないはず.
なので,そのGreedyに分けた場合のスコアを用いて適当に枝刈りすれば通った.

E. Series / Parallel Resistor Circuits
各点の間にある電気抵抗が与えられる.点の数は26以下.
2つの電気抵抗は,直列だと足し算,並列だと逆数の和の逆数の1つの抵抗と等価である.
それのみを利用してある2点間の抵抗を求める問題.
それだけでは求めれない場合や,そもそも連結でなかったりする場合はそれを指摘する.

以下の処理を繰り返すだけ.
 まず並列な部分を問答無用で処理する.
 後は,始点と終点以外で,2つの抵抗と繋がっているところを直列の式で直していく.

F. Combination Lock
金庫みたいな鍵で数字が何々になるまで回して回してを繰り返すタイプの鍵.
最悪ケースで,いくら回転させれば鍵が開くかを求める問題.
やるだけ.

G. Stems Sell
読んでない.
文字列置換実装問題?

H. Signal Strength
単純DP.
ノード数1000以下のDAGが与えられる.枝は数字の小さいノードから大きいノードにしか張られていない.
ノード0からノードn-1まで移動するのだけど,各ノードを通過するごとにノードごとに設定された定数倍されて,枝を通るごとに枝ごとに設定された定数倍される.
最初ノード0で1だったらノードn-1で最大で幾つになるか,求める問題.
たどり着けないなら0を返す.

SRM432 DIV1/DIV2 (この記事を編集する[管理者用])

2009年01月06日21時から.
[ match overviws ] [ otinn.com summary (Japan) ]

Ad-hocな問題セット.偏見かもしれないけどTopCoderらしい問題.
こうやれば良いのだろうという直観力と,これで本当に良いのか確かめる論理力,両方必要.
こういう問題をあっさり解く人は頭良いと思う.

DIV1 EASY / DIV2 MEDIUM (250pt / 500pt)
2次元の格子上にランプがついていたりついていなかったりする.
1回の操作で1つの列を選んでその列のランプを反転させる.
厳密にK回の操作の後,全てのランプがついている行の数を最大化したい.
何行達成できるかを求める問題.

全ての行は一緒に変わるので,同時に全部のランプがつくならば初期状態は一致してなければいけない.
後は,各行全てランプつけることができるかどうかを調べて,その行と同じ行の数を調べる.

DIV1 MEDIUM (500pt)
同じ文字は連結してる文字列をgroupedと呼ぶ.
50個以下の文字列が与えられたとき,それらを適当な順番でくっつけてgroupedな文字列を作ってくださいという問題.
作り方がたくさんある場合,作れない場合はそれを指摘する.

まず,最後の文字と最初の文字が一致する2つの文字列を連結させる.
ただし,1種類の文字からなる文字列は先に処理する.
後は適当につなげて,groupedになっているかどうか調べて,なってなければ作れない.
文字列がそもそも1種類まで落ちたらそれが答え,それなければ複数ある.

DIV1 HARD (1000pt)
50個以下の町があって,最初につながっている道路が与えられる.
各町には最初に建っている家の数が与えられる.

目的は,まず道路を作って連結にさせる.
次に,家を1個ずつ建てて,各町に建っている家の数を目標の数に一致させる.

道路を作るコストは,繋がっている2つの街の家の数 * 定数.
家を作るコストは,(作る街とそれと連結されている街の家の数) * 定数(作る街ごとに異なる).
コストを最小化する問題.

家を作る順番は,家を作るコストの定数が高い街から順番に作れば良いことがわかる.
家を作る順番を固定してしまうと,枝ごとにその枝を張ってしまうことで増えるコストを計算できる.
後はMSTみたいな感じでやるだけ.

DIV2 EASY (250pt)
同じ文字は連結してる文字列をgroupedと呼ぶ.
与えられた文字列の中にgroupedのものが幾つあるかを求める問題.

DIV2 HARD (1000pt)
2次元平面上に50個以下の点があって,それぞれの点に点数がついている.
直線を引いて,点を2つに分けて,両側の点数の和の差を最小化したい.

Oceania - South Pacific - 2008/2009 (この記事を編集する[管理者用])

9問.
Link先はLiveArchive.(同じコンテストの問題番号は連番だと良いのになぁ…)
[ Link ]

A. Being Late
授業の正式な終了時間と実際の終了時間のログが与えられるので,平均でいくら延長しているかを求める問題.
早めに終了した授業については延長時間0で計算する.
やるだけ.

B. Money Lesson
移動後の各人が持っている5円玉,10円玉,20円玉の枚数が与えられる.
最初みんな同じ金額をもっていたけど,先生が1枚だけ移動させた(同じ場所に戻すのも含む).
さて,今もっている額は全員同じか,そうでなければ一番多い金額を持っている人,少ない金額を持っている人の名前を出力する問題.
やるだけ.

C. Explorer's Diary
文字列処理.
縦書きで1単語ごとに列を変えながら書いたので,元の文章を復元する問題.

D. Pattern Finder
100*100以下のサイズの升目に整数が書かれている.
最小の整数が書かれている升目のどれかから,最大の整数が書かれている升目のどれかにたどり着きたい.
上下左右に動けるけど,各ステップでの増分は一定値でなければいけない.

どの方向から辿り着いたかを記憶しておけば公差はわかるので,升目の数*4程度のノードのグラフ上でBFSするだけ.

E. Takeshi Castle
竜神池.
2次元平面上に石が50個以下あるので,最初の石から最後の石まで飛び移る.
挑戦者は30000人以下でそれぞれジャンプできる最大距離が与えられている.
風雲たけし城は難しくなきゃ風雲たけし城じゃないので,挑戦者のうち半分以上はクリアできないで欲しい.
ちゃんと,半分以上の人はクリアできませんか,判定する問題.

クリアに必要な最大ジャンプ距離を求めて,挑戦者をなぞる.
必要最大ジャンプ距離を求めるのは,Kruskalの要領で求めた.

F. Balanced Races
レースに参加したい人の実力と,1回のレースで参加できる最大人数(100以下),レース回数の最大数(100以下)が与えられるので,
同じレースに参加する実力差が最も大きい人の実力差を最小化する問題.

DPで何とかなったりするのかもしれないけど,素直に2分探索 + Greedyで良いと思う.

G. Smoker's Walk
サイズ100*100以下の2次元の升目上をある場所からある場所まで移動する.
そのとき,障害物(500個以下)があって,障害物に接触することはできず,移動したパスと障害物との距離の和を最大となるようなパスを選択したい.
距離はマンハッタン距離.
最大値を求めてください,という問題.

H. P2P Currency Service
300個以下のトレード要求がある.要求は自分が出すもの,自分が欲しいものといった形式.
自分が出すものが相手は欲しくて,自分が欲しいものが相手の出すものならばトレードできる.
ただし,自分自身とはトレードできず,各人トレードは1回しかできない.
考えうるトレードの最大回数はいくらか?

最大マッチング.

I. Currency Shopping
100種類以下の通貨の両替の際のレートが与えられる.
ある通貨をある通過に両替したいとき,他の通貨を経由しても良いので,最大でいくらのレートで両替できるかを求める問題.
ただし,無限に大きくできる場合は,それを指摘する.

Warshall-Floydみたいにやるだけ.
表示は小数点以下4桁を切り捨てで表示してくださいと書いてあるように見えるんだけど,それだとWAで普通に四捨五入したら通った.

Appendix

Recent Articles

ブログ内検索

Ads


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