Hatena::Grouptopcoder

TopCoder2D

2012-12-08

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できれば一石二鳥

2012-07-09

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個与えられます.
      • 各円錐は, 円錐の高さと, 円錐の半径が与えられる.
      • 以下の例は, 帽子が作れない例と作れる例です.

f:id:Respect2D:20120710002251j:image:w400

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

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

f:id:Respect2D:20120710002406p:image:w400

Med

  • 開けずに帰りました

My Comment

反省点

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

よかった点

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

2011-11-04

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方向に移動できると考えて, スタートからゴールまでの最短距離をとればいいです(図参照)

f:id:Respect2D:20111104235806p:image:w360

2011-10-28

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問題みたいな問題は, なれていくしかないのかな

MoonMoon2016/05/03 09:20I tried taking a look at your site on my new iphone 4 and the layout doesnt seem to be right. Might wanna check it out on WAP as well as it seems most cell phone laotyus are not working with your site.

JacklynnJacklynn2016/05/04 02:04Het staat je vrij het in het geheel niet eens te zijn met de auteur van bovenstaand artikel. Maar hij voert wel feiten en argumenten aan om zijn stellingen te onderbouwen. Die tref ik in jouw reactie niet aan. Aangifte door twee vrouwen van sexueel misbruik en onderzoek daarnaar door de Zweedse politie en justitie is toch echt iets anders dan “valse <a href="http://lpqsylb.com">zekd&zaeenroddeln#8221;.</a>

LatashaLatasha2016/05/08 12:29Hi Kim, yes I too have had a few favorite blogs diaerpsaping into the abyss. I agree with Oomph - I'm going on Hiatus is a perfect explanation. HAPPY Halloween sweets, Axx http://tucciohovbd.com [url=http://dnuphsd.com]dnuphsd[/url] [link=http://fooutfhwe.com]fooutfhwe[/link]

2011-10-13

TopCoder SRM 522 Div1 参加記

| 00:42

調子悪いです~.

結果

Rating

  • 1323 -> 1270

Score

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

Easy

  • 最初考えようとしてた方針
    • 相手のアルファベットを全て消せるような置き方があれば勝てる
    • つまり, 初期の文字列の左端か右端にAがあれば, Aの勝ちということになる
    • でも, 一番最初にAが勝てなかった場合の勝者がだれになるか, 考えられなかった
    • 他の人のコードを見たら,「最初にAが勝てなかったら, Bが勝つ」という解法で解けるらしいです
  • 本番書いたコード
    • nをマスの数とすると
    • それぞれのマスにコインが置かれているかどうかは, 2^nのビットで管理できる
    • さらに, コインの置き方は, 最大でも約n^2種類
    • よって, O(2 * n^2 * 2^n) のDPで解ける
    • デバッグに非常に時間がかかりました

Med

  • Aの値だけ変更, Bの値だけ変更, Cの値だけ変更, AとBの値だけ変更, AとC,.. の全てのパターンについて, どうなるか考えてみた
  • わからなかった!!

My Comment

反省点

  • ひとつひとつの処理をどのような意図で書いているかを考えながらコーディングする
  • 「まとめて全てコーディングしてから, デバッグ」ということをしているけど, デバッグ能力低いから, バグを探すのに時間かかるし, これはやめておくことにしよう