hotpepsiの練習帳

TCO 2014 Round 1A

greedy | 00:42

Easy (250) EllysSortingTrimmer

問題

• 文字列を変更する装置がある
• 先頭のN文字をそのまま、途中のL文字をソートして、末尾を削除できる
• 何回でも適用できる
• 適用結果のうちの辞書順最小のものを求める

方針

• 末尾に若い文字が入っている場合、それを先頭にもっていきたい
• なのでまず末尾のL文字をソートする
• 次にひとつ前の位置をソートして末尾を削除
• あとは長さがLになるまで繰り返す
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysSortingTrimmer.cpp

Medium (500) EllysScrabble

問題

• 文字列と、移動可能な距離Dが与えられる
• 各文字は、左右どちらか距離Dまで移動可能
• 移動結果のうち辞書順最小を求める

方針

• 先頭から1文字ずつ確定させていく
• 置ける候補のうち辞書順最小のものを見つける
• ただし、D個前の位置にあるものを使っていない場合、それを置く
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysScrabble.cpp

Hard (1000) EllysLamps

問題

• N個のランプとボタンがある
• 各ボタンはトグル動作し、押すとランプがON/OFFする
• ただし、両隣の片方または両方のランプも同時にON/OFFするようなボタンが存在する可能性がある
• ボタンの挙動がワーストケースの場合に、OFFにできないランプの最小値を求める

方針

• YNまたはNYの数を数える
• とサンプル4が合わない
• スイッチがN個連動するという前提でDP書いてみたりとか
• (終了後)
• YYYと並んでいるとき、一つ目と二つ目が連動していて、二つ目と三つ目が連動しているとき、NNNにできないので、+1カウントする、ということらしい
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysLamps.cpp

結果

oo- 238.44 + 386.42 = 624.86pts 331st/2205 rating 1513 -> 1578 (+65)

毎年の祭りその2到来。

比較的早く解けた。highest更新。

http://togetter.com/li/651699

Google Code Jam 2014 Qualification Round

01:11

Problem A. Magic Trick (6pts)

問題

• 数当て
• 4x4個の数が2セット与えられる
• 観客が数を一つ選び、最初と次の並びの行の場所を答える
• 数が一意かどうか、または観客が嘘をついているかどうかを答える

方針

• 両方の行に含まれる数値を求める
• 0ならうそ、1なら一意、2以上なら失敗
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_A.py

Problem B. Cookie Clicker Alpha (8pts/11pts)

問題

• クッキークリッカー
• 毎秒2個クッキーが焼ける
• F個のクッキーで工場が建てられる
• 工場を建てると毎秒の生産能力がC個増える
• X個のクッキーを焼く最短秒数を求める

方針

• 漸化式かと思ったけど式が作れない
• Cは1以上なので収束するっぽい
• 次の工場を建てたほうが早ければ建てる
• 放置したほうが早いなら放置して終了
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_B.py

Problem C. Minesweeper Master (11pts/24pts)

問題

• マインスイーパー
• R行C列の盤面にM個の爆弾を置く
• 1clickで解けるなら盤面を出力する

方針

• smallは最大25マスなので、全列挙して可能かどうか探索する
• DFSで埋めて判定
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_C_s.cpp

Problem D. Deceitful War

問題

• 重さが全て異なる石を使うゲーム
• 先手が重さを言って石を出す
• 後手が石を出す
• 重いほうが1ポイント得る
• ここまでが普通のゲーム
• チートありのバージョンは、後手の重さが全て既知
• そのうえで、後手にばれない範囲でうそをつく
• 正しい重さを言わなくてもよいが、うそがばれてはいけない
• 普通のルールの最大ポイントと、チートありルールの最大ポイントを求める

方針

• ソートしておく
• チートなしの場合、最大から出しても最小から出しても結果が変わらない気がする
• とりあえず最小から出してシミュレーション
• チートありのとき
• 先手の最小値が後手の最小値より軽いとき、その石でポイントを得ることはないが、後手の最大値より少しだけ軽い値を言うことで、一番軽い石を使って一番重い石を浪費させることができる
• そうでないときは後手の最大値より大きな値を言うことで、後手に一番軽い石を出させて、先手の一番軽い石でポイントを得る
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_D.py

結果

毎年の楽しみの一つ目到来。

A small、B small+large、C small、D small+large=66pts 2059th/25462

