Hatena::Grouptopcoder

yehara のTopCoder日記

2012-06-08

SRM 545 Div1

12:27 | SRM 545 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 545 Div1 - yehara のTopCoder日記

143.42 + 261.17 + 0 + 50*0 - 25*0 = 404.59 (103位) Ratings 1876 -> 1947

すごく久しぶりだけど、なんか書いておくかな。問題自体の説明はやめて、どういう方針で実装したかのメモだけ。

Level One - StrIIRec (275)

12:27 |  Level One - StrIIRec (275) - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  Level One - StrIIRec (275) - yehara のTopCoder日記

問題がややこしいけど、まあ先頭から順に深さ優先で探索していくだけ。探索は辞書順で小さいものから。途中の段階で、この先最も辞書順で後になる形を仮定したときの inversion を計算することで、それ以上深く探索を進めて解がみつかるかを判定できるので、そこで枝刈りできる。実装は時間かかった・・・

Level Two - Spacetsk (500)

12:27 |  Level Two - Spacetsk (500) - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  Level Two - Spacetsk (500) - yehara のTopCoder日記

K=1 の場合は、格子点の数 (H+1) * (L+1) を返して終了。以下、K>1 のケース。

まず真上に飛ぶ場合を別に計算。出発点を固定したとしたら組み合わせ C(H+1, K) (C(a, b) はコンビネーション aCb のつもり)で、出発点が L+1 通り選べるので、C(H+1, K) * (L+1)。

斜めに飛ぶ場合は、出発点と、最終発信場所の相対位置関係毎に計算した。左右対称に考えられるので、右斜めに飛ぶ場合だけを考えて結果を2倍する。最終発信場所の相対位置は (K-1,K-1) 〜 (L, H) の 2 次元範囲を全探索。相対位置を (x, y) とすると GCD(x, y) + 1 が出発点から最終発信場所までに存在する格子点の数になるので、最終発信場所は常に発信するとして、残りの組み合わせは C(GCD(x, y), K-1)。これに出発点のとりかた L - x + 1 と、左右対称分の 2 を掛けて加算すれば OK。

まとめ

12:28 |  まとめ - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  まとめ - yehara のTopCoder日記

ひさしぶりに Medium ができて highest 更新。2000 が見えてきたか?

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20120608

2011-03-09

SRM 499 Div1

14:37 | SRM 499 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 499 Div1 - yehara のTopCoder日記

o o x 219.16 + 293.49 + 0 + 0 = 512.65 (126位)

Level 1 (250)

同じ数字を言ううさぎはできる限り同じ色とみなす。同じ色の数字を言えるのは、最大その数字+1匹という点だけに注意すれば OK かな。これで計算する和が入力の個数を下回ることはなさそう。テストケースが親切なので、落としている人は少なかったみたい。みんな速いなあ・・・

Level 2 (550)

RETURN を入力する回数は固定なので SPACE/DELETE を入力する回数だけ考えれば良いはず。いろいろなサンプルを考えていくと、DELETE を使うケースは、同じ手数の DELETE を使わない手順に置き換えられる気がしてきた。たとえばサンプルにある [3,2,3] は

  • [3,3,3] にしてから 2 行目で DELETE する手順
  • [2,2,2] にしてから 1,3 行目で SPACE を入力する手順

は同じ手数。

あと、上下に連続する SP は必ず 1 回の SPACE 入力で対応できるはず。

ということで全ての桁で連続する SP のブロックが何ブロックあるのか(何本の縦線で SP だけを塗りつぶせるか)を数えれば良いのではないかという仮説を立て、実装する。するとテストケースが全部通った。しばらく反例を考えるが思いつかないので提出。

550 がこんなに簡単なはずないなーと思い、提出後も必死に反例を考え続けたが思いつかない。なんと通ってしまった。個人的には儲かったが、こんなちゃんと証明できないやり方しかできない自分もレベルが低いと思うし、問題も 550 にするのは不適切なんじゃないかなーと思ってしまう。

Level 3 (1000)

あきらめて、Level 2 を考え続けてた。

まとめ

チャレンジフェーズもずっと Level 2 を考え続けてた。全体で見ると Level 2 が撃墜されまくっていたので、自分のも絶対だめだろうなと思ってたがまさかの通過。結構Rating 上がった。1766 -> 1841

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110309

2011-02-27

SRM 498 Div1

23:58 | SRM 498 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 498 Div1 - yehara のTopCoder日記

