Hatena::Grouptopcoder

TopCoder2D

|

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

反省点

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

2011-10-04

TopCoder SRM 520 Div1 参加記

| 03:17

青の安全圏まで戻ってきました.

また寝落ちして緑まで下がるとかあり得るので, 気をつけたいと思います.

ということで, 簡単に参加記書きます.

結果

Rating

  • 1257 -> 1343

Score

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

Easy

  • 1~3問目を, それぞれ解いたことにするかどうかで場合分け
    • O(2^3)
  • その後スコア計算し, 最大値更新
    • LuckPointを使うときは, 3問目から順番に使った方が明らかに得なので, その方法でスコア計算(貪欲).

Med

  • 実装が間に合いませんでした...
  • 方針としては, 以下のように考えてました.
  • あらかじめ, 以下のような表をDPで計算しておきます.
    • 1問目だけを通したとき, スコアがxであるときのパターン数を記憶する表
    • 2問目だけを通したとき, スコアがxであるときのパターン数を記憶する表
    • 3問目だけを通したとき, スコアがxであるときのパターン数を記憶する表
    • 1問目と2問目, 1問目と3問目, 2問目と3問目, 1・2・3問目, も同様
  • あとは, 上記の表を利用しつつ, [21][200001]のDPでうまいこと計算しながら解く.

My Comment

今回のMedは, 実装の仕方が非常に冗長でミスりやすく書くのに時間がかかるようなコードを書いてしまっていたので, もっとスマートに書けるようになる必要がありますね.

あと, Easyを解ける確率があがってきたので, 200点台を取れるようにがんばりたいところです.

2011-09-11

TopCoder SRM 517 Div2 参加記

08:53

皆「お前, またDiv2落ちたのかよ」

僕「全ては英語のせいなんだ!!(爆」

開始前のチャット「\アッカリ~ン/」


ということで, 参加記書きます.

Result

Rating

  • 11931228

Score 404.49 pt

  • easy : 190.46 pt
  • med : 164.03 pt
  • Challenge : 50 pt

Easy

  • 問題を難しい方向へ勘違いしてしまい, バカみたいにタイムロス.
  • 読み直したら, 昔解いたことある問題だったので, すぐ書いて提出.
  • 方針
    • 全てのマスがBであれば, min(H,W)
    • それ以外は, Bの列と行をカウント

Med

  • こちらも, はじめ読解ミスでタイムロス.
  • さらに, FORループの開始文とか終了判定とかミスってて, 再提出.
  • 方針
    • 2から順番に, targetを作ることができる数であるかをDPで計算.(bool dp[100001]みたいなの作る)
    • 整数xが, targetを作れる数であるかどうかは,「xを割りきる全てのiについて, (dp[i]==true || dp[x/i]==true)であるか」により判定できる.

Hard

  • ずっとMedにミスがないかを見てたので, 読んでません.

My Comment

  • 次こそは, 寝落ちやら, 問題文の読解ミスやらで, Div2に落ちてこないようにしたいです.

2011-08-21

Respect2D20110821

TopCoder SRM 514 Div1 参加記(?)

| 07:05

寝落ちしたー!!(泣)

250考えてる間に寝落ちしたぁ・・・。

レート100下がった・・・・。

最悪・・・・・。


次はこんなことないようにします。

がんばる!

2011-08-20

Respect2D20110820

Codeforces Round 82 Div2 参加記

| 11:56

開始直前に変更したやよいちゃん画像のパワーにより, 無事Div1に上がることができました.

ということで, 参加記書きます.

結果

Rating : 16021660

Rank A B C D Hack
54 00:08 00:25 00:51 01:53 ±0

簡単な問題を解くのに時間がかかってしまいましたが, こどふぉでは, 初めて紫になるのでうれしいです!

A問題

  • 読解できたらやるだけ
  • でも, 読解がなかなかできず3~4回問題を読み直し...
  • 実装はすぐ終わり, 提出した時間は8分
  • 遅すぎ!!

B問題

  • こちらも読解にかなり時間をかけました
  • 焦って実装まで手間取ってしまい最悪でした
  • 3つとも他のより小さいのを先に削除しておいて, costの最小を取りました

C問題

  • 問題文読むのに15~20分ぐらいかかってたかも
  • dp [ M (原料の種類) ][ N (パンの合計重量) ] = 最大売上
  • ↑これでDPするだけ

D問題

愚直はまず無理っぽい.

僕が思いついたのは,「スタート地点の周りに, どのように陸が広がっていればよいかの情報が作れれば, オーダは大丈夫そうだ」ということです.

  • 26(アルファベット数) * (1000*1000)(スタート地点の周りに正しく陸が広がっているかのチェック)

たとえば, Sampleの一番目であれば, スタート地点のまわりに, 以下のように陸が広がっていればいいことがわかります.

#.#
...
#S#

このようなマップを事前に作っておいて, アルファベットごとに, まわりがこういう形になっているかということを確認していくわけです.

このマップを現実的な時間で作り上げるのが, 少し難しいと思いましたが, そこはがんばりました.

  • 多分O(10^6)

感想

相変わらず問題文を読むのは遅いですが, Div2レベルであれば確実に問題は解けるようになってきているので, この調子でがんばりたいと思います.

次からはDiv1に上がります.

今のレートが1660なので, 油断したらすぐDiv2に落ちそうです.

次は, ミスしないように, 確実に点を取っていきたいです.


ではでは~.

次同じ部屋になった人はよろしくです~.

|