TopCoder2D

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が心配でずっとテストしてたので開かなかった

今後

黄色戻りたい。

TopCoder SRM 563 Div1 参加記

本番 | 04:30

結果

• System Test : x--
• Challenge : +0/-0
• Point : 0pt
• Rating : 1519 -> 1458

開始前の目標

• easyを確実に通す
• それ以外はどうでもいい

目標の達成度

• 達成できていない

反省

• 「確実に通す」と目標を立てながら, 確実に通ると確信できるまでアルゴリズムをしっかり考えていなかった
• 自分の貪欲解法の反例がないか, 全く考えずに実装し始めてしまった
• 自分も合わせて6人も同じ部屋で間違った解法を提出していたのに, Challenge Phaseは, あきらめて傍観していた

今後

• 貪欲法は, 反例がないかよく考える
• 貪欲は余程自信がない限り落とす確率が高くなるので, DPに逃げられるなら逃げる
• ただし, いつまでも貪欲から逃げていては, 貪欲をできるようにならないので, 練習のときは進んで貪欲解法で実装する
• Challenge Phaseでは, 落とす気がなくても他の人のコードをちゃんと読む
  • 他人のコードを読む練習になる
  • まぐれでChallengeできれば一石二鳥

TopCoder SRM 549 Div1 参加記

本番 | 00:27

きゅうりさんの帽子が出てきました.

結果

Rating

• 1407 -> 1448

Score

• Easy : 129.82 pt
• Med : Unopened
• Hard : Unopened
• Challenge : +0/-0

Easy

• 概要
  • 次の条件を満たす円錐A, Bを使って, 魔法使いの帽子を作ることができます.
    • Aの円錐をBの円錐の上にかぶせます.
    • このとき, Aの円錐の頂点は, Bの円錐の頂点より上側にないといけません.
    • また, Aの円錐の頂点とBの円錐の頂点が重なるのも許しません.
    • AをBにかぶせたとき, Bの円錐のどこか一部が見えていなければいけません.(完全にAがBにかぶさってはいけない)
  • 帽子の上側となる円錐の候補がN個. 帽子の下側となる円錐の候補がM個与えられます.
    • 各円錐は, 円錐の高さと, 円錐の半径が与えられる.
    • 以下の例は, 帽子が作れない例と作れる例です.

• このとき, 最大でいくつの帽子を作ることができるでしょう.

• 解法
  • 各円錐をグラフのノードとみなします.
  • 上側の円錐のノードと, 下側の円錐のノードとで, 帽子にできるペアをエッジでつなぎます.
  • あとは, このグラフについて, 二部グラフの最大マッチング問題を解けばいいです.
  • グラフはこんな感じになりますね↓

Med

• 開けずに帰りました

My Comment

反省点

• 英語読むの遅いです.
• アジア地区もあるので, 英語の勉強しましょう.

よかった点

• 貪欲をやらずに, 確実性のある二部マッチングで解いていたのはよかったでしょう.
• でも, 貪欲解法思い付けた方がいいですね.

Codeforces Round 92 Div 1 参加記

本番 | 18:46

今回は結構調子がよかったです.

次, オレンジになれるといいな～.

結果

Rating

• 1684 -> 1751

Score

• A : 852 pt (00:37)
• B : 518 pt (01:48)
• Hack : +0/-0

Problem A

• 貪欲に解きました.
  • [小さめの素数*i] の位置には, 入力文字列の中の出現回数が多いアルファベットを割り当て
  • 逆に大きめの素数の位置には, 出現回数が少ないアルファベットを割り当て

Problem B

• x+y≡0 (mod 2a) の位置を, 2次元平面上に書き出してみると, ／の形をした直線が何本もできることがわかります
• x-y≡0 (mod 2b) の位置は, ＼の形をした直線ができます
• 答えを求めるためには, この線をなるべくまたがずにスタートからゴールへ行かなければいけません
• ／区切りでX座標に直して, ＼区切りでY座標に直します
• あとは, 8方向に移動できると考えて, スタートからゴールまでの最短距離をとればいいです（図参照）

Codeforces Round 91 Div 1 参加記

本番 | 18:46

結果

Rating

• 1698 -> 1684

Score

• A : 390 pt (00:55)
• B : 668 pt (01:23)
• Hack : +0/-0

Problem A

• コメント
  • あきらかに愚直にできない
  • Lucky Numberとか使う問題はすごく苦手です
  • 解法は, 結構短時間で思いついたけど, 信じられないほどのコーディング時間がかかった
• 解法
  • 4と7で作れる整数を10^9ぐらいまですべて列挙
  • これを列挙するだけなら, そんなに数はありません
  • あとは, lとrに近い境界を適当に探して, こまごまとしたことをやるだけです

Problem B

• コメント
  • 僕は, こっちの方が余程A問題としてふさわしいとおもいました
  • B問題から先に解けばよかった...
• 解法
  • 結果は, 以下の2パターンしかない
    1. 全ての"47"が"44"に変化
    2. 奇数位置から, "447", "477" という文字列が発見できたら, "447"と"477"でひたすらループする

My Comment

• レートは下がったけど, 前回のSRMの反省点を活かして, ミスなく確実にコーディングできたのはよかったと思う
• A問題みたいな問題は, なれていくしかないのかな