hotpepsiの練習帳

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は謎の前処理を入れたことで落ちていたようだ。再帰処理自体は合ってた。