Entries

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

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

PKU 3720 - Occurrence of Digits (この記事を編集する[管理者用])

POJ Monthly Contest - 2009.02.22
[ Link ]

[ 問題概要 ]
 1/2 = .5
 1/6 = .1(6)
といったように分数を循環小数で書くことを考える.
nとkが与えられたとき,
 1/2, 1/3, ... , 1/n
の循環小数表示にkが何個含まれるかを求める問題.
nは100以下,kは0から9.

[ 解法 ]
やるだけ.

PKU 3719 - Art of Balance (この記事を編集する[管理者用])

POJ Monthly Contest - 2009.02.22
[ Link ]

[ 問題概要 ]
ツリーが与えられて,葉に錘をつるす.
葉につるす錘を適当に入れ替えることができて,それぞれ,つりあう点が真ん中からずれている長さの和を最小化する問題.
問題文の絵を見ると分かりやすい.
錘の数 = 葉の数は16以下.

[ 解法 ]
普通にDPするだけ.
O(4^16)では間に合わないので,効率悪い実装はしないように気をつけるだけ.

PKU 3716 - Panda's Birthday Present (この記事を編集する[管理者用])

POJ Monthly Contest - 2009.02.22
[ Link ]

[ 問題概要 ]
4つのサイコロがある.24面それぞれは赤か青のどちらかに独立に等確率で塗られる.
まず,4個サイコロを一度に振ったら赤の個数はp個で,次に4個振ったら赤はq個だった.
次に4個サイコロを振ったら,赤の個数の期待値はいくらになるか,という問題.

[ 解法 ]
よくよく考えると簡単なのに,何故か中々正しく計算できなかったのは僕だけだろうか….
答えは書かないけれど,計算すると単純な式で表される.

まず,4個ではなく1個のサイコロしかない状況を考える.
最初に赤,次に赤だった場合,3回目に赤が出る確率は…,
 各面が:赤,赤,謎,謎,謎,謎となるのは,確率5/7で,この場合3回目赤になるのは2/3
 各面が:赤,謎,謎,謎,謎,謎となるのは,確率2/7で,この場合3回目赤になるのは7/12
なので,27/41等といった感じで計算する.
上は1回目と2回目で出た面が違う場合,下は1回目と2回目で出た面が同じ場合,謎の面は確率1/2で黒なので,それぞれの確率が5/7と2/7となることに注意する.

後は,ちょっと考えると,サイコロが4つになっても,それぞれ独立に考えることができるというのがわかるはず.

PKU 3715 - Blue and Red (この記事を編集する[管理者用])

POJ Monthly Contest - 2009.02.22
[ Link ]

[ 問題概要 ]
N人の人がグループ0またはグループ1に属している.
また,M個の友達関係が与えられる.(ノード数N,枝数Mのグラフ)
N人の中から最小人数をグループから脱退させて,グループ0とグループ1の間をまたぐ友人関係の人を無くす問題.
誰を脱退させるか,最適解がたくさんあるなら辞書順最小を求める.
Nは200以下,Mは20000以下.

[ 解法 ]
脱退させる人数の最小数は二部グラフのマッチングで求まる.
辞書順最小を求めるのは,番号の小さな人から1人ずつ脱退させてマッチングを求めて,マッチングが減るなら脱退させる,というのを繰り返す.

PKU 3717 - Decrypt the Dragon Scroll (この記事を編集する[管理者用])

POJ Monthly Contest - 2009.02.22
[ Link ]

[ 問題概要 ]
TopCoder SRM434 DIV1 HARDとほとんど同じ.
違うのは文字列の長さの制限が500以下になっていることと,辞書順の定義が違う.

[ 解法 ]
基本戦略はTopCoder SRM434 DIV1 HARDとほとんど同じ.
単純にやるとTLE食らうので,適当に自明な枝刈りを入れると通った.

闘神3 / Lv.77 / Vit.15433 / Att.2013 / Def.577 (この記事を編集する[管理者用])

ハードモード,強制セーブ1まで進んだ.
中間デモ以降は,なんか雑魚敵に比べて固定敵が弱い気がした.さくさく進めた.
一番苦戦したのがはらぺこハニー,ボス戦は魔法でごり押してたのだけど,やつには通用しなかった.

