Hatena::Grouptopcoder

hotpepsiの練習帳

2015-11-15

SRM 654

| 22:27

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

https://competitiveprogramming.info/topcoder/srm/round/16318/div/2

Div1 Easy (250) SquareScores

問題

  • アルファベットと?からなる文字列Sがある
  • ?がどの文字になるかの確率が与えられる
  • Sから連続した文字を取り出したものを部分文字列とする
  • 全て同じ文字からなる部分文字列の総数をスコアとする
  • スコアの期待値を求める

方針

結果

o-- 138.33pts 134th/350 rating 1454 -> 1504

今年初黄色。DP必要ないっぽい。


http://togetter.com/li/799762

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20151115

2014-06-30

SRM 626

| 01:29

Div1 Easy (250) FixedDiceGameDiv1

問題

  • Aliceはa個のb面ダイスを振る
  • Bobはc個のd面ダイスを振る
  • n面ダイスは1からnの値を持つ
  • 出目の合計の多いほうが勝ち
  • Aliceが勝つときの期待値を求める

方針

  • nCkでやるとたぶん死ぬ
  • dp[N回振った][合計値]で確率のテーブルは作れそう
  • AliceとBobのテーブルを作っておく
  • Aliceの合計値がN回のときの確率をPa、Bobの合計値が1からN-1までの確率をPbとする
  • 全事象に対する生起確率Pn=Pa×Pb
  • PnにNを重み付けして、Pnの和で割れば期待値になりそう
  • (N×Pnの和)÷(Pnの和)が答え
  • Passed System Test

https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_626/FixedDiceGameDiv1.cpp

結果

o-- 107.91pts 359th/739 rating 1522 -> 1539 (+17)

外は寒かった。家でやるべき。

http://togetter.com/li/686090

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140630

2014-05-04

SRM 612

| 17:36

Div1 Easy (250) EmoticonsDiv1

問題

  • 顔文字をsmiles個送り付けたい
  • 入力欄全体をクリップボードへコピー、クリップボードを入力欄へ貼り付け、入力欄から1つ削除の3つの操作が可能
  • 入力欄にsmiles個入力するための最小手数を求める

方針

結果

x-- 0pt 324/452nd rating 1247 -> 1209 (-38)

NまたはN+1を因数分解して作る感じっぽい。


http://togetter.com/li/641003

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140504

2014-04-21

SRM 610

| 00:32

Div2 Easy (250) DivideByZero

問題

  • 何枚かの紙に数字が書いてある
  • 任意の2枚を取り出して、大きいほうの数÷小さいほうの数を計算する
  • 商が紙にない数なら追加する
  • 最終的に紙が何枚か求める

方針

Div2 Medium (550) TheMatrix

問題

  • 0か1からなる升目がある
  • チェス盤状になっている長方形の面積の最大値を求める

方針

結果

oo- -1 227.78 + 338.56 -25 = 541.34pt 30th/766 rating 1170 -> 1257 (+87)

典型的なDPが普通に解けた。


http://togetter.com/li/634761

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140421

2014-04-14

SRM 607

| 01:32

Div1 Easy (250) PalindromicSubstringsDiv1

問題

  • a-zと?からなる文字列が与えられる
  • ?はa-zのどれかに置換される
  • 左右対称な部分文字列の個数の期待値を求める

方針

結果

x-- -1 -25pt 700th/719 rating 1405 -> 1242 (-163)

単純だけど思いつかなかった。


http://togetter.com/li/624676

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140414