2011-05-29
SRM 507 Div2
Easy (250) CubeAnts 蟻さん集め
問題
- 蟻の位置がvector<int>で与えられる
- 蟻の移動時間を返す
考察
- maxを求める
- 距離は静的配列で持っておけばOK
実装
Medium (500) CubeStickers サイコロ色塗り
問題
- 六面体を、色が隣り合わないようにステッカーを貼る
考察
- 反対側なら同じ色が使える
- 色の種類 + 2つ以上ある色 の合計が6以上ならOK
実装
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_507/CubeStickers.cpp
- 他の人の実装を見たら、5色をチェックしていないものもあった。これは、ステッカーの枚数が6以上という前提条件を使っているっぽい。
Hard (1000) CubeRoll サイコロ転がし
問題
- n^2マス単位で動かすことができるすごろく
考察
- わからなかったので、小さい数のとき総当りするコードを書いたが、時間内には間に合わず
実装 ※終了後解き直した
解説 https://topcoder-g-hatena-ne-jp.jag-icpc.org/ir5/20110529 を読んだ。素晴らしい!
開始点startから終点endまでの距離をrとしたとき、
- 範囲が無限の場合
- (x+1)^2 - x^2 = 2x+1 つまりrが3以上の任意の奇数であれば2でいける
- (x+2)^2 - x^2 = 4x+4 つまりrが4の倍数であれば2でいける
- rが4の倍数でない偶数の場合、a^2+b^2の可能性があるので、rの範囲で全探索する
- ただし最大でも3
- 範囲が有限(つまり下限と上限の穴がある)の場合
- 全探索する
- 最大値は不明
結果
oo- 237.63+394.43
落ち着いて解けたので、EasyとMediumが通った。rating 964 → 1030 やや増
2011-05-22
SRM 504.5 Div2
Easy (250) TheJackpotDivTwo
問題
- 整数の配列と、jackpot jが与えられる
- 一番低い値のところにjを1ずつ分配する
考察
- どのindexまでに分配するかを求める
- 端数の処理
実装
- ソートする
- 最大のindexからはじめる
- index iまでの合計とjを合計する
- 合計の平均値averageと、[i]を比較して、averageが[i]以上なら分配対象
- 0からiまで配る
- 大きいindexから、端数を配りなおす
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/TheJackpotDivTwo.cpp
Medium (500) TheNumbersWithLuckyLastDigit
問題
- 下一桁が4か7ならアホになります
考察
- 規則性が見出せなかったので、手作業で表を作る
- 十分大きな数に対してはループしている
実装
- 手作業で99まで表を作っておいた
- アホの数に対してはmap<int,int>に突っ込んでおく
- 見つからなかったら-1を返す
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/TheJackpotDivTwo.cpp
Hard (1000) TheTicketsDivTwo
未着手 → 解き直し
問題
- n人を一列に並ばせて、その中から一人だけ選ぶ。
- 一人しかいなければ選んで終了。
- サイコロをふり、4が出たら先頭の一人を選んで終了。
- 奇数が出たら、先頭の一人を末尾に移動する。
- 偶数(2か6)が出たら、先頭の一人を取り除く。
- k回の試行で誰も選ばれなければ、先頭の一人を選んで終了。
- m番目の人が選ばれる確率を求める。
実装
感想
xo- 147.04*0+239.15 991 -> 964
番号は、504がノーコンだったため、やり直しという意味っぽい。
500しかsystem testが通らなかったためrateが964に落ちてしまった。
しかしまずはちゃんと解けるかどうかが重要。
2011-05-14
SRM 506 Div2
Easy (250) SlimeXSlimeRancher2 育てゲー
問題
- 最大のスライムの値に合わせるために、育てる総和を求める。
考察
- maxだけわかれば、ソートする必要なかった。
実装
Medium (500) SlimeXSlimesCity 合併
問題
- 任意の二つの町を合併させるとき、町の名前として残るのは何通りか答える。
考察
- 人口でソートしておく
- X+1番目の町の人口が、X番目の町までの全合計を上回る場合、X番目までの町は残らない。この条件で消していくだけ。
- 全合計を上回らない場合は、残る可能性がある。(判定条件としては上の条件のみでよい)
- 本番では解く早さ優先で個別に合計を求めたが、合計を求めながら判定するだけでいいので二重ループは不要。
実装
Hard (1000) SlimeXResidentSlime ゾンビスライム
問題
- 文字で表された2次元のフィールドがある
- フィールドに勇者(あなた)とゾンビスライムが何匹かいる
- ゾンビスライムは1～9の数字で表され、数字のターン後に復活する
- ゾンビスライムと交差すると倒せる
- 倒されたゾンビスライムに交差すると、復活してその場で倒したことになる
- 全てのゾンビスライムを倒す瞬間が生み出せればOK
- 最小のターン数を求める
考察
- スライムが10匹以上いたら不可能
- 全てのスライムに到達可能でなければ不可能
- 一番値の小さいスライムから、一番値の大きい(または遠い)スライムまでの距離が、一番値の大きいスライムの値を超えていたら不可能
- kusanoさんのを写経
- 初期位置を0番目、スライムの位置を1～9番目とする
- 任意の位置同士の距離を求めておく(不可能なら-1)
- 0番目から最後のスライムまで一筆書きした距離を求める
- 最後のスライムに到達した時点で復活しているスライムがいなければOK
- 復活判定のため、最後のスライムから距離を加算していくと簡単に判定できる
- スライムを一筆書きする順番は1～9でnext_permutationで列挙
実装
結果
oo- 240.35+358.19 864 -> 991
EasyとMediumのシステムテストが通って緑に戻った。
Hardは無理げーなので諦めた。もう少し慣れたら再挑戦するかも。
2011-05-12
Google Code Jam 2011 Qualification Round
準備
GCJ勉強会に参加したので、せっかくなので挑戦。
過去のQRのTheme ParkとClosing the Loopを解いて、入出力のひながたを用意しておいた。
A Bot Trust
問題
- ロボットBまたはOと、ボタン番号が指定される
- 指定されたロボットが、そのボタンへ移動してボタンを押す
- 最小の時間(クリティカルパス)を求める
ポイント
- 指定された方が行動している間、指定されていない方も、次に指定された場所へ移動できる
実装内容
- 指定されたロボットは、行動時間を累計しておく
- 累計ぶん、指定されなかった方も動ける
- ロボットが交代(色が変化)したとき、必要な行動時間から、他方の累計行動時間を引く
https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_A_BotTrust.cpp
B Magicka
問題
- エレメントが1つずつ与えられ、リストに加わる
- 末尾の2つがcombine条件に合致したら、1つの別のエレメントに変化する
- opposedペアが発見されたら、リストをクリアする
ポイント
- opposedよりcombineが優先
- 1個足し、combine判定ループ、opposed判定、の繰り返し
実装内容
- combineとopposedの両方については、逆のパターン(AB→TならBA→T)も保持しておく
- opposed判定のために、エレメント毎の個数をひけるようにしておく
- opposed判定は、最後のエレメントと、opposedペアになるものがどこかに1個以上あるかどうかで判定
- ただしopposedペアが同じエレメントの場合は、2個以上あるかどうかで判定
https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_B_Magicka.cpp
C Candy Splitting
問題
- Seanは加算ができる
- Patrickが加算だと思い込んでいるのはXORである
ポイント
- XORが一致するというのは、SeanとPatrick全体でのXORがゼロである
- 全体のXORがゼロでない場合、Patrickは泣く
- 全体のXORがゼロの場合、1つだけキャンディーを渡すと、XORが一致する
実装内容
https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_C_CandySplitting.cpp
D GoroSort
問題
- ソートされていない要素をランダムにシャッフルするとき、並ぶまでの期待値を求めよ
ポイント
- 2回で少なくとも要素ひとつは交換、すなわち揃えられるので、O(n)かなーと予想だけした。
- ふぞろいがn個のとき、1回シャッフルするとだいたい1個揃う(それぞれの1個が揃う確率が1/n、それのn倍)ので、直感的にはn回、つまり、ふぞろいの数=回答、ということらしい
結果
A、B、Cのlargeが通って70点。四時間くらいかかった。
largeが全部通ったのでとりあえずよしとしたい。Round 1は通過したいなあ。
2011-05-10
SRM 505 Div2
Easy (250) SentenceCapitalizerInator 先頭の大文字化
問題
- 小文字の英字で、スペースとピリオドで区切られているフレーズの、先頭だけ大文字にする。
実装した内容
https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/SentenceCapitalizerInator.cpp
Medium (500) PerfectSequences 完全な数列
問題
- 1つ変更することで和と積が一致するperfectな数列になるかどうかを答える
はまりポイント
- すでにperfectな場合に、Noとしてよいのか確信が持てない
- 積がゼロの場合に特別扱いするかどうか
実装した内容
- (product * x) == (sum + x) であるため、x = sum / (product - 1) として求める
https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/PerfectSequences.cpp
Hard (900) RectangleArea 格子の数を求める
わからんのでスキップ→解き直し
問題
- 大きさW×Hの四角形がある。
- 四角形はN個の水平位置X[n]と、M個の垂直位置Y[m]で区切られている。
- 位置X[i]Y[j]のサイズが既知であるかどうかが与えられる。
- 四角形全体のサイズを既知とするための最小の質問回数を求める。
方針
- 既知が全くなければ、縦幅+横幅-1が答え
- YYYNNとNNYYYのような行は既知と既知をつなげてYYYYYと見なせる
- YYYNNとNNNYYは、1回聞けば既知をつなげられる
- というのはunion find木でいける
- とりあえず水平方向についてそれで求める
- 縦方向については、一つでも既知の桁があれば既知となるので、未知の行だけカウントを加算する
実装した内容
https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/RectangleArea.cpp
感想
ox- 232.27+255.56*0 932 -> 864
EasyとMedium/Hardの難しさがアンバランスすぎる気が。
Easyのみ通過でratingが灰色になってしまった。
Mediumのシステムテストを通すのに、終わってから2時間くらいかかってしまった。