hotpepsiの練習帳

SRM 651

17:05

Div1 Easy (250) RobotOnMoon

問題

• 月にロボットがいる
• 有効な座標の範囲、および、ロボットと障害物の座標が与えられる
• 上下左右のいずれからなる一連のコマンドを送信する
• コマンドの任意の部分が欠損する可能性がある
• ロボットが地図からはみ出さないコマンドの最大長を求める
• 無限の長さでもはみ出さない場合は-1とする

方針

• 前後左右のどこかに#があれば、一方向へ無限のシーケンスを送ればいいので-1
• なのでどの方向にも壁がない場合だけを考える
• ある方向について、何もない部分の一歩手前までは必ず行ける
• 全方向について成り立つ
• つまり横の長さ-1 + 縦の長さ-1の合計が答え

結果

unrated

提出できなかったらメールしろ、という珍しい指示が出た回。

気づかないと間違えるSRMらしい問題だと思った。

http://togetter.com/li/789285

SRM 650

22:00

https://competitiveprogramming.info/topcoder/srm/round/16314/div/1

Div1 Easy (250)

問題

• 文字AかBだけからなる文字列がある
• 確定している文字の種類と場所が与えられる(与えられなかった場所の文字は未確定である)
• 隣り合う文字が同じである個数の総数を最小にするとき、可能な場合の数を求める

方針

• 確定している文字について、位置でソートする
• 端から確定した文字については、一意に定まる
• 確定した文字と確定した文字との間については、文字の違いと、距離d(隣なら1)で場合分け
• 同じ文字の間に、奇数個はさまっていたとき(dが偶数)は一意で、偶数個のときはd通りある
• 異なる文字の間に、偶数個はさまっていたとき(dが奇数)は一意で、奇数個のときはd通りある
• 一意でない場合、連続するところを一カ所だけ作るのが最小で、それがd通りになる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_650/TaroFillingAStringDiv1.cpp

結果

o-- 107.77pts 257th/357 rating 1443 -> 1410 (-33)

agwさんと同室。4回目?

何通りなのかよくわからず時間がかかった。

http://togetter.com/li/784723

SRM 649

15:02

Div1 Easy (250) Decipherability

問題

• 文字列sが与えられる
• K文字削除する
• 削除した場所が一意かどうかを判定する

方針

• 全ての文字がユニークな場合は常に一意
• 全て削除する場合は一意
• 一意でないのは、同じ文字が含まれていて、削除後に残った文字がどちらなのかわからない場合
• すなわちs[i]とs[i+j]が同じ文字のとき、jがK以下のとき(K-1文字以下がはさまっているとき)は一意でない
• 全てのiについて調べる
• Passed System Test

結果

o-- -1 204.60 -25 = 179.60pts 293rd/555 rating 1424 -> 1443 (+19)

写経が不十分で失敗した。

最長共通部分列を求めても解けるらしい。

http://togetter.com/li/781384

SRM 648

21:41

Div1 Easy (250) AB

問題

• 'A'か'B'だけからなる長さNの文字列Sについて考える
• i<jで位置iが'A'、位置jが'B'の個数がK個のものを求める</li>

方針

• Aより右にあるBの個数がスコア
• Aの個数をa個、Bの個数をb個として、a×bが最大値
• aとbを全て試す
• a×bがK以上になるとき、a-1個のAは全てのBの前で、残りひとつのAの位置でスコアが調整できる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_648/AB.cpp

結果

o-- 127.75pts 379th/528 rating 1460 -> 1424 (-36)

堅実にratingが削れた。

http://togetter.com/li/777753

Facebook Hacker Cup 2015 Round 1

00:59

A. Homework

問題

• 数AからBまでの間で、素因数の個数の最大値を求める

方針

• 素因数の個数を配列に持つ
• 全探索
• 配列p[n]の値が0だったら素数なので、p[n*2],p[n*3]...の素因数を+1
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_A.cpp

B. Autocomplete

問題

• 残りの文字列が一意なら文字を補完してくれるシステムがある
• 全ての単語を入力するのに必要な入力文字数を求める

方針

• 1文字ずつノードにする
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_B.cpp
• Trie木でやればよかったらしい

C. Winning at Sports

問題

• 1点ずつ取っていくスポーツがある
• 先に1点取り、常に相手より得点して勝つ(stress-free)
• 相手が最終得点になるまで相手の得点を上回らないで勝つ(stressful)
• のそれぞれの勝ち方の総数を求める

方針

• DPがんばる
• スコア20までを全探索して検算した
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_C.cpp

D. Corporate Gifting

問題

• 会社にN人の従業員がいる
• それぞれの直属の上司の番号が与えられる
• 直属の上司にある金額の贈り物をする
• 部下を持つ従業員は、部下からもらったのと同じ額の贈り物はできない
• CEOも贈り物をする
• 贈り物に使う全社の合計金額の最小値を求める

方針

• 彩色問題みたいなやつ?
• あるノードが色Cで塗られていたときのコストの合計をDFSで求める
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_D.cpp

結果

ooox 60pts

変な持ち方をしてしまいDを落とした。解きなおしたが、intオーバーフローしたりして、時間内には無理かもだった。

去年は1問だけ正解なのでだいぶ解けるようになった感はある。