MemberSRM505

TopCoder

社会人としてのSRM初陣。

  • -

300. RectangleArea

問題：n×mに分割された長方形の各部分の面積をなるべく少ない回数聞いて、全体の面積を当てるクイズ。

  • 300か。これ無理じゃね…。
  • しかし、思考停止したら終了なので何か考えてみる
  • i番目の縦幅をR(i), j番目の横幅をC(j)とする
  • 求めるのは、(R(0)+R(1)+…+R(n-1))*(C(0)+C(1)+…+C(m-1))
  • サンプル見た感じ，R(0)以外をR(0)の式で表せればよさそう
  • 面積Aij (= R(i)*C(j))が分かればR(i)とC(j)間の変換はできる
  • R(i)，C(j)それぞれをノードだと思えば、変換可能な関係はグラフになる
  • 面積Axyを聞く操作は，R(x)とC(y)間に枝を張る操作になる
  • すべてのノードが連結されていれば計算可能
  • つまり、(連結成分の数-1)が答え。こ れ だ！
  • ここまで約30分。もう無理かと思った。

500. SetMultiples

問題：A以上B以下またはC以上D以下の整数からなる集合Sが与えられる。Sに対しmultipleである、要素数最小のSの部分集合の要素数を求める。

  • こういうときは問題を簡単にして考えると良いと、昔えらい人に聞いた。
  • Sの要素が1以上B以下の整数のとき
    • B/2以下の数iは、2*iがSに属するので、[B/2+1,B]が最小の部分集合
  • Sの要素がA以上B以下の整数のとき
    • 同じような理屈で、[max(A, B/2+1), B]が最小の部分集合
  • Sの要素がA以上B以下またはC以上D以下の整数のとき
    • [max(A, B/2+1), B]または[max(C, D/2+1), D]までは簡単に削れる
    • C〜D側はこれ以上削れないので、A〜B側で削れる要素があるかが問題
    • [(C+i-1)/i, D/i]内の整数kは，i*kが集合に属するので削れる
    • 1〜Cについて区間[A,B]から共通部分を削れば良いと思ったけど、これだとO(C)
    • O(sqrt(C))くらいなら良いんじゃねという気がしたので、
      • 1〜sqrt(C)について区間の共通部分を削っていく
      • A〜(C+sqrt(C)-1)/sqrt(C) までは1つずつ[C,D]内に倍数があるか調べる
    • という感じでやった。
  • これでどうだ！と思ったら一箇所long longにすべきところをintにしててTLE。
  • 社会人になってもこの辺は平常営業。

Challenge Phase

  • 300に嘘っぽい解法がいっぱい見えた
  • 反例を考えてる先から落とされていって、心が折れてしまった
  • -

結果：AC / TLE / -- ，+0, 184.35pt, 128位
レーティング：2347 -> 2332


詰めの甘さが露呈してしまった素敵な回になりました。問題は好きですが。
社会人なりたてで、まだ深夜回に参加する勇気はないので、
こんな感じでまったり生きていきたいと思っています。