Hatena::Grouptopcoder

TopCoder2D

|

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に落ちそうです.

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


ではでは~.

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

2011-08-13

フロンたんは何も悪くない

Codeforces Round 81 参加記

| 04:55

ディスガイアな回でした.

そして, ReadForcesな回でした.

はい, 英語がとんでもなく苦手な僕には明らかに無理な回でした.

結果

Div2は, おそらくレート変動せず.

A問題を提出したけど, Failedで結局0点でした.

本番

A問題
  • 問題を理解するのに15分ほど要した.
  • 理解したらやるだけ, とか思ってたら, 丸め誤差が発生して死んだ.
  • 情報系失格である.
B問題
  • 問題を理解するのに, 30分以上要した.
  • サンプルの二番目の求め方がわからなかった.
  • 100パーセントを上回る人にはアメを配れないとか思ってたせいで出力が合わなかった模様.
  • ↑これだけのせいで解けないとか, おわってます.
  • 書いてたコードは, ただの全探索コードで, 誤解してた箇所を直したら通りました.

感想

「英語」がたいせつです. 世の中「英語」が全てです.


あ, ちなみに問題文が難しいだけであって, ディスガイアは何も悪くありません.

ディスガイアは何も悪くないです.

ですので, みなさん, ディスガイアをうらまないでください.

|