SRM Div2 Hard 455～554までの100問が終わった。6月の頭から初めて12月の終わりまでかかったためほぼ7ヶ月でやり通したことになる。平均して2日に1問以下で明らかに遅いペースだと思う。やはりDiv2 Hard級は一問一問に時間がかかる。Div2 Medium / Div1 Easy…

問題 C種類の色のブロック（1x1x1のサイズ）が各色無尽蔵にあり、これらのブロックを積み上げていき、2x2xHのタワーを作りたい。隣接するブロックが同色であるというのををK個以下に抑えるようにタワーを作る方法は何通りあるか。1234567891で割った余りを返…

問題 数列が与えられる。この数列から１つずつ数字を取り除きたい。数字を取り除くとき、残りの数列の和が４の倍数にならないように取り除く。このようにしてK個の数字を取り除くとき、残った数列の和が最大になるようにしたい。最大値を求めよ。 やりかた E…

やりかた DP。 dp[i][j] :=（i番目までで、レートjの時のレート色の変化した回数の最大値）（０）次のコンテストが最終コンテストでそれに勝てばbrown coderになれるとき次コンテストが最終コンテストではないとき （１）現状がciel coderで次のコンテストで…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=12138&rd=15173 複数のカップケーキがあり、'A', 'B', 'C'のいずれかの色がついている。これらのカップケーキを円形に並べたい。隣合うカップケーキが同じ色にならないように並べるとき、何通り…

問題 グリッド上にタイルが敷かれており、タイルの色は数字かアルファベットで表される。タイルは必ずXY軸に平行な矩形の形で敷き詰められる。タイルは別のタイルの上に積み重ねていくことができ、各色のタイルは一度しか敷かれることがない。タイルを鳥瞰し…

問題 http://apps.topcoder.com/wiki/display/tc/SRM+549あるグラフの隣接行列が与えられる。このグラフに辺を加えるか、すでにある辺を取り除くかしてacyclicにしたい。必要な手順の最小回数を求めよ。 やりかた Editorialを参考にしました。bitDP。 acycli…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=12030&rd=14737 xy座標のX軸上を原点から座標(L,0)までの整数座標上において、ロケット任意の方向に１つだけ発射される。放たれたロケットはその方向に直線で進行し、0 やりかた XY座標における…

問題 正数が書かれたカードのデッキが2つあり、2つのデッキの上からカードを任意の枚数ずつ取り出して場に積み上げていき、これを2つのデッキからカードが無くなるまで繰り返す。続いて場に積み上がったカードの上から任意枚数ずつ2つのデッキに積み戻してい…

問題 http://apps.topcoder.com/wiki/display/tc/SRM+542 長さが等しい文字列が複数与えられる。文字列中のランダムな2箇所を置換するのをランダムな回数行う処理をすべての文字列について行う。処理後の文字列をソートした時に当初の文字列が何番目に置かれ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11135&rd=14732 P / Q（既約とは限らない）をX進数で表現した時に割り切れないとする。AからBの間にこのようなXはいくつ存在するか。 やりかた Editorialを参考にしました。まずP、Qをこれらの最…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11890&rd=14733 'o'か'.'かで埋められたグリッドが与えられる。'o'のマスは毎ターンごとに隣接する上下左右のマスを'o'に塗り替えていく。Kターン後の'o'のマス数を求めよ。 K やりかた 単純な幅…

問題

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11784&rd=14726 ある魔法少女は最初に非負整数Mのライフを持っている。毎日1ずつライフが減り、ライフ0で戦闘継続できなくなる。day[i]にモンスターに出会い、win[i]%の確率で勝利し、勝つことで…

問題 正六角形を組み合わせたボードがある（問題文図参照）。 このボードのタテヨコのサイズに対応したvector string boardが与えられる。board[i][j]が'X'の時、対応する正六角形に色を塗るとする。'-'の時は塗らないものとする。隣接する正六角形は異なる…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11654&rd=14553 蚊が数直線上でxInit[i]の初期位置におり、毎秒v[i]の速度で移動する。あなたは前後R以下にいる蚊を殺傷できる爆弾を持っており、任意の時刻に任意の位置で爆発させることができ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11674&rd=14762 文字列がn個存在し、これらを辞書式最小になるように結合したものがSとなる。このnを最大化せよ。 やりかた DP。 dp[j][i] := （文字列Sのj文字目まででS[i...j]を1つの文字列と…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11222&rd=14552 のコインを枚使ってcoins_sumにしたい。かつそのとき使用するコインの枚数の合計としたい。このような辞書式最小のを返せ。 やりかた coins_sumを2進数で表現したとき、これは2^i…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11609&rd=14547 a * b = cという等式が与えられる。しかしこの等式は成り立っていないのでa,b,cをA,B,Cに書き換えてA * B = Cが成り立つようにしたい。の最小値はいくつか。1 やりかた Aを1から1…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11552&rd=14544 カードが複数枚あり、2^0, 2^1, 2^3, ...というように各々に２のべき乗のいずれかが書かれている。このカードを表にすることでそのカードを使用するということをあらわす。自然数…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=11473&rd=14543 表向きに置かれたN枚のコインと要素数Kの配列a[]が与えられる。ターンi（0-indexed）ではコインをa[i]枚ランダムに選んで裏表をひっくり返す、という動作をKターンまで行っ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11536&rd=14542 複数の木があり、それらの高さはinit[i]である。毎ターンそれぞれの木はgrow[i]だけ成長する。そしてあなたは毎ターンどれかの木を切る。切るとその木は高さが0になる。 木の高さ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11239&rd=14541 文字列message[i]を部分列として持つような最短の文字列を返せ。複数ある場合は辞書式最小のものを返せ。なお各message[i]の文字はすべて異なる。 やりかた Editorialを参考にし…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11501&rd=14538 N*Mの盤面に0~9の数字が書かれている。この盤面を垂直方向か、水平方向の断片に分ける（問題文中の図参照）。この断片一つ一つを、垂直な断片なら上から、水平な断片なら左から10…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11289&rd=14537 AとBが両手でじゃんけんをする。1.Aの右手がBの左手に勝ち、Aの右手もBの右手に勝つときAに2点入る 2.Aの右手がBの左手に勝ち、Aの右手がBの右手と引き分けるときAに1点入る 3.そ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11466&rd=14439 自然数nが与えられる。これをb進数で表した時に各桁に4か7しか現れないようなb進数（ただしb >= 2）はいくつか（つまりbはいくつの値を取りうるか）。 やりかた 全探索ではもちろ…

問題 R*Cのグリッドで区切られたボードを(c1, r1)の座標から(c2, r2)まで移動することを考える。各セルは0~9までの数字が書いてあるかもしくはemptyを示す'.'が書いてある。数字dが書いてあるセル(x, y)からは(x - d, y)、(x + d, y)、(x, y - d)、(x, y + d…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437 N、Rが与えられる。 かつとなる数列の個数を求めよ。 やりかた N個の項のある桁のビットを取り出した時に、それらのビットが1であるのが高々1以下であり、これがすべての桁につい…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11322&rd=14436 数直線上に落とし穴があり、落とし穴の位置はholePos[i]で与えられる。最初initPosにある石をgoalPosに動かすことを考える。一回の移動で数直線上で平方数移動することができる。…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11433&rd=14514n人の人間が一列に並んでいる。サイコロをふり、4が出たら列の先頭に並んでいる人を選んでおしまい。それ以外の偶数が出たら先頭の人を列から外して、もう一回サイコロを振る。奇…