Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-20SRM543 Div1

  • 250:190.76, 500:Opened(+50), score:240.76, rank:168, rating:2301(-11)
  • 500解けなかったのは猛省

SRM543 Div1 250 EllysXors

| 19:29 | SRM543 Div1 250 EllysXors - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM543 Div1 250 EllysXors - SRM diary(Sigmar) SRM543 Div1 250 EllysXors - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

異様に速い提出者がいて若干ライブラリゲーの様相を呈する

ライブラリは持っていなかったので普通に考えた


0~NまでのXORを単に求める問題に置換する

ビットごとに考える

  • 1ビット目は 0,1,0,1,0,1,0,1,...
  • 2ビット目は 0,0,1,1,0,0,1,1,...
  • 3ビット目は 0,0,0,0,1,1,1,1,...

となるから、xビット目は2^xの周期を持つ

1ビット目は、4で割った余りで場合分けが可能

2ビット目以降は、1周期の1のビット数が2の倍数だから、周期で割った余りだけ調べればいい


書いた

合わない


こまごましたoff by one的な間違いがあった

直した

提出


遅っ・・・!


後で

unsigned intにして、ループで計算して通した人がいたと聞いて驚いた

XORって2秒間に40億回も計算できるのね・・・

計算量の見積もりに精通していれば一瞬で書けるというのは、悪くない問題設定だと思う


ソースコード

提出したバージョン

続きを読む

SRM543 Div1 500 EllysRivers

| 19:30 | SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

明らかに普通のDPは無理だよね


これが船が島のどこからでも(整数の位置でなくても)発着できて、歩くのが一切ないのであれば、単なる光の入射角を決める問題である

高校物理によると光の進む速度によって屈折率が決まり、光が通る道は常にその場所への最短路となるらしい

ということは、光の屈折率を使えば最短路が出せるということである

  • sin(θ1)/sin(θ2)=v1/v2 みたいな感じ

入射角が決まれば、屈折率に従って右端の島のどの位置に着くのかは一意に定まる

そこで、入射角を二分探索することで、目的地に到着するための入射角を決めることができる


walkはどこでやっても同じだから、左端の島だけで歩けばいいんだろう

ということは、どうせwalkの距離に対して到着時間が谷型の関数になるんだろうから、三分探索で出せるんだろう


あとは整数の位置しか港がないから、doubleで計算した港の位置の近くにある適当な港を使って、どれを使えば一番速いか適当に探索すればよさげ


書いてみようとする


・・・


タイムアップ


こんな複雑なの時間内に書けるわけなかった/(^o^)\


チャレンジフェーズ

適当に怪しそうな人にでかいケースをぶつけて+50

たまたま誤差死してくれたみたいで助かった

こんなお茶濁し的なやり方では長くは持たないのでちゃんと問題を解けなければ・・・


後で

Greedyで良かったっていう・・・


どこかで北にlength回進まなければならないので、最初は全ての島で下端にいるとして、1つ北に進むのはどの川 or 歩きを使えば一番速いかっていうのをGreedyにlength回求めるだけだった


DPで計算量が多すぎるときに、部分的にGreedyにしたり、そのために見方を変えるのは常套手段で、今回もそういう意味では典型的なんだけど、全く対応できてない、というか、ちゃんと考えられてない気がする


屈折率による解法でも解けたけど、ちょっと書くのが遅すぎるし、色々いけてなかった。。

まあ高校物理なんて覚えてないんで思い出すのに時間がかかったってのもありますが・・・


ソースコード

せっかくだから屈折率のコードをpracticeに通したので掲載します

港を選ぶ辺りが若干嘘解法っぽいが、lengthの大きさに耐性のある解法だからあながち意味のない考え方でもないかな?

続きを読む

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

2012-05-13TCO2012 Round2B

  • 300:201.68, 550:255.68, 900:Opened, score:457.36, rank:135, rating:2312(+38)
  • 解くのが遅すぎる
  • 後100点くらい足りなかった。精進が必要

TCO2012 Round2B 300 BlurredDartboard

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

Problem Statement

コーディングフェーズ

300とか嫌な予感しかしない

と思ったが珍しくやるだけの予感

見えてる中で最高得点の的と見えない的の平均値で比較していい方を採用する

見えない方は最後の余りは平均でなく小さい方から選ぶことになることに注意する

書いた

例外が発生しました: Integer division by zero

サンプル親切・・・!


直した

合わない

やっぱ300だしこんな単純じゃなかった?/(^o^)\ナンテコッタイ


分からん

デバッガ起動


添字誤りだった

本当につまらないミスが多い・・・


提出


ソースコード

続きを読む

TCO2012 Round2B 550 HeavyBooks

| 17:55 | TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん

一番重いのを押し付けあうとしか思えない

それより軽いのを渡しても得する場面が全く思いつかない


