Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

2012-03-21SRM538 Div1

  • 250:239.04, 450:265.45, 1000:Opened, score:504.49, rank:137, rating:2064(+25)
  • ようやく下げ止まってちょっと回復・・・

SRM538 Div1 250 EvenRoute

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

Problem Statement

コーディングフェーズ

チェッカーボードで同じ色の間を移動するのなら、どんな経路を通っても偶数ステップになるんじゃないか

逆に違う色の間を移動するのなら、どんな経路を通っても奇数ステップになるんじゃないか

正しいっぽい

ということは原点と最後に訪れる点だけ決めればパリティが決まるし、どんな経路を通ってもいいのだから全ての点を通ってきたとすればいい

各点の原点からのマンハッタン距離のパリティを調べれば終わり

久々に結構すぐ解けた


ソースコード

続きを読む

SRM538 Div1 450 TurtleSpy

| 20:26 | SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

直感的には、forwardとbackwardは全部結合して、forwardとbackwardの間に最適な角度を差し込めばいいように思われる

本当かな・・まあ450だし書いてみよう

適当なDPを書く

意外と時間がかかってしまった・・・実装力低すぎる・・・

とりあえずサンプル通ったんで提出

しかしアルゴリズム的に楽勝すぎる。本当に大丈夫か。これじゃあ450っていうより300くらいのような・・

forwardしてbackwardしてまたforwardするのがいいようなパターンはないのか

  • 一回目のforwardのベクトルとbackwardのベクトルを足すと、新たなベクトルができる。
  • 二回目のforwardのベクトルの方向が、一回目のforwardのベクトルと新たなベクトルの間に入るようにできれば、forwardを分割したほうがいい
  • どうやら検討してみると、そのような二回目のforwardを作れる回転があるなら、backwardする前に使ったほうがいい結果になるっぽい

なんだ。つまらない。しかし解くよりも証明するほうが大変そうな気がする。チキンレース気味だな。


ソースコード

続きを読む

EsmeEsme2012/11/15 09:54Fell out of bed feeling down. This has brihgtened my day!

