2016-03-31
SRM 663
https://competitiveprogramming.info/topcoder/srm/round/16512/div/1
Div1 Easy (300) ABBADiv1
問題
- 文字列initialが与えられる
- 文字Aを末尾に加えるか、文字Bを末尾に加えて全体を反転する
- 文字列targetにできるかどうかを求める
方針
- targetから、遷移可能なものをDFSで見つける
- 末尾がAか、先頭がBなら遷移可能
- 判定関数に向きをつければ、文字列を反転しなくてもいい
- Passed System Test
結果
o-- +1 191.52pt 205th/468 rating 1292 -> 1362 (+70)
遷移可能なパターンは実はあまり多くないというのに気づけばいいっぽい。
入院してて病室から解いた。
2016-03-21
TCO15 Algorithm Round 2C
https://competitiveprogramming.info/topcoder/srm/round/16520/div/1
Easy (250) YetAnotherCardGame
問題
- 1以上の整数が書かれたカードが何枚かある
- PetrとSnukeにN枚ずつ配り、交互に1枚ずつ出す
- 場にカードがないか、場のカードより大きな数のときだけ積むことができる
- 積めないときはカードを捨てる
- 場に積める枚数の最大値を求める
方針
- (終了後)
- dp[ターン数][場のカード]=枚数 でDP
- https://github.com/firewood/topcoder/blob/master/tco_2015/YetAnotherCardGame.cpp
結果
--- 0pt 188th/538 rating 1283 -> 1292 (+9)
オンサイトイベント。iwiさんとりんごさんが解説してくれるという素敵な回だった。
hardにはフラクタルが出てきた。フラクタルで何か問題作って、と言われて作ったらしい。すごい。
ハッカソンでは、Sails.jsでwebを巡回するというtravelling-sailsmanというサイトを作って発表した。楽天さんから特別賞を頂き、topcoderの賞金獲得額が$600になった。
ほんとはゲームにしたかったけど間に合わず。competitiveprogramming.infoにゲームを追加したほうが良かったかも。
色んな人と会えて良いお祭りだった。願わくばたまに開催して欲しい。
2016-03-20
SRM 662
https://competitiveprogramming.info/topcoder/srm/round/16511/div/1
Div1 Easy (250) FoxesOfTheRoundTable
問題
- N匹の狐がいて、それぞれの高さが与えられる
- 狐を円卓に並べたとき、隣り合う狐の高さの差の最大値をDとする
- Dが最小となるときの並べ方を求める
方針
- (終了後)
- ソートして、[1,1000]の各Dについて、1つずつ左右のどちらかにつないでいき、D以下ならOK
- (kmjpさんの解説読んで解きなおし)
- ソートしてA,B,C,D,E,...となっているとき、E-C-A-B-Dのように交互につないでいけばよい
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_662/FoxesOfTheRoundTable.cpp
結果
--- 0pt 175th/243 rating 1325 -> 1283 (-42)
これ以上ないくらいシンプルだった...
2016-03-06
TCO15 Algorithm Round 2B
https://competitiveprogramming.info/topcoder/srm/round/16500/div/1
Easy (250) Bitwisdom
問題
- Nビットの文字列が与えられる
- 1回の操作で、先頭または末尾から連続するビットを反転できる
- 各ビットの生起確率が与えられる
- 全ビットを0にするための操作回数の期待値を求める
方針
- 適当にメモ化する
- 死
- (終了後)
- ビットが異なっている部分を反転する必要があるので、それを数える
- ただし全ビットが1のときは反転部分がないので、その確率も期待値に追加する
- https://github.com/firewood/topcoder/blob/master/tco_2015/Bitwisdom.cpp
結果
--- 0pt 323rd/554 rating 1379 -> 1325 (-54)
翌日すごく面倒なDPを書いたが、正解は出力するものの意味不明なので書き直した。
2016-02-27
SRM 661
https://competitiveprogramming.info/topcoder/srm/round/16464/div/1
Div1 Easy (250) MissingLCM
問題
- N+1からMまでの数の最小公倍数をAとする
- 1からMまでの数の最小公倍数をBとする
- Nが与えられたとき、A=Bとなる最小のMを求める
方針
- 1からNまでに含まれる素因数(とその累乗)が、N+1以降で必ず出現する必要がある
- その出現位置の最大値がM
- Passed System Test
- LCMに影響するのは素数とその累乗p^nで、それが次に出現するのはその数の2倍なので、2*p^nの最大値を求めればいい
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_661/MissingLCM.cpp
結果
o-- -1 +1 106.14 + 25 = 131.14pt 181st/318 rating 1351 -> 1379 (+28)
一応解けた。
2倍を求めればいい理由に納得するのに時間がかかった。