一番重いのを押し付けあうとすると、最初にTomekがどの本を入れるか決めるだけの問題

重い順に見ていけばどちらが持つかは一意に決まるので、重い順に本を採用するかしないかでDPすればOKかな


書こうとする

添字とDPの更新条件式がカオスになる

デバッグで最終的に40分もかかった


提出


ソースコード

DP更新条件式のカオスなところは直しました

今回はpairを使えば比較的ラクに更新ができる気がする

本番でもpairを使っていたのになぜカオスになったんだ・・・

続きを読む

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

2012-05-06Google Code Jam 2012 Round 1A

  • A-small/A-Large:Passed, B-small/B-Large:Passed, score:53, penalty(time):1:08:08, rank:319
  • 遅すぎる・・・Round2通過するレベルの目安としては少なくともペナルティは50分以内にしたかった
  • Cが難しかったです

Google Code Jam 2012 Round 1A A Password Problem

| 20:30 | Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

最初のi個が連続して正しい確率を求めて、何個バックスペースを使うと最も期待値が小さいか調べて、その最小値を返すだけ

なんだけど、色々こまごました式で混乱してしまって20分くらい使ってしまった

終わっとる・・・


ソースコード

続きを読む

Google Code Jam 2012 Round 1A B Kingdom Rush

| 20:30 | Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

なぜか1-starクリアの数で二分探索なんじゃないかと思ってしまった

いやいや、そもそも上限1000で二分探索なんか普通いらんし・・・

というか何で二分探索なんだ。どの面を1-starに選ぶか決められないとそんな手法取れないし

逆にそれが決められるなら二分探索いらない気がする


もう一度落ち着いて考える

ある状態で2-starに行ける面があるなら、常に取ってしまっていい

ある状態で1-starしか行けないとき、どの面を選ぶかが問題になる

1-starの必要star数を満たしていないものは当然除外する

1-starの必要star数を満たすものの中で、2-starの必要star数が小さいものを残しておいたほうが、総合的に1-starクリア数を減らせるんじゃないか

これで行けば、Greedyでいいことになる


問題文中のサンプルの進め方と異なるが、本当に正しいか。

(1-starの必要star数,2-starの必要star数)という表現で具体的な例を考える

(0,1)と(0,3)があったとする

  • (0,1)からクリアすると、(0,1),(0,1),(0,3),(0,3)の順で合計4回クリアする必要がある
  • (0,3)からクリアすると、(0,3),(0,1),(0,3)の順で合計3回クリアでいける

どちらの1-starを取っても、2-starの必要star数は変わらないし、もらえるstar数も変わらない

だったら、なるべく早い時点で2-starが取れる可能性のある方を残しておいたほうが得に決まっている

やはり正しそうだな

サンプルはたまたまどちらから進めても同じ結果になる例なだけっぽい


とりあえずできたが無駄に時間がかかった。最悪・・・


ソースコード

続きを読む

Google Code Jam 2012 Round 1A C Cruise Control

| 20:30 | Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

全然解答方針が思い浮かばない、かつBまでで通過した気がしたのでイマイチやる気が出なかった・・・


といいつつ、1時間後くらいに何か二部グラフかどうかの判定をすればいいんじゃないかという気がしたので色々考えてみる

左右のレーンを二部グラフに見立てる

前後5m以内にいる2台を、連結しているノードとみなす

そうすると、このグラフは当然二部グラフでなければならないはずだ

追いつきや抜き去りの発生する全ての時刻で、このような判定をする


何かそれが全てのような気がしてきた

書いた

サンプルの最後が通らない

レーンが固定されているはずの人が、入れ替わったりすることが可能になってしまっている

レーンが固定されているか、入れ替え可能かを判定しつつ二部グラフの判定を行う必要があった


書きなおす

サンプル通った

提出

Wrong Answer


時間切れ

終了


後で

グラフの連結解除をするタイミングが誤っていた

単に抜き去りきっただけで連結を解除してはいけない

その時点で他の人と並走していると、レーンを動かせないので、連結状態が続くとみなさないと状態が崩れる

誰とも並走しなくなった時点で、全ての連結を解除するのが正しい


追いつくタイミングと抜き去るタイミングが混ざっていた

ある時刻tで追いつきと抜き去りの両方が発生する場合、まずは抜き去りだけが完了したとみなして連結の判定をしなければならなかった

追いつきも同時に発生させてしまうと、本来レーン変更が可能なはずなのにできなくなってしまう


他にも細かい間違いがいっぱい

全然だめでした

難しい・・・


ちなみにこの解法は、本質的にはanalysisと同じことをやっています

上位2名の解答を見ましたが、やはり本質的には同様の解法でした

しかし書き方が上手で、うまいこと問題が起きないようにコードが書かれています。短時間ですごい・・・


ソースコード

修正してpractice(Large)に通るバージョン

続きを読む

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

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