Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-04-25SRM541 Div1

  • 250:234.52, 550:292.65, 1000:Opened, score:527.17, rank:29, rating:2274(+104)
  • 特段普段と変わらない気がしたのだがなぜか順位は良かった

SRM541 Div1 250 AntsMeet

| 01:12 | SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

任意の蟻のペアで衝突判定をして、時間の早い順に並べて、死んだ蟻を取り除きながら真の衝突判定をする

とか思ったけどあまりにも面倒そうだったので他の手段を検討

単純なシミュレーションで間に合うことに気づいたので書く

サンプル合った

提出


チャレンジフェーズ

ボロボロと周りが落とされていくんだが全然何が悪いのか分からない

どうやら座標を2倍していない人がたくさんいたらしい

サンプルにそういう例があるのでまさか2倍せずに(or 0.5刻みにせずに)提出してる人がいるとは思っていなかった・・・


ソースコード

続きを読む

SRM541 Div1 550 AkariDaisukiDiv1

| 01:12 | SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

上限が1000万だから単純なループにする問題ですかね

だとすると、Xに対してWaaiとかAkariとかくっつけた時に解が増える増分だけ調べればいいのでは

これって、Xの先頭はWaaiWaaiWaai...になるし、後ろは...DaisukiDaisukiDaisukiになるから、50回以上繰り返せば増分は一定の値に収束するっぽい

Xが短い間は全探索して、ちょっと長くなったらprefixとsuffixだけ覚えて、50回以上になったらあとはループするだけ

やるだけ・・?

なぜ550


書く

増分の計算かなりめんどい

思ったよりは大変だった


できた

提出


ソースコード

続きを読む

PraveenPraveen2012/11/14 15:22You've really captured all the esstenials in this subject area, haven't you?

lltwektgdjilltwektgdji2012/11/17 00:38s3e55e <a href="http://weadgecnprbz.com/">weadgecnprbz</a>

