2012-03-22
SRM 538
Div1 Easy (250) EvenRoute
問題
- N個の点が与えられる。
- 初期位置が(0,0)で、N個の点の全部を1回だけ経由するものとする。
- 位置のパリティがwantedParityと一致するかどうかを求める。
方針
- サンプルを読まずに適当に解く
- 死亡
- 解きなおし
- パリティは途中経路に関わらず、始点と終点との関係で決まる
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/EvenRoute.cpp
Div1 Medium (450) TurtleSpy
問題
- 左右の回転と前後の移動が可能なスパイロボットがある。
- N個のコマンド列が与えられ、それぞれを1回ずつ実行する。
- 最も遠くに移動できるような順番で実行したときの距離を求める。
方針
- 前進と後退それぞれをまとめた方が良さそう
- なるべく遠ざかるように角度を決めればよいのでは
- 180度に近づけるためにDPすればいけそう
- 角度で使わないやつは最初か最後に浪費させればよい
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/TurtleSpy.cpp
Div2 Easy (300) LeftOrRight
問題
- LかRからなるコマンド列が実行可能な機械がある。
- Lは左に、Rは右に一歩進む。
- コマンド列の一部が破損して?になっている。
- 破損したコマンドをLかRに補ったとき、初期位置から最遠点の距離を求める。
方針
- うしろからやるのかな...失敗
- 全ての?をLとRのどちらかに置換したときが最大
- 単純に、?が全部Lなのと全部Rなのの両方試せば良さそう
- 配列で持つ必要なかった
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/LeftOrRight.cpp
Div2 Hard (1050) SkewedPerspectives
問題
- 3色のブロックと、1x2の大きさの黒いブロックがある
- 幅w以内で縦に積む
- 横から見たときの図が与えられる
- その図になるように積めるかどうかを求める
方針
- analysisとkusanoさんのを読む
- 黒いブロックが偶数のときはただ積むだけ。奇数の場合に色々やればよい
- 奇数の黒いブロックは、横に積んで一つ隠す
- 一番下を1つだけ黒にすることはできないので、はじく
- 途中で黒が奇数のときは、今積んでいる列をやめて、うしろに今の位置-1個を積んでから、黒を積む
- ただし一番下が黒かつ奇数のときは、まず黒を積み、うしろに1個積んでから黒を積む
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/SkewedPerspectives.cpp
結果
xx- 237.62*0 + 187.57*0 - 25 = -25 rating 1516 -> 1322
落ち着きと集中力を欠いた。しかし良い練習になった。
easyは基礎なのだが苦手。引数名の通り、パリティを求める問題。
mediumは提出したコードに二箇所バグがあった。具体的にはDPで同じ配列に代入していたので、最長になっていなかった。初歩だがいったん書くと発見しづらいので、計算量に余裕があるなら冗長でも丁寧に書くべき。しかし方針は合っていたようなので、前回（通ったが実装自体は単純）よりも、できた感じがした。
div2easyは珍しく300点。再帰で書くと2^50回呼ばれるから死亡。なるほど。
div1残留があぶなくなったので、次回は慎重にeasyを通すようにしたい。それとTCO楽しみ。
2012-03-21
SRM 537 Div2
練習
Hard (1000) PrinceXToastbook
問題
- N冊の本がある。
- そのうちの何冊かは、別の本を読んでからでないと理解できない。
- ランダムにN冊読むとき、理解できる冊数の期待値を求める。
方針
- わからん
- uwiさんに教わる
- 事前知識を親として自分が子というグラフとして考える
- 木とか森になっている
- 木が成立せず、閉路があると失敗する(閉路の部分がゼロになる)
- 木の場合、理解できる場合の数÷とりうる全ての場合の数を考えればよい
- 深さをdepthとすると、得られる知識は1.0÷depth!
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/PrinceXToastbook.cpp
感想
赤い人に教わるという贅沢。
まず制約条件から、どういうものなのか(グラフで表せるのかとか)を描くべき。
閉路検出は最初、自分に戻ってくるかどうかを判定したら無限ループした。すばらしいテストケース! 深さがノード数を超えたら閉路、でよい。
2012-03-18
SRM 537 Div1
Easy (275) KingXNewCurrency
問題
- アヒルの国の通貨は価値Aと価値Bの二種類ある。
- 王がAとBに飽きたので通貨を価値Xと価値Yに変更することにした。
- 変更後もAB貨幣システムでの価格が使えるYは何通りあるかを求める。
方針
- P=A*n+B*mが表せることが必要
- GCDとLCMかな...と思い込んでだいぶ時間を浪費
- いろいろ書き直す
- A=X*i+Y+j、B=X*i+Y*jと表せればよさそう
- 全部満たす場合(-1)の判定条件を書き間違ったまま提出
- 書き直し
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/KingXNewCurrency.cpp
Medium (500) KingXMagicSpells
問題
- アヒル王国の王宮に部屋がN室ある。
- それぞれの部屋にはducks[i]匹のアヒルがある。
- 国王は一日一回、魔法の呪文を唱えることができる。
- 呪文はSpell 1とSpell 2の二種類で、唱える確率は1/2ずつである。
- Spell 1の効果は、各部屋のアヒルの数がXORされる。
- Spell 2の効果は、各部屋のアヒルが一斉に部屋spellTwo[i]に移動する。
- K日後のゼロ番目の部屋のアヒルの数の期待値を求めよ。
方針
- doubleに突っ込んでみる
- 小数点のXOR...? 意味がわからない
- 1ターン毎に考えると、移動かXORしかない
- ビット毎に独立して考えてよい
- 桁毎にdoubleで持ってターン毎にシミュレーションしてみる
- サンプルと合ったので提出
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/KingXMagicSpells.cpp
結果
xo- 134.77*0 + 289.96 + 0 = 289.96 218th rating 1404 -> 1516
easyは40分かかって提出。mediumがぎりぎり解けそうだったので見直せなかった。凡ミス。10分くらいかけて方針を書き出したりしてもよかった。
mediumは残り30分でいけそうだったので書いた。medium解けるチャンスはほとんどないので、解けそうな回で通ったのは嬉しい。問題としては唯一div2hardで解いたことがあるSRM518に近い感じだった。
三月だけでレートが+320と、ラッキーが重なっていきなり黄色に。今年の目標（GCJ R1突破、一瞬黄色になる）の片方を早くも達成してしまった。とはいえまだeasyを落とすレベルなのでeasyメインで取り組む。
2012-03-11
SRM 536 Div2
練習
Easy (250) BinaryPolynomialDivTwo
問題
- P(x) = a[0] * x^0 + a[1] * x^1 + ... + a[n] * x^nという多項式がある
- a[i]は0か1のいずれかである
- xとして0か1のいずれかを与える
- a[n]は必ず1が与えられる
- x^0は1である
- P(x) mod 2が0の場合がいくつかを求める
方針
- x=0の場合、和はa[0]
- x=1の場合は、全部の和 mod 2
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/BinaryPolynomialDivTwo.cpp
Medium (500) RollingDiceDivTwo
問題
- 面の数が不明なサイコロがx個ある
- それぞれの面の数は1から9のいずれかであり、出目の確率は等しい
- n回サイコロを振った出目が与えられる
- 面の数の合計の最小値を求める
方針
- 各試行をソート
- 各試行のi番目の試行のうちの最大値を保持
- 最大値を合計
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/RollingDiceDivTwo.cpp
Hard (1000) MergersDivTwo
問題
- n個の会社があり、それぞれの利益が配列で与えられる。
- 会社を合併すると、新会社の利益は、各社の利益の総和÷社数となる。
- 合併には少なくともk社必要で、最終的には1社になる。
- 最終的にできる会社の利益の最大値を求める。
方針
- ソートするとか基本部分はdiv1easyと同じ
- k社ずつ合併できる場合は最大回数を選べばよい
- そうでない場合つまり(n-1)%(k-1)がゼロでない場合は、この余りを何回目に配分するかの判断が必要
- まず全試行だけど最適解でないとわかったら打ち切るメモ化っぽいのを書いた
- 次に、i番目からj個併合した最大値を保持するようにしたDPで書いた。このほうがシンプル
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/MergersDivTwo.cpp
感想
easyとhardのクラス名が交換されているというのがしゃれがきいている。
easyは長文なので読解&早解きの会。
mediumの正答率は97%だったようでchallenge phaseは暇だったと思われる。
hardはdiv1 easyの制約条件が違うだけなのだがだいぶ難しい。DP書く練習になった。
2012-03-08
SRM 536 Div1
三ヶ月ぶりのdiv1参加
Easy (250) MergersDivOne
問題
- いくつかの会社があり、それぞれの利益が配列で与えられる。
- 会社を合併すると、新会社の利益は、各社の利益の総和÷社数となる。
- 最終的にできる会社の利益の最大値を求める。
方針
- なんか赤字のとこからマージしてくと良さそうなのでまずソートする
- これ最小のとその次のマージするのを繰り返せば、赤字の効果が最も薄まるんじゃ
- 一度に任意の社数をマージできるけど、2で良さそう
- sample通ったのでとりあえずsubmitして検算する
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/MergersDivOne.cpp
Medium (500) RollingDiceDivOne
問題
- N個のサイコロがある。
- それぞれのサイコロの面は1からk=dice[i]までの番号が振られていて、出目の確率は等しい。
- 最も出やすい出目の合計値を求める。複数ある場合は最小値。
方針
- 個々の期待値は(1+k)/2
- 足すと1が含まれているサンプルが合わない
- 1のとき場合わけするとサンプルと合うのでとりあえずsubmit
- 何人かresubmitしてるので読み直す
- 自分を撃墜するパターンは見つけたが、実装間に合わず
- 終了後解き直し
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/RollingDiceDivOne.cpp
Hard (1000)
openだけしてみた。
結果
ox- 235.23 + 395.84*0 + 50*1 = 285.23 174th rating 1258 -> 1404 (+146)
できすぎな結果。
easyはsubmitしてから落ち着いて考えて、計算手順は合ってそうだが、誤差死するのかどうか確認したりした。一意に定まるので、誤差が出ることはなかった。
setに突っ込んでいる人が落ちていたのだが、理由は同じ値が消えるためだった。よくある不具合だが実行しないとわからなかったので、修行が足りない。
mediumはとりあえずサンプルは合って、div1mediumがそんな簡単なわけはないと思ったがやはりそうだった。しかしコーナーケースはわかったので、最速で1撃墜した。
最後だけ大きいケースの場合が、それまでの最大値+1になるのは、パターンを書いてみて直感的には理解した。最後の出目を加えたパターンは、最大値+1までは場合の数の分布になり、最大値+1のところから先は変化しなくなるから、みたいな感じ。
ちなみに和をaccumulateで求めるとoverflowするというおまけつきだった。