hotpepsiの練習帳

Google Code Jam 2011 Round 1C

23:12

A. Square Tiles (10pt + 10pt)

問題

• グリッドに1x1の正方形のタイルが敷いてある。
• 全てのタイルが敷いてある場所を2x2のタイルで置き換えたい。
• 可能かどうか、可能な場合は敷き方を求める。

方針

• 左上から貪欲に置いていくだけ
• 1マスでも置いてあれば、残りのマスに置けないとだめ
• 右端や下端に1マスだけ置いてある場合を考慮する
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_A.cpp

B. Space Emergency (12pt + 25pt)

問題

• 星0から星Nまで、速度0.5の宇宙船で移動する。
• 利用準備に時間tがかかるブースターがL個ある。
• ブースターを使うと、使用してから次の星までの速度が1.0になる。
• 星と星との距離を示すのに、C個の配列が与えられる。
• それぞれの星の距離はC個の配列の繰り返しである。
• 星Nへの最短到達時間を求める。

方針

• 距離を2倍しておいて、ブースターを使った場合に1/2にするのが楽
• ブースターの準備時間より前はひたすら足すだけ
• ブースターが使える区間をリストで持っておく
• 星と星の間にブースターが使えるようになる場合は、準備完了後から次の星までの残りの区間をブースターが使える区間として扱う
• 長い期間から貪欲に使う
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_B.cpp

C. Perfect Harmony (8pt + 35pt)

問題

• ある二つの数があり、片方がもう片方で割り切れるとき、ハーモニーと呼ぶことにする。
• 数値の配列Aが与えられる。
• L以上H以下でAの全てとハーモニーが成り立つ数を求める。

方針

• 全探索でsmallのみ通す
• largeは、素因数分解+大きさで場合分けだろうか...
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_C.cpp

結果

本番ではA(small+large)+C(small)で28ptだった。

今年はBみたいなのが何とか解けるかも。

TCO12 Round 2B

22:00

Easy (300) BlurredDartboard

問題

• N分割されていて、それぞれ1～N点のダーツ盤がある。
• 一部の文字盤は汚れていて数値が読めない。
• 正確にどれでも当てられるとして、最低P点以上にできる回数を求める。

方針

• 読める部分の最大値と、読めない部分(Z個)の期待値を求めて、どちらかを使う二択
• 読める部分の最大値が期待値以上であれば、最大値だけで試行すればよい
• 期待値を使う場合は、Z個単位で試行するとZ×期待値のポイントが得られる
• Z×期待値未満のポイントについては場合わけが必要
• 読めない部分の小さい値から順番に取得すると考える
• それらの総和が残りのポイント以上ならOK
• ただし、最大値だけで試行したほうがよい場合がある
• https://github.com/firewood/topcoder/blob/master/tco_2012/BlurredDartboard.cpp

結果

o-- 150.03pt 616th rating 1368 -> 1414

300点ということで慎重に解いたら遅すぎた。でも正解なのはとても良い。

SRM 542

00:26

Div1 Easy (250) PatrolRoute

問題

• X×Yの大きさの空間がある。
• x座標とy座標がそれぞれ異なる任意の3点を選ぶ。
• それらをユークリッド距離が最短かつループするように結ぶ。
• 最短距離minTと最大距離maxTが与えられるとき、3点の選び方が何通りあるか求める。

方針

• 隅を決めてDPみたいなの書いてみるがうまくいかない
• submitできずに終了
• 解きなおし
• いろいろ解き方がある
• 3点の座標の上端、下端、左端、右端で四角形を形成すると考える
• パトロールする距離は、この四角形の横と縦のサイズの2倍になる
• 3点をA,B,Cとして、左上をA、右下をBとして固定してみる
• もう一つの点Cは中央の(横サイズ-1)×(縦サイズ-1)のどこに置いてもいい
• 上端、下端、左端、右端の座標をAx,Ay,Bx,Byとしたとき、Cの座標をAx,Ay,Bx,Byのどれかと交換しても四角形のサイズが同じになり、これが6通りある
• x座標Ax,Bx,Cxの置き方が3!通り、y座標Ay,By,Cyの置き方が3!通りで、点A,B,Cは順不同なので並べ方3!通りは重複分だから(3!×3!)÷3!＝6通り、な気がする
• 四角形全体の移動(X-横サイズ)×(Y-縦サイズ)を考慮
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_542/PatrolRoute.cpp

Div2 Easy (250) WorkingRabbits

問題

• N匹のうさぎがいる。
• うさぎの生産性は、別のうさぎとの仕事の総和の平均である。
• 全うさぎの個々の仕事量が与えられる。
• うさぎの生産性を求める。

方針

• 半分は同じもの
• 半分だけ合計して(N×(N-1))÷2で割る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_542/WorkingRabbits.cpp

結果