このままストーリー進めるかレベル上げするか….
狂王強い.体力が150万近くあるし,攻撃も一発で9万近く食らう….

闘神3 / Lv.16 / 795-154 (この記事を編集する[管理者用])

タイトルはLv. / 活力-攻撃.

ついにハードモードやり始めてしまった.
今度はのんびりやっていこうと思う.

現在,教会と貯水池.
地味に難しくなってる…,逃走スキルセットしておくのは必須だね….
でも,そろそろ普通にお金が貯まるようになってきた.

ハードモードはなんか魔法が最初から使えるし,優遇されてるみたいだったので,
今回はちょくちょく使ってみてるんだけど,魔法強いね.
ボスは魔法でごり押してる.

続きを読む

Another high quality contest (この記事を編集する[管理者用])

2008 ACPC Alberta Collegiate Programming Contest
UVa 11577 - 11586

2009年02月21日18時から5時間,10問.
[ Link ]

A. Letter Frequency
文字列が与えられて,最も出現頻度の高いアルファベットを出力する問題.
大文字小文字は区別しない.答えが複数あるなら全部出力する.

B. Situp Benches
DP + 経路復元.
少し面倒だけど書くだけ.

C. Triangle Trouble
使える辺の長さが10000個以下与えられる.
それから3つ選んで三角形を作ったとき,面積の最大値を求める問題.
作れないなら0を返す.

辺の長さでソートして,隣接する3つの辺を使う場合のみ調べればよい.

D. Finding the Transmitter
入力,出力は緯度経度.
点A,Bの座標と,A,Bと北極点および点X間の角度が与えられたとき,点Xを求める問題.

E. Grid Successors
3*3のグリッドが与えられる.各マスには0か1が書かれている.
1回変形すると,各マスの数字は,隣接する数字の和 mod 2 に変形される.
ループに入るまでに何回変形できるかを求める問題.

サイズが小さいので,馬鹿っぽく書いても十分通る.

F. Colossal Fibonacci Numbers!
f(x)をフィボナッチ数とする.
 f(a^b) mod n
を求める問題.
aとbは2^64未満,nは1000以下.

鳩ノ巣原理より,f(x) mod nは周期n*n以下.
後は周期を求めて適当に計算するだけ.
実際にはnが1000以下なら周期は最大で3000程度.

G. Alien DNA
10000個以下の文字列が与えられる.
いくつかの連続する文字列に分ける.
ただし,同じグループ内の文字列には,最低1文字は全部に含まれる文字がなければいけない.
最小で幾つの文字列に分ければよいか.

Greedyにやるだけ.

H. Partitioning by Palindromes
文字列を連続する複数の文字列に分ける.
それぞれの文字列は回文でなければいけない.
最小で幾つの文字列に分ければ良いか.
最初の文字列の長さは1000以下.

回文かどうかを判定するのはDPでできる.
で,最小の分け方を求めるのもDPでできる.

I. Nurikabe
パズルのぬりかべ.
黒く塗った結果が与えられるので,それが問題の解となっているかどうかを判定する問題.
行数,列数は1以上100以下.

実装問題.書くだけ.

J. Train Tracks
細長いピースが50個以下与えられる.
両端が窪んでいるか出っ張っているか与えられる.
窪んでいるのと出っ張っているのをつなげることができる.
ただし,同じピースの両端はつなげることができない.
全部を使って大きなループを作ることができるかどうかを判定する問題.

ピースが1個だとできない.
そうでなければ,出っ張っている数と窪んでいる数が一致していれば作れる.

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

会津大学のオンラインジャッジは,制限時間が緩くて,簡単な問題も多くて,初心者にはとても良いと思う.

[ Link ]

[ 問題概要 ]
人生に絶望し,余生をMMORPGに捧ぐことを決めた.
しかし,MMORPGの世界では効率が全てだった.
ある街からある街へ移動するのに最も良い効率を求める問題.

具体的には,ノード数1000以下,枝数1000以下の無向グラフが入力として与えられる.
枝には,その長さとその道中で得られる経験値が与えられる.
あるノードからあるノードまで移動するのに
 獲得経験値 / 総移動距離
