Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
|

2011-12-24

Codeforces Beta Round #99 Div. 2

00:32

久々に参加してみたところひどい記録になりました。

o opened o opened x : 1830 pts. 147th. Div. 2であることを考慮するとひどすぎです。主に読み間違いがひどい。

A

ループしながら引き算。愚直に n -= a[i % 7] しました。一週全部で読める量を調べたりすると罠にハマるそうです。具体的にはp週間でぴったり読み終わる場合に7じゃなくて1と出したりする。

B

問題の英語が難しい。

各部屋に最安の壁紙を割り当てるだけでした。が、以下の場所を読み間違えます。

And pieces of the same roll cannot be used to paper different rooms. That is, for each room the rolls are purchased separately.

壁紙の切れ端を別の部屋の壁紙にしないでね、という話です。これを、rollをtypeと読み間違えて、同じ壁紙を複数の部屋に使わないでね、と読んでしまいました。あっという間に最小コスト2部グラフマッチのできあがりです。手元にライブラリが無いのでスルーしてしまいました。

C

やるだけです。韻を踏むだけの母音がない場合に注意しましょう。

D

105桁まで、を105まで、と勘違いして全く通りませんでした。TLEではなくint32 overflowかなにかしていた模様です。正しくは

  • 足して10になるものがなければ、0の数が答え。そうでなければ以下。
  • 1の位になりうるもののうち、0を用いない5通りについて以下を試し、最大の値を返す。
    • 10以上の位になりうる組み合わせの総数を数える。
    • 余った0があれば下の位に集める。

こんなところでしょうか。49060 + 60940 みたいなので落としていてもおかしくは無いです。


E

一次元上に得点源がばらまかれていて、ある確率である範囲の得点源がお釈迦になります。その際の得点の総和の期待値はいくつでしょう。

N(得点源の数) * M (区間の数) をやるとTLEしそうなので注意して、端から順に見ていくだけでO( (N + M) log (N + M) )で解けるなと思いつつ解いていましたがTLE。区間同士が非常に重なり合っている場合に、それすべてを毎得点源について掛け算しているのでO(N * M)かかっていました。

  • 総和を覚えておく時みたいに、掛け算の結果を保持して、区間の出入りの際に差し引きする。
  • 確率100 % で死滅する、という入力が来る。これをそのままかけてしまうと、掛け算の結果は0になってしまい、その区間を抜けても元の確率は復旧しない。0を直接かけず、0が掛かった回数を覚えておくことでそれを回避。
  • 区間の数が10 ^ 5あるので、普通に掛けるとアンダーフローしうる。logを保持する方が無難。

コンテスト終了後に、全部をやって通りました。

2011-05-09SRM 505

x opened opened: 0 pts.

半数が0点という恐ろしいsetでした。

1時間前

久々にSRMうけようと、macbook proでArenaを起動。したところpluginがmacbook proで動かないことが判明。慌ててdebianに移行。おそらくMacJavaの問題だと考えています。

300

長方形が不規則な長さの碁盤目に区切られている。区切られた部分長方形いくつかの面積が分かっている。あといくつ分かれば長方形全体の面積が求まるか。

ある4つの長方形 @ (x1, y1), (x1, y2), (x2, y2), (x2, y1) のうち、3箇所が分かっていれば残りはわかります。

規則性は判然としなかったので、とりあえずまだ分かっていないところを順番に調べればよいのではないかとあたりを付けて解きました。オーダーはO(格子の数^2)程度。結果xx分。ある場所の面積が判明したあとに、それによって新たに別の箇所の面積が判明するようなケースに気づかずちょっと手間取りました。最大入力で帰ってくることだけ確かめてsubmit。

しかしsystest failed。塗る順番をちゃんと考えないと行けないようでした。正解の方法は確認しましたがまだ本番のアルゴリズムの反例が理解できていません。

500

整数集合S = [A--B] + [C--D]のうち、Sに自分の倍数が含まれていないSの部分集合のサイズを求めよ。各変数は最大10 Billionまで伸びるので注意。

まずA--BのうちA--B自身に倍数を含むもの、C--Dのうち倍数を含むもの含まないものを求めておきます。そのあと、[A--B]のうち、[C--D]の中に倍数を含んでいないものを数えます。