dfcfxtaudfcfxtau2012/11/17 05:21FAXLCr , [url=http://nigkynubluqk.com/]nigkynubluqk[/url], [link=http://sdzcawuwyqac.com/]sdzcawuwyqac[/link], http://eralavivvuvl.com/

fsakkadkfsakkadk2012/11/17 21:48Ln0gXw , [url=http://vgjurqseohhr.com/]vgjurqseohhr[/url], [link=http://gcpmrqxsqmmm.com/]gcpmrqxsqmmm[/link], http://mlzyuaxtrdqy.com/

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

2012-03-17SRM537 Div1

  • 275:171.21, 500:Opened, score:171.21, rank:473, rating:2039(-65)
  • ダメすぎてどうしようもない

SRM537 Div1 275 KingXNewCurrency

| 03:57 | SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

よく分からんがmax(A, B)までの数iを候補として、適当にlcm(X, i)までの数で問題ないかチェックすればいいだろう

というのが正しそうかどうかを検討するのに20分くらい要した


後で

そもそもAとBをXとiで表せなければダメだし、逆にそれができれば他の数も全部表せるので、そのチェックだけで良かった

相変わらず不要な検討ばかりして時間がもったいない。。。


ソースコード

続きを読む

SRM537 Div1 500 KingXMagicSpells

| 03:57 | SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

期待値ってことは、また線形性か

XORだとビット毎に変化するので、ビット毎にそのビットが立つ確率を計算して、後で足しあわせればいいだろう

と思ったけど最大10億だったら無理か(←無理でない。30ビットしかない。)


うーん分からん。DPか。

DPも無理ぽい。お手上げ・・・


後で

チャレンジフェーズでようやく30ビットしかないことに気づいた

頭悪すぎる・・


ソースコード

続きを読む

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

2012-03-10SRM536 Div1

  • 250:230.35, 500:WA, 1000:Opened, score:230.35, rank:364, rating:2104(-68)
  • MediumとHardがうまくいかず、Easyスピード勝負+チャレンジ勝負みたいな回になってしまった
  • 色々歯車が合わず消化不良気味・・・

SRM536 Div1 250 MergersDivOne

| 11:45 | SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

一瞬DPかと思ってちょっと時間を無駄にしてしまった

しかしよく見るとどう見ても小さい方から2つずつくっつけていけば最適っぽい

こういうGreedyなのって急ぐとろくなことがない。落ちる可能性が高い。

少し考えてみるが、反例が思いつかない。大丈夫な気がする。

提出。

プログラミングというより数学の問題ですね


ソースコード

続きを読む

SRM536 Div1 500 RollingDiceDivOne

| 11:45 | SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん分からん

しかし値が大きすぎるので、一発で求める系の可能性は高いよなあ・・

大まかに言えば、1+面数を足しあわせて2で割れば期待値になるんでそれに近い値っぽい

なぜか2と2とか、2と3とかで検討して、2以上離れた数字の組み合わせを全く考えなかったので、上の考えでそのまま提出してしまった。酷い

当然Challenged


後で

サイコロ2つで考えてみる。2と4のサイコロだと、縦軸を2の方の目、横軸を4の方の目とすると以下みたいな平面で合計値の組み合わせを表せる

2 3 4 5
3 4 5 6

見ての通り、斜めに切ると同じ数字が出てくる

サイコロ3つだと直方体の形で、斜めの面が全て同じ数字になる

4次元以上は人間の頭では想像できないが、同じような感じ


2と4のサイコロの例で考えてみると、3~5が2つずつ出てくるので、解は3である

3という数字は、上に書いた平面で短い順に辺を辿っていったときに、最後から2番目の角の数字である

3~5までは、斜めにスライスしたら同じ長さなので、同じ数だけ数字が出てくる

条件を整理すると、最後から2番目の角に来るまでに辿ってきた数字の数(2つ)が、最後の辺の数字の数(4つ)以下であれば、その数字が解になる

別の言い方をすると、一番大きい数字(6)から、逆方向に順に短い辺を辿って、最後から2番目の角(5)に来た時に、前から順に辿った最後から2番目の角(3)以上であればいいということになる


逆にその条件を満たさないときは、前からと後ろからで最後から2番目の角の値の中間が解になるはず

(この2つの間では、スライスした面が一度大きくなり、また小さくなるはずだから)


ソースコード

以上の考え方でプラクティス通った

他の人を見ると色々考え方があるみたいですね。

続きを読む

SRM536 Div1 1000 BinaryPolynomialDivOne

| 11:45 | SRM536 Div1 1000 BinaryPolynomialDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM536 Div1 1000 BinaryPolynomialDivOne - SRM diary(Sigmar) SRM536 Div1 1000 BinaryPolynomialDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

値が大きすぎてどう見てもbinary methodとしか思えない

binary methodを再帰的に計算する場合、AやBを多項式として、A^2と、A*Bみたいなものの2種類の計算が出てくる

ところでA^2って、展開して、ある項kに着目すると、Σ(A[n]*A[k-n])みたいな係数の計算になる

ということは、A[n]*A[k-n]+A[k-n]*A[n]みたいに順序を入れ替えたものが出てくるので、A[k/2]*A[k/2]を除いて全て2の倍数である

なのでA[k/2]*A[k/2]以外の計算は無視できる


あとは、、A*Bになるところの計算が問題・・・

A*Bの片方は、元の配列aなので、最大50しか項がない

じゃあ50通りだけ係数を計算すればOKか

といっても50通りも計算したら、毎回50分岐して無理すぎる


うーん


いや違う

50分岐といっても、連続した50個の区間である

段々kを1/2していくのだから、50個くらいであれば同じ値に収束していくはずだ

ということは、メモ化すれば全然楽勝っぽい


残り15分くらいある。書ける気がする

書いた

合わない

結構悩む

ifの中に外側と同じ変数が定義してあった。ミスった。最悪。直した

まだメモ化の部分書いてない。

make_pairとかちまちま書いてたらコーディングフェーズが終わっていた

1分くらい間に合わなかった。

マクロは使わない主義だけど、今回だけはマクロが使いたくなった・・・


ソースコード

特に修正せずプラクティス通りました。もったいな・・

こっちのほうがMediumより簡単だった気がする

続きを読む

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