o o x 198.93 + 323.61 + 0 + 0 = 522.54 (196/824位)

Level 1 (250)

やるだけ問題?配列へのアクセスではみ出さないようにだけ注意して、先頭から順番に調査していく。もうちょっとはやく解きたい。

Level 2 (450)

それぞれのセルにおいて、すべてのマークされたセルからの距離を表すマーク数次元の座標(ベクトル?)を考える。同じ座標を持つセルの石同士は可換なので、とりうるすべての座標に対して、同じ座標のセル数の階乗をかけ合わせていく。いままで参加した中で一番簡単な Level 2 じゃないかな。

C の人を見てていいなと思うのは Map のキーに int 配列をそのまま指定できるらしいこと。Java だとキーの指定でクラスを作るか文字列表現にマッピングするなどちょっと一手間入れないといけない。

Level 3 (1000)

35 分くらいで 2 問終わったのでちょっと考えてみたが、さすがにそんなに簡単ではなさそう。ここは分をわきまえて無理をせず、終わった 2 問の見直しやチャレンジケースの検討に残りの時間を使うことにした。

まとめ

チャレンジフェーズはなにもできず。他の人に先をこされたのは仕方ないが、システムテストで落ちてるものも結構あった。チャレンジ力が弱いな・・・。

前回のエントリを書いてないが、0 点で rating 1878 -> 1706 に大暴落。まあそれまでが自分にしては高すぎる rating だったので、このあたりが実力かな。今回は 1706->1766 でちょっと取り戻した。長らく滞在していた 1500 前後からはちょっと上抜けできてきたような気がする。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110227

2011-02-02

SRM 496 Div1

12:13 | SRM 496 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 496 Div1 - yehara のTopCoder日記

o x x 220.47 + 0 + 0 + 50 = 270.47(201位)

Level 1 (250)

ここ最近では一番簡単な問題な気がする。けど、インデックスの順番がよくあるケースと逆なのでちょっと慎重になってしまった。左上が起点なら、普通 (x, y) は x が縦軸でしょうに・・・

Level 2 (500)

普通に DFS でも間に合うんじゃねと思ったが甘かった。500 でそんな簡単なわけないよね。TLE でチャレンジされました。mod で分けて考えればよかったのか、なるほど。そういえば最近こういう問題あったな。

Level 3 (1000)

Hard はこれまで一度も手をだしたことがないけど、30 分ちょっとで 2 問おわったので、初めてちゃんと見てみる。文字列全体の長さで決まる部分はどの経路を通っても合計は同じなので、共通プレフィックスで決まるスコアの合計を最大化する問題ということまではわかった。まさかとおもって Greedy にやってみたけど当然だめ。タイムアップ。

まとめ

赤のいない平和な部屋でした。チャレンジフェーズで 250 を一撃墜。レベルの高い部屋なら取れなかったと思うのでラッキー。

1 問しかできなかったけど Rating は微増 (1860->1878)。4 回連続ベスト更新だ。

gfnkjlegfnkjle2011/02/28 08:07GpiIQE <a href="http://zyavmhehqtad.com/">zyavmhehqtad</a>, [url=http://lgvhggijrbmv.com/]lgvhggijrbmv[/url], [link=http://vqefrusqjyzg.com/]vqefrusqjyzg[/link], http://vhjmfbixjovo.com/

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110202

2011-01-27

SRM 495 Div1

03:27 | SRM 495 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 495 Div1 - yehara のTopCoder日記

o x x 179.79 + 0 + 0 + 50 = 229.79(91位)

Level 1 (275)

ある場所のカードの数値を決定するのに、最小最大の両端から最も無駄なく数字をつかっていき、最後に残った真ん中の数字で複数選択肢が残ってるかどうか判定した。

Level 2 (500)

典型的 DP な感じだけど・・・。大きなケースで TLE してしまって、結局タイムアップ。まだ良いやり方がわかってません。

Level 3 (975)

みてない。

まとめ

チャレンジフェーズでは 500 のあきらかにおかしいやつをみつけた。戻り値が 1 - 1/整数 みたいなのしか返してなくて、それ問題文にあるテストケースも通らんやん。おいしくいただきました。

チャレンジのラッキーがあったにせよ、1問だけでこんなに Rating あがるのか?(1779->1860)。自己最高を3回連続で更新。最近ちょっとインフレ気味。ちょっと実力以上の数字になってる気がする。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110127