--- 0pt 286th rating 1420 -> 1368 (-52)

メモ用紙に何通りか列挙してようやくわかった。

ちなみに1000000007はエマープ(emirp)とのこと。

Google Code Jam 2011 Round 1B

23:20

A. RPI (8pt + 12pt)

問題

• NCAA男子バスケットボールトーナメントが毎年開かれている。
• 350の学校のうちRPIが高い学校が推薦される。
• RPIは0.25 * WP + 0.50 * OWP + 0.25 * OOWPで計算される。
• WPは勝率である。
• OWPは全対戦チームの、自チームとの勝負を除いた勝率の平均である。
• OOWPは全対戦チームのOWPの平均である。
• 全チームの対戦成績から、各チームのRPIを求める。

方針

• 読解できれば書くだけ
• 去年は一時間くらいかかって提出
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_A.cpp

B. Revenge of the Hot Dogs (15pt + 20pt)

問題

• ホットドッグ屋が水平方向のみに伸びる道路上にいる。
• それぞれのホットドッグ屋は、少なくとも距離Dだけ離れる必要がある。
• ホットドッグ屋の移動速度は毎時1である。
• 地点の水平座標と、その地点のホットドッグ屋の個数が与えられる。
• 全てのホットドッグ屋の移動が完了する時間を求める。

方針

• 去年は解けなかった
• 今年も解けない
• ぐぐる
• にぶんたんさく
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_B.cpp

C. House of Kittens (20pt + 25pt)

問題

• 柱がN本ある猫屋敷がある。
• 柱と柱の間にM個の間仕切りを設置して部屋を作った。
• それぞれの柱は異なる種類のマタタビが使ってある。
• ある部屋にあるマタタビの種類が別の部屋にないと猫は機嫌を損ねる。
• マタタビの種類を最大化した上で、それぞれの柱に使用する種類を求める。

方針

• さっぱりわからない
• 彩色問題?
• 色数=最小の頂点数
• 壁から部屋を生成する
• 最初の部屋を塗る
• 2頂点以上塗られている部屋を次々塗る
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_C.cpp

感想

一年かかって1Bまで復習。本番はAのみで20pt、2589位。

Aはこの評価式微妙だよねみたいな説明が面白い。

Bは冗長に書いたら納得できた。

Cはだいぶ無駄があるけどlargeまで通った。ちょっと嬉しい。

Google Code Jam 2012 Round 1A

23:39

A. Password Problem (10pt + 10pt)

問題

• めっちゃ長いパスワードを使っている。長さはBである。
• そのうち、すでにA文字入力済である。
• 入力済の文字が合っている確率が文字数ぶん与えられる。
• その状態から、パスワードを正しく入力するまでのストローク数の最小の期待値を求める。

方針

• 入力した長さが間違っているというのは考慮しなくてよい
• 新たに入力するぶんは完全一致するとみなしてよい
• 最終的に、入力した文字は完全一致する必要がある
• つまり入力した文字が使える確率は、それまでに入力した文字が全て一致する確率 p0*p1*p2... である
• BSキーで削除すると、削除した部分は全て一致するとみなしてよい
• ということで、全て一致する確率のテーブルだけあれば計算できる
• 全部打ち直した場合を考慮しておく
• https://github.com/firewood/topcoder/blob/master/gcj_2012/1A_A.cpp

B. Kingdom Rush (15pt + 18pt)

問題

• Kingdom Rushというゲームをクリアしたい。
• ゲームはN面からなる。各面はレベル1とレベル2からなる。
• 全ての面のレベル2をクリアすればゲームクリアである。
• レベル1をクリアすると星がひとつ、レベル2をクリアすると星がふたつもらえる。
• ただしレベル1をクリア済でレベル2をクリアしたときは星がひとつだけもらえる。
• 各面のそれぞれのレベルをクリアするのに必要な星の数が与えられる。
• 星の条件を満たしている場合、1プレイでそのレベルをクリアである。
• 星の条件を満たしていない場合、そのレベルはクリアできない。
• ゲームをクリアするのに必要な最小のゲームのプレイ数を求める。

方針

• 貪欲でやってみる
• レベル2がクリアできるものを全て処理する
• クリアしていないレベル2のうち最も星が少ないやつがクリアできるようになるまでレベル1をこなして星を稼ぐ
• そこで無理なら失敗
• 書いたがIncorrect...最適解じゃないのかな
• 簡単なやつから取ると無駄があるっぽい
• クリアできるレベル1のうち、レベル2の星が最も大きいやつから取ればよさそう
• いけた
• https://github.com/firewood/topcoder/blob/master/gcj_2012/1A_B.cpp

結果

oooo-- 2WA 53pt 989th

超ぎりぎりだけど通過!!

今年の目標はGCJ R1突破とTopCoderで一瞬黄色になる、だったのだけど両方達成できて嬉しい。