の最大値を求める問題.
ただし,移動する方向は,厳密に目的のノードに近づく方向にしか進んではいけない.

[ 解法 ]
まずは,目的地からダイクストラして,それを基に各枝に対して進める向きを限定する(両端が同じ距離なら両方向とも進めない).
そうするとグラフはDAG (閉路のない有向グラフ) に落ちる.

後は2分探索 + DP.
具体的には,効率c以上のパスがあるのと,枝の重みを
 その枝の獲得経験値 - c * その枝の長さ
としたグラフ上で,枝の重みの総和が0以上となるパスが存在することとは同値.
DAG上で,重み最大の路を見つけるにはDPすれば良い.

UVa 11571 - Simple Equations - Extreme!! (この記事を編集する[管理者用])

Contest of Newbies V.

ようやく通った….
誤差に強いコードを書くべし.

[ Link ]

[ 問題概要 ]
1以上6*10^18以下の自然数A, B, Cが与えられたとき,
 x + y + z = A
 xyz = B
 x^2 + y^2 + z^2 = C
となるような,互いに異なる整数x, y, zを求める問題.
複数なるならばxが最小となるもの,次にyが最小となるものを選ぶ.

[ 解法 ]
根と係数の関係から,x,y,zを根とする3次方程式は
 X^3 - A * X^2 + (A^2 - C)/2 * X - B = 0.
例えば,ニュートン法 + 二次方程式の根の公式とか.

TJU 3184 - Government Help (この記事を編集する[管理者用])

CTU Open 2008 問題H
[ Link ]

[ 問題概要 ]
n個の与えられた正整数を順番に2人に分け与えていく.
与える順番は自由,どちらに何個与えるかも自由.
与えた瞬間瞬間に,2人に与えた数字の和の差を考えて,その最大値を最小化したい.

どんな順番で誰に分け与えると良いかを出力する問題.
答えが複数ある場合は,どれを出力しても良い.

正整数は100000以上199999以下.

[ 解法 ]
正整数の最小値と最大値は2倍以上差がつかないのがポイント.
与えられた数字のうち,最小のものが和の最大値とすることができる.
交互に2人に与える.最初に最小のものを与えて,後は大きい順に与える.
図を描くと振動していく様子がわかるはず.

TJU 3185 - Tree Insertions (この記事を編集する[管理者用])

CTU Open 2008 問題I
[ Link ]

[ 問題概要 ]
数列が与えられるので,数列から二分探索木を作る.
では,そのような二分探索木となるような数列は何通りあるかを求める問題.

[ 解法 ]
多倍長 + DP + 二項係数.
先頭の数字を見て,それより小さいのとそうでないのでグループ分けする.
すると左右の小問題に帰着される.後は左右はどっちが先に来ても良いので二項係数をかける.

Pre-warmup contest (この記事を編集する[管理者用])

2009年02月14日18時から3時間,5問.

Waterloo ACM Programming Contest
February 8, 2009
UVa 11572 - 11576

[ Link ]

A. Unique Snowflakes
数列が与えられるので,連続した区間の中に同じ数字が2個ないような最長の区間の長さを求める問題.
ハッシュを使ってO(n)にするとか.
C++ならmapを使うと楽.

B. Ocean Currents
1000*1000以下のグリッドが与えられる.
それぞれのマスでは隣接8方向のどこかに向かって海流が流れていて,そっちの方向へはコスト0,その他の方向へはコスト1で移動できる.
ある場所からある場所に移動するのに必要な最小コストを求める問題.

キューを2つ使った幅優先探索.
ダイクストラでも良いかなと思ったけど,僕はTLEだった.

C. Colliding Traffic
幾何,二次方程式.
1000個以下の質点が等速直線運動をしている.
初めて2質点間の距離がr以下となる時間を求める問題.

各質点間の距離に対して方程式を解くだけ.

D. Zerg Rush!!!
シミュレーション.
隣接した場所に敵がいれば攻撃,それでなければ一番近い敵に近づく,といったアルゴリズムで
戦略シミュレーションゲームっぽいものをシミュレーションする問題.

