hotpepsiの練習帳

SRM 619

着想 | 01:30

Div1 Easy (250) SplitStoneGame

問題

• 複数の山それぞれに何個かの石がある
• 二人で交互にプレイする
• 一つの山を選ぶ
• 残りの山から2つの山を選び、それぞれに1個以上の石を分配する
• この操作ができなくなったほうが負け
• 最適戦略下でどちらが勝つかを判定する

方針

• 残りの山の数が2以下なら負け
• 2つ以上の石がある山がなければ負け
• そうでないときは、ターン毎に山が一つずつ減っていく
• 残りの山が3つになるほうが勝つので、奇数なら勝ち、偶数なら負け
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_619/SplitStoneGame.cpp

結果

o-- 151.83pt 451st/681 rating 1528 -> 1504 (-24)

判定ゲー意外と時間かかった。

http://togetter.com/li/663337

Google Code Jam 2014 Round 1B

22:15

A. The Repeater

問題

• いくつかの文字列が与えられる
• 同じ文字を隣に追加するか、連続する文字のうち1文字削れる
• 全部同じ文字列にするのに必要な操作回数を求める

方針

• それぞれの文字列について、連続する文字は1文字にする
• 同じにならなければ不可能
• 各文字について、長さ1～100を全部試して最小操作回数を求める
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_A.cpp

B. New Lottery Game

問題

• くじ用の乱数生成器が二つある
• 二つの出力の論理積が当選番号になる
• K未満を出力するのは何通りか求める

方針

• smallのみ、全探索
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_B_s.cpp

C. The Bored Traveling Salesman

問題

• N個の都市を飛行機で最低1回訪問する
• フライトチケットは行きと帰りがあり、行きを使ってからでないと帰りが使えない
• 行きのチケットはN枚で、出発地は任意だが行き先は全て異なる
• 都市には郵便番号が設定されている
• 訪問順に郵便番号を結合していく
• 結合した数値の最小値を求める

方針

• next_permutationで訪問都市の順番を生成して全て試す
• 可能かどうかを探索
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_C_s.cpp

結果

ooo--- 31pts 1316th/7381

Bは桁DPらしい。要復習。

Google Code Jam 2014 Round1A

01:29

A. Charging Chaos (8pts/17pts)

問題

• 充電の特性が全て異なるN個のデバイスと、N個のコンセントがある
• それぞれの特性値が長さLの2進数で表される
• コンセントの特性値の任意のビットを反転できる
• 同じ特性値のデバイスだけが充電可能
• 全てのデバイスを充電できるようにするために反転させるビット数の最小値を求める

方針

• largeは最大40bitsなので全ての組み合わせは試せなさそう
• 半分の20bitsなら全部試せる
• 半分全列挙かな?
• がんばって書く
• Passed System Test
• (終了後)
• 任意のデバイスとコンセントを固定すれば、ビットパターンが決まり、あとは残りのコンセントに反転ビットを適用した値がデバイスに存在するか調べるだけ
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1A_A.cpp

B. Full Binary Tree (9pts/21pts)

問題

• グラフが与えられる
• どれかのノードを親として、いくつかのノードを削除して完全二分木にする
• 削除する最少数を求める

方針

• smallは残すかどうかをビットで全列挙してDFSでいける
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1A_B.cpp

結果

ooo--- 8 + 17 + 9 = 34pts 1601st/3621

毎年のことながら1000位のゲームバランス設定がすごい。

SRM 618

着想 | 01:56

Div1 Easy (250) Family

問題

• 簡易版の家系図がある
• 配列parent1とparent2があり、親のindexが入っている
• 親は片方が男で片方が女である
• 可能な組み合わせかどうかを求める

方針

• ひとつの組み合わせを決めたら、あとは再帰的に決めていって矛盾があるかどうかを見ればよさそう
• なんとか提出
• Passed System Test
• union findに突っ込んで矛盾があるかどうかを見ればよかった
• AとBがCの親で、AとDがEの親みたいなとき、BとDは同じ性別みたいにしてグルーピングして、矛盾があればNG
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_618/Family.cpp

結果

o-- +1 99.96 + 50 = 149.96pt 320th/532 rating 1544 -> 1528 (-16)

久々のunion find回。

http://togetter.com/li/659154

SRM 617

math | 02:15

Div1 Easy (250) MyLongCake

問題

• 長さNのケーキがある
• 何人かの友達が来るので、到着前にケーキを切っておく
• 友達の数はN未満かつNの約数であり、何人到着するかは不明である
• 友人の到着後、切っておいたケーキの連続するピースを渡す
• ただし各友人には同じ量だけ渡す
• 分割数の最小値を求める

方針

• 謎すぎる
• 適当にループで書いて提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_617/MyLongCake.cpp
• (終了後)
• X番目の数がNと素でないとき、その場所で分割する必要がある
• GCD(X,N)==1の場所を除外すればOK
• N-totient(N)らしい

結果

o-- 162.54pts 551st/842 rating 1578 -> 1544 (-34)

わからないのにプラス点で反省。

http://togetter.com/li/657938