hotpepsiの練習帳

SRM 593

21:42

Div2 Easy (250) RaiseThisBarn

問題

• 牛舎に何頭かの牛がいる
• 壁をつくって二つの部分にわけたい
• 同じ数だけ牛がいるようにしたい

方針

• (長さ-1)通りのわけかたがある
• 分割してから牛を数える
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/RaiseThisBarn.cpp

Div2 Medium (500) WolfDelaymaster

問題

• 数nを選び、n個のwとn個のoとn個のlとn個のfを連結する
• そのような文字列を1回以上連結する
• 上記の操作でできる文字列かどうかを判定する

方針

• がんばって4つの状態ごとに数える
• Passed System Test
• (書き直し)
• 4つの文字が連続していると仮定して数える
• 全てが同じ個数ならOK
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/WolfDelaymaster.cpp

Div1 Easy (250) HexagonalBoard

問題

• ヘックスの升目のボードがある
• Xの印がついているところに色を塗る
• 隣接していれば違う色を塗る
• 最低何色必要か求める

方針

• DFS
• 最大3色っぽい
• 周りが塗られていなければ色1で塗る
• 周りが色1のみで塗られていれば色2で塗る
• 周りが色2のみで塗られていれば色1で塗る
• 周りが色1と色2で塗られていれば色3で塗る
• 最大の色番号が必要な色数
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/HexagonalBoard.cpp

結果

oo- 228.43 + 274.65 = 503.08pt 406th/1314 rating 1161 -> 1141 (-20)

mediumは最初がwでないときみたいに場合わけになってしまい、いまいちな書き方だった。

数えるのと判定するのを分離すべき。

SRM 592

20:59

Div1 Easy (300) LittleElephantAndBalls

問題

• RGB三種類のボールがある
• テーブルに1つずつ置いていく
• ボールを置いたとき、置いたボールの左側の色の数と、右側の色の数が得点になる
• 得点の最大値を求める

方針

• 手が出ず
• (終了後)
• 左右それぞれにできるだけ異なる色を置いていくと、結局左右それぞれに置いたかどうかになる
• 色毎に最大2個まで覚えておけばよい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_592/LittleElephantAndBalls.cpp

Div2 Easy (250) LittleElephantAndBooks

問題

• 何冊かの本があり、ページ数が配列で与えられる
• N冊選んで読む
• 読んだページ数の合計が2番目に少ないようにしたい
• 何ページ読むことになるか求める

方針

• 最初または末尾より一つ前、どちらかの本を読まないのが2番目
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_592/LittleElephantAndBooks.cpp

Div2 Medium (500) LittleElephantAndPermutationDiv2

問題

• 1からNまでのN個の数列AとBがある
• それぞれの要素を並べ替えて、max(Ai,Bi)の和を求める
• 和がK以上になるのは何通りか求める

方針

• next_permutationで全列挙
• 並べ方はN!通りあるので、K以上ならN!を加える
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_592/LittleElephantAndPermutationDiv2.cpp

結果

--- 0pt rating 1217 -> 1161

並べ方を考えてしまい失敗。

SRM 591

01:14

Div2 Easy (250) TheArithmeticProgression

問題

• y-x=z-yが成り立つタプル(x,y,z)を等差数列と呼ぶ
• タプルが与えられたとき、等差数列にするために加減算する最小値を求める

方針

• aについて考えると2b-c-a=xとして等差数列ならx=0なのでxが変更しなければならない数
• a,b,cのそれぞれの式の最小値が答え
• Passed System Test
• なのだが、bが2倍できいてくるので結局bを変更すればよい
• (a+c)*0.5-bが答え
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_591/TheArithmeticProgression.cpp

Div2 Medium (500) ConvertibleStrings

問題

• 2つの文字列が与えられる
• Aの文字セットを置換することでBにする
• 成立させるために削除する必要がある文字数を求める

方針