問題文の移動方法の記述が曖昧でよく分からない.
とりあえず,通らない.

計算時間をO(ターン数*マップのサイズ)にすることが大切.
例えば,一番近い敵に近づくのに,毎ターン敵味方2回BFSすれば良い.

E. Scrolling Sign
K文字の文字列がN個与えられる.
N種類の文字が全部与えられた順番に含まれるような最小の文字列の長さを求める問題.

やるだけ.

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

2009年02月08日02時から.
[ match overviws ] [ otinn.com summary (Japan) ]

EASY - FindingSquareInTable (250pt)
1桁の数字が書かれた9 * 9以下のグリッドが与えられる.
x座標y座標がそれぞれ等差数列となるようにグリッドに書かれた数字を並べてできる平方数を探す問題.
たくさんあるならもっとも大きいもの,ないなら-1.

全探索するだけ.

MEDIUM - HexatridecimalSum (500pt)
36進数で書かれた数字がいくつか与えられる.50桁以下.
k種類の文字をZ(35)に変えることができるので,和を最大化する問題.

各文字をZに置き換えたときの増分を求めておいて,大きいものからk個採用する.
まあ,やるだけ.

HARD - IncreasingLists (1000pt)
50文字以下の文字列が入力.
?を,または数字に置き換えて,増加列を作る問題.
たくさん作ることができるなら辞書順最小のものを求める.

とりあえず,増加列を作れるかどうかを判定するルーチンを作って,
一番最初に登場する?の部分を,0123456789と順番に代入してまだ作れるならそれを採用する,ということを繰り返す.
増加列を作れるかどうかの判定が結構面倒.

LiveArchive 4382 - YAPTCHA (この記事を編集する[管理者用])

Europe - Central - 2008/2009 問題A
[ Link ]

[ 問題概要 ]
問題文で定義されているS_nを求める問題.
nは100万以下.

[ 解法 ]
シグマの中は0か1.
シグマの中が1となるのは (3k+6)! = (3k+6) mod (3k+7) となるとき.
これは 3k+7 が素数であるとき.
なので,エラトステネスの篩で素数をカウントしていけば良い.

LiveArchive 4229 - A No-Win Situation (この記事を編集する[管理者用])

North America - Southeast - 2008/2009 問題G
[ Link ]

[ 問題概要 ]
ブラックジャック.
ディーラーの戦略は固定されていて,数字が17以上になると引くのをやめる.
デッキが与えられたとき,プレイヤーが勝つことができるかどうかを判定する問題.
細かいルール等は問題文に書かれている.

[ 解法 ]
シミュレーション.
全通り試してみるだけ.

LiveArchive 4228 - Fred's Lotto Tickets (この記事を編集する[管理者用])

1問ずつでも書いていってみようかと思う.

North America - Southeast - 2008/2009 問題F
[ Link ]

[ 問題概要 ]
6N個の1以上49以下の自然数が与えられるので,49種類の自然数が全て,少なくても1個は含まれているかどうかを判定する問題.

[ 解法 ]
やるだけ.
ジャッジがバグってたので指摘してたのだけど,昨日ぐらいにRejudgeされたみたい.

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

[ Link ]

[ 問題概要 ]
10000個以下の数列をソートするのに必要なコストを最小化する問題.
数列に含まれる数字はユニークで,100000以下の自然数.
できる操作は任意の2つを入れ替える操作のみで,それにかかるコストは入れ替える2つの数字の和.

[ 解法 ]
やるべき操作を巡回置換で考える.
それぞれの巡回置換で,要素が1つだけならコスト0,2つなら数字の和がコスト,3つ以上なら下の2つのうち小さい方
 (1) SUM + M(N-2)
 (2) SUM + M + m(N+1)
ここで,SUMは巡回置換内の数字の和,Nは循環置換内の要素の数,Mは巡回置換内の最小要素,mは数列全体での最小要素.
(1)は巡回置換内で,一番小さい要素を順番に動かしていく方法に対応,(2)は最初に一番小さい要素と巡回置換内で一番小さい要素を入れ替えてから(1)を行う感じ.

Appendix

Recent Articles

ブログ内検索

Ads


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