Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2010-01-21

SRM459

06:50 | SRM459 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM459 - tanakhの日記 SRM459 - tanakhの日記 のブックマークコメント

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=14145&rm=303346

ついにレッドコーダーになれました!!

http://www.topcoder.com/tc?module=MemberProfile&cr=22627322

私のグラフにも赤の帯が…。

挑戦すること59回目、登録からちょうど三年半、レートががた落ちする度に何度も諦めそうになりましたが(グラフを見た感じでは4回ほどですね)、ついにひとつの壁を超えることができました。今回も2100台にのってから、なかなか2200の壁が越せなくて、リーチが掛かってから半年ほど上がったり下がったりを繰り返していましたが、完全に心が折れてしまうほどの激減がなかったのが今回の勝因だと思います。

そのために、去年あたりから、ミスを徹底的になくすと言うのを心がけていて、問題文をしっかりよむというのと、ちゃんとコーナーケースをチェックするというのを基本ですけど、意識して気を付けることにしていました。問題文を読むのは、私はTopCoderを始めた頃は英語を読むのがすごく苦手で、ICPCでも問題読みは全くやってなかったので、一問あたりゆうに10分は掛かっていたのですが、流石に59回も参加してますと177問もの問題を読んだことになるので、最近は2,3分もあれば大抵の問題は理解できるようになってきました。それで、細かいところまで読む余裕が出てきたと言うのがあります。コーナーケースは、最近の問題は入力が親切なことも多いですが、やはり一通りは入力を作らないといけません。最大ケースと、境界のケースと、あと、テスト入力で仕様が網羅されてないときなど。これは自分のサブミットを守ることに加えて、考えた入力がそのまま撃墜ケースに使えるので、結構得点に貢献したと思います。あとは、昔は時間が余ったら1000をずっと考えていたのですが、最近は無理っぽいと思ったらさっぱりと1000を無視することにしています。250と500のソースを穴が開くほど繰り返し読んだり、何度もテストしたりする方が、悔しいですが私のようなレベルにいるものには有意義だとようやく気づきました。

そんなわけで、こんな私でも諦めずに頑張ればレッドコーダーになれると言うことが示せたので、少しでも他の皆様への勇気付けになればとおもいます。今後は、ひとまずは維持したいと思います。ずっとレートを上げていきたいものですが、とりあえず短期的には2500ぐらいで安定するのを目標に頑張りたいと思います。

250 221.99 AC

Xに関する不等式が50個以下与えられるので、これらの部分集合のうち解を持つもので、最大のもののサイズを求めよ。

定数が0~1000までしかないとのことなので、-0.5~1000.5まで0.5刻みで調べれば十分。最初問題を読み違えていたので、ちょっと時間をロスした。doubleを使うと、0.5刻みだと誤差がでないことは分かっているのだが、なにかがまかり間違って落ちたら嫌なので、二倍にしてintで計算。何か少しでも不安なときに、少し手間がかかっても絶対安全の方に倒すのは悪いことではないと思う。

500 225.28 AC

パスカルの三角形のようなルールで数列を足して行く時、トップの数がtopになるような長さNの数列は何通りあるか?

全部試す自明な解法だとtop^Nだなあ、どうするか。あれ、サンプルの二つ目を見るに、これはどう見てもtop>2^(N-1)の時は解がない。ということは、結局N<=20程度を考えればいいということだ。とはいえまだ、だからどうするんだという段階。パスカルの三角形を考えるに、これはΣai*nCi=topを満たすAiの数を数えればいいのだろう。しかしどうするのか?前から順に埋めていくDPなら、top^2*Nで計算できるな。現実的な計算量が見えてきた。しかしもう少しのところで捕まえられない。三角形を上から埋めるようなDPはできないか?左右の子の山を独立して計算して、うまく制約をつけられないか?うーん、全然だめだ。というか、できたところで、各ノードの値をO(1)でまとめる方法が思いつかない。やっぱりさっきの方法を改良するべきか。しばしさらに黙考するもアイデアが出てこないので、とりあえずtop^2*Nの解法を実装してみる。サンプルは通った。しかし、最大ケースを入れると全く帰ってこない。さらに悪いことに、向こうのテスターだとbad_allocで落ちる。DPのテーブルはどう考えてもtop*N個は必要なので、これは配列を順になめて2つを使いまわすような、つまり、普段私が書いているメモつき再帰ではだめだと言うことだ。まったく、めんどくさい話だ。メモつき再帰の本質的に良い点は、ノード間の依存関係を全く考える必要がなくて、とりあえずDAGにさえなってればいいというところで、配列をなめてやる場合は、どういう方向で配列を埋めていくかを考えなければならない。私はTopCoderなら、コードの質よりも考慮するべき事柄が少ないということを優先するのだけども、それを強要されるなら、慣れてないけどやらねばならぬか。オーダを改善する方法が見つからなくて飲み物を飲みすぎたので、トイレに行ったら解法を思いついた。最近SRM中にトイレに行って解法を思いつく率がかなり高い。私がtop^2*Nで想定していたのは、左からi番目以降の和がjになるようなaの埋め方をx[i][j]として、x[i][j]=sum[x[i+1][j-nCi*k]|k<-[1.. のように、ある場所に何を埋めるかのすべての数を試す、のようなものだったが、よくよくも考えると、2以上の数kは1+(k-1)じゃあありませんか。なんでこんな簡単なことに気づくのに20分もかかったのだろうか。というわけなので、1のケースと、2以上のケースの二つを足すだけでよいと言うことになった。x[i][j]=x[i][j-nCi]+x[i+1][j-nCi]で、小さい方から埋めていけばいい。それで、ようやく解けたので、サブミットである。

1000 Opened

記念にOpenしたが、難しそうだったので読んでいない。

Challenge Phase

サンプルデータが親切だったため、何もできない。私の部屋では250が一人落ちただけだった。

反省・感想

なんかTopCoderらしい問題だったなあという印象。500は解くのが遅すぎた。上位の人達はこの程度は一目でアルゴリズムが分かるのだろうけれども、その溝をどうやれば埋められるのだろうか。練習でどうにかなるものなのだろうか。

shinichiro_hshinichiro_h2010/01/22 03:12おめでとうございます!

tanakhtanakh2010/01/23 01:23ありがとうございます!

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100121
 |