クッキークリッカー、ナイスすぎる。

うっかり予選が終わる前にコードを公開してしまい、コピペされてた。そのぶんの点数が引かれるだけなら通過はできると思うが気をつけたい。

参加条件読んだら、予選だけは問題について話してもいいらしい。

SRM 616

シミュレーション | 23:09

Div1 Easy (250) WakingUp

問題

• Alexの眠さをSとする
• 毎分眠さはD増加する
• N個のアラームがあり、開始時刻、間隔、ボリュームが与えられる
• アラームが鳴ると眠さがボリュームのぶんだけ減る
• 眠さが0以下になると起きる
• 初期値Sのうち、起きることができる最大値を求める
• 任意のSで起きることができるなら-1

方針

• 変化には周期性がある。periodのLCMになるはず
• 増える一方の場合には最初から0でないと起きられない
• S=0からシミュレーションして、最小値を符号反転したものが答え
• Failed System Test
• 最初と次の2520(1..10のLCM)分でシミュレーションをしてみて、最小値が低くなっていれば、任意の数で起きられる
• そうでなければ、最小値を符号反転したものが答え
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_616/WakingUp.cpp

Div2 Hard (1000) TwoLLogo

問題

• LL株式会社は、ロゴをデザインしようとしている
• N×Mの升目の中に二つのLを含む必要がある
• それぞれの升目は白か黒に塗られている
• 白い部分にLを二つ配置する組み合わせの総数を求める

方針

• 各座標のLの縦棒(上方向)と横棒(右方向)の最大の長さを求めておく
• 最初に置くほうの座標、上の長さ、横の長さ、あとに置くほうの座標で全探索 O(N^6)
• 後置のL字の組み合わせ(縦棒×横棒＝組み合わせ数)を足していく
• ただし、自分より上か、同じ高さで自分より右にあるものにすることで、同じ組み合わせを一回だけ数えるようにする
• 前置の縦棒に後置の横棒がふれる可能性があるときは、前置より左に置くときに、横幅の組み合わせを制限する
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_616/TwoLLogo.cpp

結果

x-- +2 0+100pt = 100pt 348/816th rating 1477 -> 1513 (+36)

周期とシミュレーションという問題はあまりないパターン。

0点だが一生懸命写経したら2年ぶりに黄色になれた。

復習が追いついたらdiv1 mediumに挑戦していきたい。

http://togetter.com/li/653487

SRM 615

シミュレーション | 02:33

Div1 Easy (250) AmebaDiv1

問題

• アメーバのモンテカルロは、自分と全く同じ重さのゼリーだけを食べる
• ゼリーを食べると体重が2倍になる
• ゼリーの重さが出現順に与えられる
• モンテカルロが到達しない重さの組み合わせの総数を求める

方針

• ゼリーに含まれない大きさだったときは何も食べないので無関係
• ということはゼリーに含まれる大きさだけを考えればいい
• 元々の大きさがaだったとき、最終的にa*2^nになるので、aが到達しない候補となる
• a*1/2のゼリーが含まれているとaになることがあり、それを候補から除外する
• まずゼリーに含まれる大きさにそれぞれについてシミュレーションしておく
• ゼリーに含まれる大きさのうち、到達しないものを数える
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_615/AmebaDiv1.cpp

結果

o-- 211.75pt 323/727th rating 1439 -> 1477 (+38)

落ち着いて解けた。なかなか良い点数。

乱数は出てこなかった。

http://togetter.com/li/650989

SRM 614

全探索 | 22:11

Div1 Easy (250) MinimumSquare

問題

• N個の座標がある
• それらのうち、K個以上の座標を含むように正方形で囲む
• ただし辺の上にあるものは含めない
• 最小の面積を求める

方針

• 範囲を愚直に全て調べるのは無理なので、どこかを決めうちする
• どういう範囲であっても、左下は存在するはず
• 左下を決めて、その位置より右かつ上のものを覚えておく
• 条件を満たすものがK個以上になる場合、距離でソートして、K番目のものを使う
• 左の座標と下の座標は、それぞれ別の点の可能性がある
• XとYそれぞれのかけあわせで試せばいい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_614/MinimumSquare.cpp

結果

o-- 159.79pt 239th/748 rating 1354 -> 1439 (+85)

図に描いたら思いついた。

xとyを独立で試すの割とよくあるかも。

http://togetter.com/li/648607