[C--D]の約数は、, [C/4--D/4], [C/3--D/3], [C/2--D/2]といった分布をしています。ただし互いにoverlap擦る可能性はあります。まあとりあえずこの範囲を端から順に調べます。tsukunoさんとは逆に大きい方つまり分母の少ない方から探しました。

が、エラーでサンプルが合わずに時間切れ。1ずれていたので当時はどこかでoff-by-oneと思っていました。

あとでpracticeしてみたところ、C--Dの幅が狭いところでの処理が全く正しくないことが分かりました。それを訂正すると今度はTLE。具体的には[C--D]が狭く、ある数の倍数がその中に一つもないときに、そのままもう倍数ないよと探索を放棄していました。分母を増やして最挑戦するのが正解。

1000

与えられた整数集合を、和と積が等しくなるよう変形せよ。

見ただけ。

あとで、和と積とが等しくなるような集合のリストを手元で生成してみました。結果、サイズ50までにはバリエーションが多いので全列挙埋込みはあまりかしくこないかもしれないことを確認しました。いややり方はあると思いますが。

2010-05-05

! SRM 469

o o opened: 470.47 pts. 66 th

  • 250 208.52 pts 13分
  • 500 261.95 pts 34分
  • 1000 opened

最近にしてはよかったです。

特に500が、あまり早くなかったものの、落としている人が多い中確実に取れたので結果オーライ。

500

500から開いてみました。250を後攻することで、その必要時間を見極めてみるつもり。

  • え、これどうするの。
  • ある組み合わせの映画が見れたら、残り時間はその見る順序を問わず定まる。なので、その組み合わせの映画が見れるとしたら、見る順序は一つだけ保存しておけばいい。
  • でもどうすれば。よくわからないから250に逃げようかな。
  • なるほど。高々20枚だからO(220) の空間でできます。よし解ける。
  • 残り時間を表す変数にlifeと付ける。
  • できた。30分かかってない。最近にしては上出来かも。
  • あれ、operator<<(ostream&, vector)でエラーがおきている。
    • cout.hとテンプレート(vectorを出力)とによる二重定義。とりあえずcout.hを外す。
  • テストケースはpass.
  • 最大ケースで3 secかかる。これはまずい。
  • 計算量はO(N 2N)でぎりぎりだった。これはまずい。
  • とりあえずpprof。std::_Rb_treeが原因。メモの部分をmapでやっていたので。
  • 時間を半分にできればいいのだからmapをhash_mapにできればよいはず。
    • 何か間違えたかな。/usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated.
  • よく考えたらvectorで良かった。これで最大ケースが300 msでpass. submit.

BFSで見られる映画の組み合わせを探索します。上記したとおり、ある組み合わせの映画を見る順番は一つだけ保存していればよいです。自然な順番で探索するとはじめに見付かった手順が辞書順最小になるため、そのときの手順だけ保存しておきます。N個の映画に対してノードが2N存在し、一つのノードにつきO(N)の次の手を探すのでO(N 2N)の時間がかかります。ぎりぎりの時間で解けます。

変数lifeはsanの方が良かったかもしれません。

実はO(N4)でできるとか。 なん...だと...

250 pts

  • 映画館の座席のうち、並んで座れるところの個数を返す。ただし映画館が異常に広い。
  • 座席をソートして前から順番になめて、間の個数を返してみる。
  • N * M は掛ける前にcast。
  • 面倒くさいな。
  • できた。submit.

1000 pts

  • open.時間はちょっとあるしなんとかしてみるか。少なくとも考えてみる。
  • O(247)とか無理ですね。どうすればいいんだ。
  • 半分に分けるとできるのかしら。でもどうやって。
  • 以前の半分に分ける方法はなんだっけ。PARTITIONか。全然違うな。
  • 無理。

challenge

500のTLEだけ準備したものの、TLEしそうなものが見つかりませんでした。ただ他の人が次々と撃墜されています。何がおきているのか。

250がかなり遅かったので他の人の解法を確認。全体から座れない席を引く方が早いですね。

system test

同じ部屋で四件も落ちていました。これはもったいない。

反省

  • 250はもうすこし俯瞰すれば早くなるかも。慣れか。
  • テンプレートを直す。
  • hash_mapを使う。
  • やはり250から解く方が迷いがなくて楽かも。

challenge resultsの確認。

