2012-03-04
SRM 535 Div2
Easy (250) FoxAndIntegers
問題
- A-BとB-CとA+BとB+CからA、B、Cを求める。
方針
- 安全にいく
- (A-B)と(A+B)を足したら2Aになる。BとCも同様
- 2A、2B、2Cが偶数かつ、引数の条件を満たすかチェック
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndIntegers.cpp
Medium (500) FoxAndGCDLCM
問題
- 最大公約数Gと最小公倍数Lが与えられる。
- GとLを満たす数AとBの和の最小値を求める。
方針
- LがG未満とかのケースは不能としてはじく
- ぐぐるとA×B=G×Lだが、直接役には立たない
- 別の表現をするとA=x×G、B=y×G、x×y×G=L
- すなわちL÷G=x×y
- (xとyの和の最小値)×Gが答え
- xとyの組み合わせを因数分解して全探索するのは面倒
- 範囲は1～sqrt(x×y)、たかだか10^6だから全数探索すればいいや
- sample4が合わない
- AとBのGCDがGになるためには、xとyは互いに素、つまりxとyのGCDは1
- 合った!
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndGCDLCM.cpp
Hard (1000) FoxAndSorting
問題
- 0から1000000000000000000までの数を、桁の数値の和で、和が同じもの同士は辞書順で並べる。
- idx番目の数値を求める。
方針
- DPぽい
- analysisを写経
- [ある桁数以下][和がS]のテーブルを作成
- S未満までの位置がわかったら、1桁ずつ確定させていく
- その際、同じテーブルが使える
- これは自力で書くの無理
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndSorting.cpp
結果
oo- 240.45 + 296.80 = 537.25pt 63rd 1196 -> 1258
div1! 100位以内に入れればいいやと思ってたので目標はクリア。
easyは手抜き実装すると落ちるので、良いdiv2easyだと思った。実際偶数チェックしてない人とか、引数チェックをコピペミスしてちゃんと書けてない人とかいた。撃墜は遅くて間に合わなかった。
mediumは自信ないのでGCDとLCMをぐぐったら基本的すぎてあまり載ってなかった。和が最小になるのは、xy=aとx+y=bの接点ぽい感じでxとyが近い数になるとき。なのでsqrt(xy)から試行すればminで更新する必要ないかも。あとGCCには__gcdがあるのでそれ使えばよかったとか。点数はいまいちだけど最終的にはよかった。challengeは、単純なバグ持ちの人は即落とされて、バグってはいるけどサンプルは通るみたいな人だけ残ったので、控えた。
hardはopenしたけど全く見当がつかなかったので残り時間はmediumを見直した。
2012-02-25
SRM 534 Div2
Easy (250) EllysDirectoryListing
問題
- ディレクトリのファイルのリストがある。
- リストの最後がカレントディレクトリとルートディレクトリでないとき、最初に見つかったディレクトリを末尾と交換する。
- それでもリストの最後がカレントディレクトリとルートディレクトリでないとき、最初に見つかったディレクトリを末尾のひとつ前と交換する。
方針
Medium (500) EllysCheckers
問題
- N個のマスからなる盤面がある。
- マスは空または駒が置かれている。
- 駒の右が空いていれば駒を一つ右に移動できる。
- 駒の右とその右が駒でその右が空いていれば、駒を三つ移動できる。
- 盤面の一番右の駒は直ちに取り除かれる。
- 二人のプレーヤーで交互に移動操作をする。
- 動かせなかったら負けとするとき、最初のプレーヤーが勝つかどうかを求める。
方針
Hard (1000) EllysFiveFriends
問題
- Ellyたちは5人でゲームをする。
- 円陣を組み、それぞれ数値を持つ。
- 1ターンでは隣同士の任意の2人の数値をピックアップする。
- 両方の数値が奇数であれば「りんごアクション」で両方の数値から1を引くことができる。
- 両方の数値が1以上であれば「オレンジアクション」で両方の数値を1/2できる。
- 全員の数値がゼロになると勝利となる。
- 何通りの勝利パターン数があるかを求める。
方針
- メモ化再帰
- メモ化領域のサイズと、処理時間がけっこうきつい
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_534/EllysFiveFriends.cpp
結果
225.30 + 310.77 + 50-25 = 561.07 87th rating 1152 -> 1196
限りなくブルーに近い緑
easyは、ディレクトリを消してから末尾に足しているのを撃墜した。TopCoderは解が決まっていて末尾の順序が違っても落ちるので、そこは狙っていた。
末尾がディレクトリの場合には先頭から2回ループする必要があるのだが、それをやってない人がいて、気づけなかった。まだまだチャレンジ精神が足りない。
mediumは2回連続メモ化再帰で解いたが、今回は偶数奇数判定すればよかった。まあ300点は取れたのでよしとする。
2012-02-24
SRM 533 Div2
Easy (250) PikachuEasy
問題
- ぴかちゅーは ぴ か ちゅー しかしゃべれない。
- 与えられた文字列がぴかちゅーが発音できるものかどうかを求める。
方針
Medium (500) CasketOfStarEasy
問題
- 星の器は東方銀河のエネルギー生成装置である。
- N個の器のそれぞれに星が格納されており、それぞれの重さが配列が与えられる。
- エネルギーの生成は、位置xを選択することで行う。
- 位置xの星を消滅させると、位置x-1と位置x+1の重さの積のエネルギーが得られる。
- 得られる最大のエネルギーを求める。
方針
Hard (1000) MagicalGirl
問題
- 魔法少女がN人の悪い魔女と戦う。
- ライフの初期値はMで、毎日1ずつ減る。
- 魔女はday[i]の日に出現する。
- 魔女に勝つ確率はwin[i]%で、勝つとライフがgain[i]増える。
- ただしライフの最大値はMである。
- 魔法少女の生存日数の期待値を求める。
方針
- 期待値DPらしい
- わからないのでAnalysisを読む
- ある一日に複数の魔女が出現する場合が問題
- ライフは増えるかゼロになるかだけなので、戦う順番は期待値に影響しない
- なので日付順に処理していってよい
- メモ化再帰 (std::mapだとTLEした)
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_533/MagicalGirl.cpp
結果
244.96 + 242.99 + 50*2 = 587.95 188th rating 1123 -> 1152
ナイスな問題。
easyは進めていくだけなのだけど、challenge phaseでJavaの人がreplaceAllしていたので、2撃墜した。ケースを事前に予測できてたらなおベターだと思った。easyは解くのより撃墜のほうが楽しいかも。文字列処理の典型的なミスり方は、(プロコン以外の)一般的なコーディングとしても参考になる。
mediumは順番を考慮する方法が思いつかなかったのでbitのメモ化再帰。div1easyの制約条件だと通らない。40分くらいかかってチャレンジなかったらレート下がるくらいの感じだった。easyが簡単かつ典型問題だと上位は厳しい。
hardはなんとなく解法を予想しただけ。残り時間がなかったのでmediumの見直しの時間に充てた。
2012-02-23
SRM 532 Div2
Easy (250) DengklekTryingToSleep
問題
- アヒルにAからBまでの番号がついている。
- 呼んだ番号が配列で与えられる。
- 呼んでいないアヒルが何匹かを求める。
方針
- とりあえず足せばいいか
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekTryingToSleep.cpp
Medium (600) DengklekMakingChains
問題
- 布切れの状態を表す3文字が与えられる。
- 文字はドットか数字である。
- 数字の部分だけをつなげることができる。
- 連続する数字の和の最大値を求める。
方針
- ドットがないやつと、左と右に分離
- 「数値ドット数値」は1回しか使わないようにする
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekMakingChains.cpp
Hard (950) DengklekPaintingSquares
問題
- N×Mのタイルがある。
- あるタイルに隣接するタイルの数が偶数になるように置く。
- 置き方の総数を求める。
方針
- 典型的なDPではある
- しめじたんのを読むが、自力では書けなさそう
- ありえる置き方を泥臭くテーブルで持ってみる
- なんとか書けた
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekPaintingSquares.cpp
結果
ox- 240.0+0=240.0 436th rating 1152 -> 1123
easyはソートして先頭と末尾から一発で求めればよいだけだった。
mediumは見直したのだけど落ちてしまった。submitしてからテストケースを作ればよかった。
2012-02-21
SRM 531 Div2
Easy (250) UnsortedSequence
問題
- N個の配列がある。
- 辞書順で、ソートされたものの次のものを求める。
方針
- ソートして、後ろから見ていって違う要素があったらそれと交換
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/UnsortedSequence.cpp
Medium (600) NoRepeatPlaylist
問題
- N種類の曲がある。
- P曲からなるプレイリストを作りたい。
- 同じ曲は間隔Mだけ空ける必要がある。
- 何通りのプレイリストが作れるかを求める。
方針
- 解けない...
- kusanoさんの解が短くてすごい
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/NoRepeatPlaylist.cpp
Hard (950) KingdomReorganization
問題
- 未着手→復習
- 王国にN個の都市があり、そのうちのいくつかは道路で結ばれている。
- ある都市とある都市の道路を作るコストと壊すコストが与えられる。
- 任意の都市間の経路を一つのみにするための最小のコストを求める。
方針
- 蟻本の最小全域木のプリム法ほぼそのまんま
- priority_queue + union find木
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/KingdomReorganization.cpp
結果
239.06 204th rating 1133 -> 1152
easy、next_permutationは気づかなかった。そんなに時間かかってないのでまあいいやという感じ。
mediumが解けないのは困ったもんだ。解けないけどこれは良い問題。