Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-04-17SRM503 Div1

  • 250:218.45, 500:275.71, score:494.16, rank:63, rating:2172(+64)
  • あと少しだー頑張ろう

SRM503 Div1 250 ToastXToast

| 22:58 | SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

あまり問題文が分り易くない

ぱっと見、解が最大2にしかならなさそう

よく考えてみても最大2にしかならなさそう

書いた

提出


チャレンジフェーズ

残り5分くらいで明らかにおかしい人を見つけたがおかしすぎて解読しきれず

もっと早く読み解く力を身につけなければ。。。


ソースコード

続きを読む

SRM503 Div1 500 KingdomXCitiesandVillages

| 22:58 | SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何これ近い村から確率1/2していくだけじゃないの?早解きゲームか

書いた→サンプル合わない

常に1/2じゃなかった。手で書き下してみる。

1/2→1/3→1/4→・・・となるみたい。

確認用全探索コードを書く。1/6まで確認した。間違いないぽい

修正。サンプル合った。提出。


手で書き下すところで時間を使い過ぎた。

発想をもっと柔軟にして早く解法を導き出さないと、これ以上の順位が難しいなあ・・・


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110417

2011-04-08SRM502 Div1

  • 250:219.90, 500:150.00(+125), score:494.90, rank:63, rating:2108(+48)
  • 500に時間かけすぎた。でも通って良かった。

SRM502 Div1 250 TheLotteryBothDivs

| 22:54 | SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

一瞬包除原理かと思ったが全然違った

他の要素がsuffixになっている要素を削除するだけだった

少し時間を使い過ぎたが適当に書いて提出


ソースコード

続きを読む

SRM502 Div1 500 TheProgrammingContestDivOne

| 22:54 | SRM502 Div1 500 TheProgrammingContestDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM502 Div1 500 TheProgrammingContestDivOne - SRM diary(Sigmar) SRM502 Div1 500 TheProgrammingContestDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となくだが、問題aとbのどちらを先に解くかの比較としては、

aを先に持ってきた場合の総減点と、bを先に持ってきた場合の総減点を比較すれば良い気がする

何か怪しいがとりあえず書いてみる

サンプル合った

・・・

けどこれは明らかにダメだな

減点が少ないが得点が高く、目一杯時間を使いきらないと解けないような問題が反例になる

解く問題のセットが決まれば、上記の順位付けでとりあえずは書けそうだが・・・

セットを決めようとすると2^50とかになってしまう・・・どうするんだ・・・

・・・

(結構長く悩む)

・・・

よく考えたら、逆に考えれば良いのか

全体の順序を先に決めて、その中でどの要素を使うかを決めても同じ結果になる・・よね・・

ってことは普通に上記順序付けでソートしてDPするだけで良かったりする?

書けた

提出

もう一度見直す

あ、、微妙にDPの更新間違っとる!(泣

どうせ提出時198点とかだし今更再提出しても大して変わらんか・・・

再提出

すぐ出し直したのに150点とか。今更だが再提出の10%ペナルティってどういう意味なんだ


チャレンジフェーズ

これってサンプル相当弱いから、適当なGreedyとかでも通るよなぁ・・

と思いつつ、インターミッションの間にいくつかテストケースを用意する

皆さんの回答見るとちゃんとDPしてるから皆頭いいなーと思った

でもよく見ると最初のソートの仕方が皆けっこう適当だな

maxPointsでソートとか、pointsPerMinuteでソートとか、すぐ反例思いつくような・・不注意だなあ

3つ撃墜(コード読み違えて1回失敗)

ラッキーでした


ソースコード

続きを読む

laycrslaycrs2011/04/08 23:51再提出の10%ペナルティは,再提出するたびに,「最高点の10%」だけ点数がマイナスされます.
500点問題なら,再提出するたびに50点減点され,それが最高点の30%の150点を下回ると,150点になります.

jackperseljackpersel2011/04/09 18:11おお、ありがとうございます。今更ながらルールを理解しました・・・
いつ提出しても10%ペナルティは結構きついんですね。。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110408