どうやってchallenge phaseを得点源にするかについて、他の人の撃墜例を見て勉強します。

まずは自分の部屋から。

TLEを投げている人は2勝3負+25でなぜか微妙。ちょっとはコードを読んだ方がいいのでしょうか。+50と-25とのバランスを考えると相手を見ないでchallengeぶっぱなしてもいいと思っていましたが。例えば今回の場合、tree/mapを使っている人は撃墜対象でしたね。他は読まないとわからない。

250は実装のときに気づいてたけどchallengeのときに忘れていたものの一つです。

ついでにsystem test failedのソースも見てみました。これらは本当にバグっていました。コードは読みにくいしちょっと見つからないし見つける方向ではないと思います。残り6分とかだったら時間かけて見てもいいのかもしれませんが。

さらに他の先生の撃墜も見てみます。

[[iwi]]先生の部屋。この入力はどうやって作ったのでしょう。撃墜された人はTLEじゃなくてWAで落ちてるし。何か他のバグかしら。あるいは単に適度なランダム例で、それがTLEじゃなくてそれ以前のケースで落ちてしまったとかかもしれません。うーん。

さらに見ていった結果。

  • 250は幅1の例で撃墜している例も。
  • 500の残りライフ0生存で落ちている人とかは見あたらない。見つけにくいし。

難しい。結論はありません。

2010-05-02

! topcoder open qualification round.

5/5に書いています。

oox 488.82 pts 372位.

  • 250 238.94 pts
  • 500 249.88 pts

500の解法が酷いものでした。

500

12:46

  • 500から開く。
  • ロボットの動きをシミュレートして踏んだ升目を数える。ただし動きの列が周期であたえられて非常に長くなる。
  • 基本は一周期で踏む升目の数 x 周期数。ただし同じ場所を踏むところが出てくるので、それを検出してマージすればよい。
    • まず、周期一つこなすごとに固定した幅だけずれる。そのずれをdiff.x/yとおく。
    • 一周期したときの升目を二つ取ってきて、それらの位置関係がdiffの整数倍なら、同じところを踏むことを考慮して踏む個数を調整。
  • あれ、diff_x/yが0のときに面倒だな。こうやってこうやって。
  • あれ、はじめの何ループかはこれでは上手く解けないな。ループが少ないときは重ならない、というケースが存在するのか。
    • 10ループまでは展開して解くだけにしておこう。
    • この撃墜例を持っておこう。"ULLDDDRRRU" x 2.
  • なんとかできた。

250

12:46

  • bubble sortの交換回数 = 逆転の個数. 6分で撃破。

1000

12:46

二分探索で、あとでたらめな数が来るからオーバーフローを全て無視するようにする。

途中で意識が飛びかけて、二分探索が v 以下の数字の個数を探すのかv未満の数字の個数なのかわからなくなるほど意識レベルが低下。未完。

challenge

12:46

  • よーし500撃墜しちゃうぞ。
  • あ、あれ...
  • 500は始めループ回して、あとは増加数一定だからその分を実験的に求めてかけ算すれば終わりなのか。無駄に苦労してしまった。ついでに撃墜例はこれでは役に立たない。

感想

12:46

500で謎の混迷.

2010-04-20

SRM 468

23:29

x o opened : 383.22 pts.

  • 250 148.27 pts
  • 500 234.95 pts
  • 1000 opened. 読んでない。

出張から帰宅してすぐ参加するなど。

軽微なミスの連発とそこからの遅い復帰速度。

250

やるだけ。ただし辞書に単語がないことを考慮せず、ミスしているとsegfaultで即死するようなプログラムを作ってしまう。

  • off-by-one で233を23にする。
  • つなげてからparseするはずが、parseしてから繋げてしまう。
  • 提出。28分もかかった。

500

Nが大きいので、O(N2)もの時間を掛けないようにする。

  • Kをoff-by-oneして(K回飛んではいけないと思っていた)いろいろsegfault。
  • valgrindの使いかたを調べる。
  • 発見。
  • 提出。45分。

1000

読んでない。

Challenge

みつからなかった。

部屋には少しだけ撃墜されたプログラムがいた。250で'1'に文字がわりあてられると困るものなど。

感想

正直難しくないのでもうすこしできてもいいと思う。練習がたりない。具体的にはtopcoder templateの練度が低い。