zkwvhwizkwvhwi2012/11/17 10:47mzuI7w , [url=http://amjymbwsqtpw.com/]amjymbwsqtpw[/url], [link=http://jtoocgzxmaus.com/]jtoocgzxmaus[/link], http://uoyfejtwsvcz.com/

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

2012-04-22TCO2012 Round2A

  • 300:WA(+50), 450:Opened, score:50.00, rank:430, rating:2170(-23)
  • cafelierさんと同じ部屋だった
  • なかなかに厳しい問題セットだった・・・
  • 最後の3分間チャレンジができなかったとかで、無効試合になるかもしれないらしい → ならなかった

TCO2012 Round2A 300 SwitchesAndLamps

| 17:48 | TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

以下の2つの問題に分けて考えればいい

  1. 与えられた情報から、スイッチとランプをこれ以上分割できないグループに分割する
  2. 各グループを更にスイッチ・ランプ1個ずつのグループまで分割するための最小テスト数を求める

時間をかけた挙句、1,2ともに間違った解答を出してしまいチャレンジされる


後で

1のほうは、実は縦に見て全く同じ結果のものを集めればいいだけだったりする

つまり、1回目のテストがY、2回目がN、3回目がYのスイッチがあったとすると、それと同じグループに入れるスイッチは、やはり1回目のテストがY、2回目がN、3回目がYのスイッチである。

同様に、ランプの全く同じパターンのものを集める。

1つのグループ内で、スイッチとランプの数が違っていたら-1。


2のほうは、とりあえず全てのグループに対し、並列で試験ができるので、一番スイッチ数の多いグループだけを考えればいい。

並列で試験できることを考えると、試験数を最小にするには、グループをYとNで2分割することである

分かれた2つのグループに対し同時に試験ができるから、さらに大きい方を2分割して・・・と続けていくと、いつかスイッチ数が1になる

これにかかる回数を出せばOK


ソースコード

続きを読む

TCO2012 Round2A 450 CucumberWatering

| 17:48 | TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

どう見てもDPっぽい

テレポートポイントはcucumberの上にしか置かなかったとしても問題なさそうなのでそうする

普通にやれば、水をやる順番に進めたいところだが、そうするとどのcucumberの上に置いたか記憶するので2^50とかになるので無理

とすると、x座標で左から順にテレポートを置いていくとか考えるわけです

前にテレポートを置いた場所をptelとすると、現在の位置ctelに置いたとき、ptel~ctel間のcucumberはどんな距離を加算すれば良いでしょう

この辺で整理できなくなって時間切れになってしまった


後で

ptel~ctelの間にcucumber iがあったとき、次に水をやるcucumber i+1との距離と、前に水をやったcucumber i-1との距離をそれぞれ加算する

しかし、このとき基本的に最寄りのテレポートを経由して行くことにする。

ただし、i-1(またはi+1)がptel~ctelの間にあるときは、直接歩いたほうが早いかもしれない。

なので、その時は早いほうを採用する。

なお、i-1(またはi+1)がptel~ctelの間にないときは、必ずテレポートを経由して行っても直接歩くより時間がかかることはない。

(同じテレポートから出てくることも可能なため)

ということでDPが書けるので書く

かなり書くのしんどい


上位の人が軒並み200点台の中で、Petr見たら370点とかだった

アルゴリズム力もさることながら、ややこしいコードを素早く書く能力がずば抜けている・・・

Petr伝説


ソースコード

続きを読む

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

2012-04-20SRM540 Div1

  • 250:158.27(-50), 550:Compiled, score:108.27, rank:283, rating:2193(-31)
  • 相変わらず成績が不安定。こんな点数でよくこの程度の被害で済んだもんだ・・・

SRM540 Div1 250 ImportantSequence

| 16:55 | SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1つ決めると後は全部決まるのはすぐ分かったけど、それでどうすればいんだっけ・・

+がなければ明らかに上限がなくて解が無限にあるから、+のところで区間を区切って考えるのかなあ

何となく+のところで区切った区間ごとに上限と下限を出してみようとしてみる

区間同士はどうやって結合すればいいんだ・・・

あー、実は+のところは上限と下限を反転するだけなのか

じゃあ、区間ごとに区切らなくても、左端の要素から右へ順番になぞって、上限と下限を段々狭めていけばいいのか

書いた

時間かかりすぎた。提出。

あー部分的に0を返す判定が抜けてる・・まあ最後にも判定してるから大丈夫かな。。


チャレンジフェーズで勘違いしてオーバーフローしそうだと思ったけどしなかったんで-50点くらってしまった

ちゃんと見てから投げよう・・・


ソースコード

続きを読む

KelisKelis2012/11/15 02:30Me and this atircle, sitting in a tree, L-E-A-R-N-I-N-G!

vsolmndcevsolmndce2012/11/15 12:352t3kuC <a href="http://jkxotjkfkoqx.com/">jkxotjkfkoqx</a>

lzxslcbfdclzxslcbfdc2012/11/16 11:02lsMjkV , [url=http://pswxdpjynsds.com/]pswxdpjynsds[/url], [link=http://dfyzalsrkwwt.com/]dfyzalsrkwwt[/link], http://rcymvzaqhavf.com/

hzezocyuybrhzezocyuybr2012/11/17 21:21SC9H6Q , [url=http://pczvhtfxmuwm.com/]pczvhtfxmuwm[/url], [link=http://zqyfpyiuonso.com/]zqyfpyiuonso[/link], http://nudkivwjzsgg.com/

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

2012-04-01TCO2012 Round1A

  • 250:225.46(+100), 500:423.12(+50), 1000:598.70, score:1397.28, rank:4, rating:2224(+160)
  • なぜか高順位+TCOご祝儀相場でボロ儲けw

TCO2012 Round1A 250 EllysJuice

| 16:30 | TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

予選にしては問題めんどくさああ

制約が小さいのでnext_permutationでナイーブにシミュレーションした

シミュレーションを省略するとよく間違えるので、本当にナイーブにシミュレーションした

提出

書くの遅っ と思ったら誰も出してなかった

みんな同様に律儀にシミュレーション書いていたみたい


チャレンジフェーズ

sortせずにnext_permutationしてる人を2人落とした

実は最後の返り値をsortしてない人も2人いたらしい。気づかなかった・・・


後で

シミュレーションしなくても、2回以上名前が出てくる人は必ず勝てる

オレンジとリンゴを50%ずつ取れば必ず勝てるので。後の人はどんなに頑張っても残りを全部取れるわけではないので、負ける

ただし一人しかいない場合に注意


ソースコード

ナイーブなシミュレーション

続きを読む

TCO2012 Round1A 500 EllysFractions

| 16:30 | TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

分母と分子は互いに素なわけだから、同じ素因数を持つことができない

ということは、これまでに出てきた全ての素因数を2つに分けるだけの問題

ただし分母>分子の制約があるので、最後に2で割る必要がある

2つに分けるっていったって、同じ素因数は全部同じ側に入れるので、2^(素因数の種類数)するだけである

素因数分解してsetに突っ込んでいくコードを書いた

提出


チャレンジフェーズ

2^(素因数の種類数)を32bitで計算している人がいたので撃墜


後で

実は素因数分解はする必要がなかった

2つ以上に分解できる場合は、必ず既にその素因数が登場しているはずなので、素数かどうかだけを判定すれば良い


ソースコード

素因数分解しているコード

続きを読む

TCO2012 Round1A 1000 EllysLights

| 16:30 | TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1つのライトにつながるスイッチが最大2個っていうのがポイントだな

2個っていかにも2-SATっぽい

うーん

何か違う気もするなあ


というか、以前こんな感じの問題解いたことあるような・・・

(後で確認したら、SRM496 Div1 500 OneDimensionalBalls だった)

スイッチが2個しかないので、一つのスイッチを使うと、芋づる式に連結する他のスイッチのON/OFFが決まる

連結してるのは全部ひとまとまりで考えていいので、実は1つの連結成分ずつON/OFFを決めていけば状態数がすごく少ない

ということは適当にメモ化再帰すればいいんじゃないか


と思ったけどループするから再帰とか面倒くさい

BFSで書けばいいや・・・


書いた

うーん連結成分とか完全に無視して、前から1ビットずつ決める書き方にしちゃったけど大丈夫かなこれ・・

とりあえずサンプルは一瞬で答え出るので提出


ランダムな入力とか、全部のスイッチが連結している入力とか、色々試す

特に問題ない。一番やばそうなのでも手元で100ms以下。


チャレンジフェーズ

赤い人2人から合計3回もチャレンジ受けるが生き残る

ハニーポット状態になってしまった


システムテスト

通った。後でプラクティスで確認したらarenaでは最大で10msもかかっていない。


ソースコード

しかしこの書き方してる人、自分以外に見なかったのだが・・・

なぜだろう(一見TLEっぽいから?)

他の人はdfsしてたりunion-findしてたり色々

続きを読む

PutuPutu2012/11/14 17:34We've avrried at the end of the line and I have what I need!

qugzuwvdqugzuwvd2012/11/15 12:09hsO2Bf <a href="http://sgnsqmlhqiaa.com/">sgnsqmlhqiaa</a>

sbgfuadwnunsbgfuadwnun2012/11/17 11:17uDRxYO <a href="http://swfgvcnqwgxp.com/">swfgvcnqwgxp</a>

ppmzklppmzkl2012/11/17 20:51kG1Uk0 , [url=http://ybtvmgzaihcg.com/]ybtvmgzaihcg[/url], [link=http://hfpczhabiicm.com/]hfpczhabiicm[/link], http://gqoxvctjnvhq.com/

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