Hatena::Grouptopcoder

TopCoder2D

2018-12-14

TopCoder SRM 744 Div1 参加記

| 03:34

久しぶりに参加記。

結果

  • System Test : o--
  • Challenge : +0/-0
  • Point : 105.59pt
  • Rating : 1328 -> 1396 (+68)

開始前の目標

  • 遅くてもいいからeasyを確実に通す

目標の達成度

  • 達成した

コンテスト中の思考

Easy

  • ひとまず、(0,0)から(7,7)ぐらいまでノートに書き出してみる。
  • 「(0,0)〜(a,a)」の正方形について考えてみる
    • aが1, 4, 7, ...と増えるごとに、1の合計数は3, 12, 27, ...という増え方をする
      • 式にすると、3 * (((a + 2) / 3) ^ 2)
    • aが2, 5, 8, ...と増えるごとに、2の合計の数は5, 16, 33, ...という増え方をする
      • 式にすると、((a + 1) / 3) * (3 * ((a + 1) / 3) + 2)
  • 「(a1,b1)〜(a2,b2)」についてどう求めればいいか考えてみる
    • 「(0,0)〜(a2,b2)」から「(0,0)〜(a1-1,b2)」と「(0,0)〜(a2,b1-1)」を引いて、「(0,0)〜(a1-1,b1-1)」を足せばいい
    • ↑累積和とかでよくあるやり方
  • 「(0,0)〜(a,b)」をどう求めればいいか考えてみる
    • a = bであれば、(0,0)〜(a,a)の正方形の合計を求めればいいので、上の方で書いた思考で求められる。
    • a < bであれば、「(0,0)〜(a,a)」の正方形に「(0,a+1)〜(a,b)」の長方形を足せばいいことになる。
      • この長方形は、「(0,a+1)〜(0,b)」の1列目の合計さえ求まれば、これと同じものがa個続くだけであることが図に書き出してるとわかる。
      • 1列目の「(0,a+1)〜(0,b)」は、..., 1,2,0,1,2, ...のように、0~2が繰り返し現れる数列なので、floor((b - a) / 3) * 3 + 端っこの(b - a) % 3の部分を足したものになる(わかりづらい)。
    • a > bの場合は、a < bと全く同じ考え方

Med, Hard
  • Easyが心配でずっとテストしてたので開かなかった

今後

黄色戻りたい。