Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-16TCO2010 Qual2

とりあえず予選は通過しましたが、まだまだ課題が多いです。。

TCO2010 Qual2 250 JingleRingle

| 23:25 | TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) のブックマークコメント

Problem Statement

1jingle買うと1jingle売ることができるようになる。最も少ないringleで1jingle購入し、最も多いringleで1jingleを売却することでGreedyに儲けを最大限にできる。儲けが出なくなるまでこれを繰り返す。

特に引っ掛けもないのでsubmit。passed。

source

TCO2010 Qual2 500 FuzzyLife

| 23:25 | TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) のブックマークコメント

Problem Statement

ライフゲーム(Wikipedia)という有名なゲームがあるらしい。これをシミュレーションする。

どうにも実装に時間がかかってしまいます。練習が必要ですね。。。

結果はpassed。

何かプログラムがおかしい人が2人撃墜できて100点もらえました。ラッキーでした。

source

TCO2010 Qual2 1000 HandlesSpelling

| 23:25 | TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) のブックマークコメント

Problem Statement

ある長さまでの最大スコアをDPしていくのかと思って一生懸命コーディングしていましたがそれでは正しい答えが出ないということが分かり、本番終了しました。

実は最大スコアではなく、ある位置からある位置までの最大カバー文字数(≒最小非カバー文字数)をDPしてやれば答えが出たようです。

もう少し色々な角度から解法を考えることができなければ、やはりダメですね。少し一方向に進みすぎる傾向があるので、視野を広げる訓練が必要そうです。。。

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