Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-02-10SRM532 Div1

  • 300:246.07, 450:257.83, 1000:Opened, score:503.90, rank:46, rating:2257(+70)
  • チャレンジ祭りだったがチャレンジ強い人がいると全然ダメ
  • 久々に赤に戻りました

SRM532 Div1 300 DengklekMakingChains

| 02:29 | SRM532 Div1 300 DengklekMakingChains - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM532 Div1 300 DengklekMakingChains - SRM diary(Sigmar) SRM532 Div1 300 DengklekMakingChains - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

3つとも数字のやつを全部足しあわせておいて、左と右に適当にくっつければいいんじゃないのか?

書いた

合わない。.7.とかサンプルにあった。親切すぎ!!

よく考えると300だしなあ。他にもコーナーケースがありそうだ。

要素数1のサンプルがない。なるほど。危ない・・・修正修正

あとは大丈夫かな・・

提出


ソースコード

続きを読む

SRM532 Div1 450 DengklekBuildingRoads

| 02:29 | SRM532 Div1 450 DengklekBuildingRoads - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM532 Div1 450 DengklekBuildingRoads - SRM diary(Sigmar) SRM532 Div1 450 DengklekBuildingRoads - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

なんだこりゃ。典型的なDP。簡単すぎないか?

K<=8だから直前8個まで+今見てるの1個で9個の偶奇を覚えておけばいいだろう

DPの更新時は、直前8個のどれかと今見てる人をくっつけて道を1つ増やすか、見る人を次に進めるかの2パターン

書いた。

合わない。

しかも間違いが分からない。簡単と思いきや訳わからん・・・

・・・

分かった。道を追加するのに、順番を考慮していないから同じパターンを2回以上数えている。

直前に追加した道を直前8個の誰に対して追加したかを覚えるように変更

できた。

合った。

提出。

結構時間かかった・・・450の割に難しい。。


ソースコード

続きを読む

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

2012-02-09SRM531 Div1(Practice)

  • 参加できなかったのでpracticeで

SRM531 Div1 300 NoRepeatPlaylist

| 02:27 | SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

EasyにしてはかなりハードなDP。300だけある・・

直前のM曲は全てdistinctであることを利用すると、残り何曲演奏されていないかを記憶するDPが可能

自分は直前のM曲を除いて1回以上演奏された曲が何曲あるか記憶するというよく分からない書き方をしてしまって時間がかなりかかった。


ソースコード

続きを読む

SRM531 Div1 500 MonsterFarm

| 02:27 | SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

無限に増えるかどうかの判定がまず必要

普段ならとりあえず適当にループを回して、収束するかどうかを判定するところだが、今回はMODがかかっているので危険そうである

念のため頑張って無限に増えるかどうかを真面目に判定することにする

まずは、全ての2分岐以上に分岐するノードに対し、そのノードから出発して自分に戻ってくることができるかを判定する。

次に、始点からそのノードへ到達可能かを判定する。

これで無限に増えるかどうかが判定できた。何となく計算が冗長な気がしないでもないが、計算量は問題ない。

あとは、無限に増えない場合にシミュレーションを行うだけである。

何ステップで収束するか検討するのが面倒だったので、行列化して10億乗しておいた。さすがに大丈夫だろう・・・

一発で通った。


やっぱりMODは罠だったらしい。ちゃんと計算しておいて良かった。


ソースコード

続きを読む

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

2012-02-08SRM530 Div1(Practice)

  • 参加できなかったのでpracticeで

SRM530 Div1 250 GogoXCake

| 02:26 | SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) SRM530 Div1 250 GogoXCake - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

一番上の列の一番左のマスは、カッターの一番上の一番左に当てはめないとダメに決まっているので左上からGreedyにカッターに当てはめていくだけ


ソースコード

続きを読む

SRM530 Div1 500 GogoXMarisaKirisima

| 02:26 | SRM530 Div1 500 GogoXMarisaKirisima - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM530 Div1 500 GogoXMarisaKirisima - SRM diary(Sigmar) SRM530 Div1 500 GogoXMarisaKirisima - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

とりあえず0からN-1への最短パスを調べる。(これより短いパスはないんだから、全部のエッジを使ってしまってもいいだろう。)

あとは今まで通ったノードを覚えておいて、その中に含まれるノードからノードへのパスを適当に探して新たなパスとして追加する。

これも最短のを取っておけばたぶん大丈夫だろう。

何か最短ばかり頭にあったのでダイクストラの変形を書いてしまった。

よく考えたらコストが全部1だからBFSで十分だった。何やってるんだ・・

提出したらTLE

通ったパスを求めるための、親を記憶する変数dad[]の値がバグって無限ループしていた。ダイクストラとか詳細を覚えていないライブラリを変形するからだ・・・

直して通った。


Editorial見たら1行で書けるよ、と書いてあった。

そんな解もあるんだな・・・


ソースコード

続きを読む

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