• 先頭の文字A[0]を削除する・しないの両方試して、DFSして全ての長さで求める
• 削除しないときは、A[0]とA[i]、またはB[0]とB[i]が一致したら、両方一致するときはそのまま、そうでなければ削除する
• Failed System Test
• 文字が9種しかないので、next_permutationで置換パターンを全列挙して、置換パターンに合わない文字を削除する
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_591/ConvertibleStrings.cpp

Div1 Easy (275) TheTree

問題

• ある頂点Xを始点とする木がある
• Xからの距離Dごとの頂点の数が与えられる
• 制約条件を満たす木のうち、任意の頂点の距離の最大値を求める

方針

• 始点から上に辿っていき、折り返して別の頂点を通って一番下まで行く
• 始点は一番下の頂点でよさそう
• どこまで辿るかを全て試す
• 頂点数が2以上である限り、別のルートで分岐しているので下までいける
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_591/TheTree.cpp

結果

ox- +3 237.55+150=387.55pt 104th/717th rating 1199 -> 1217 (+18)

easyはa,b,cを0-10全て試すひながたを作っておいて写経したら3撃墜できた。

mediumは謎の前処理を入れたことで落ちていたようだ。再帰処理自体は合ってた。

SRM 590

01:48

Div2 Easy (250) FoxAndGomoku

問題

• 5目並べの盤面が与えられる
• すでに勝負がついているかどうかを答える

方針

• 全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_590/FoxAndGomoku.cpp

Div2 Medium (500) FoxAndGo

問題

• 碁盤がある
• 黒を1手打ったとき、白が取れる最大の個数を求める

方針

• 普通にDFS
• Failed System Test
• 書き直し
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_590/FoxAndGo.cpp

Div1 Easy (250) FoxAndChess

問題

• 横一列に右向きまたは左向きのポーンが配置されている
• beginからtargetの状態に遷移可能かどうかを求める

方針

• 移動しても順序は変わらない
• 移動可能な場所を全て列挙しておく
• targetを左から一つずつ見ていき、移動可能な場所かどうかを判定
• という面倒なことをしなくても、元々の位置から移動先の方向かどうかを判定するだけでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_590/FoxAndChess.cpp

結果

ox- 224.86pt 218th/1301 rating 1186 -> 1199 (+13)

mediumは実に普通なDFSだったのだが変なメモをしてしまい失敗。

SRM 589

01:12

Div2 Easy (250) GooseTattarrattatDiv2

問題

• 文字列が与えられる
• 1文字変更するのに1秒かかる
• 全ての文字を同じにするのにかかる時間を求める

方針

• 全カウント - 最大の文字のカウント
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GooseTattarrattatDiv2.cpp

Div2 Medium (500) GearsDiv2

問題

• N個のギアがある
• 最後のギアと最初のギアはつながっている
• ギアの向きが与えられる
• 全てのギアがまわるようにするために取り除かなければならない個数を求める

方針

• 同じ文字が連続している部分をつぶす
• 先頭の文字を末尾にもコピーして、前の文字と同じなら取り除いていく
• 提出
• Challenge Succeeded
• 先頭を取り除くケースに対応できてなかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GearsDiv2.cpp

Div1 Easy (250) GooseTattarrattatDiv1

問題

• 文字列Sが与えられる
• 全ての文字Xを文字Yに1文字ずつ変換する操作ができる
• 左右対称の文字列にするための最小の変更文字数を求める

方針

• わからん
• 変更してみて、一致数-変更数が一番良いものを選んでいく
• 失敗
• 他の人たちの解法を読む
• いったん同じ文字にしたらずっと同じ文字になる
• 対になる場所は同じ文字にしなければならない
• 元々同じ文字の場所もずっと同じ文字
• union findで同じ文字にしなければならない場所をまとめる
• まとめたグループを、同じ文字に変更する
• 変更する手順はdiv2の問題と同じ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GooseTattarrattatDiv1.cpp

結果

ox- +1 -1 246.03 + 50 - 25 = 271.03pt 255th/1095 rating 1183 -> 1186

例を作るのが下手すぎ。