Hatena::Grouptopcoder

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

|

2010-03-15

Maximum Winter-Contest 2010

10:03 | Maximum Winter-Contest 2010 - tanakhの日記 を含むブックマーク はてなブックマーク - Maximum Winter-Contest 2010 - tanakhの日記 Maximum Winter-Contest 2010 - tanakhの日記 のブックマークコメント

出てました。

http://m-judge.maximum.vc/standings.cgi?cid=21

下から数えた方が早そうな…。ひどすぎる借金。

A

ナップザックにしか見えないし、サイズも40までなので、

20ずつに分けてそれぞれ全生成にしか見えない。

map<long long, long long> を二つ作って、片方を舐めながらもう片方をlower_boundで探す。

さくっと作るが、答えが合わない。lower_boundの仕様が良く分からない。

結局lower_boundで探してからイテレータを一個戻す。

直ったので送信するがTLE

最適化していると泥沼かなあと思い一旦離れることに。

D

Dが解かれていたのでDに。

問題文に横線が入っていてなんか怪しい。

同一点かどうかは==、

同一直線かどうかは、(a-b)を90度回転したベクトルと(a-c)の内積が0かどうか、

同一円周上かどうかは、外心を二つ求めて同じかどうか。

外心をライブラリからコピペして適当に送信するが、WA。

もうだめぽ…。

C

通している人が多かったのでやってみる。

26C8なら一瞬だろうと、適当に実装。

再帰を書いてしまったけど、どう見てもnext_permutationでOKです。

やっと一問通る。

E

Bを読んで考えるがまったく分からなかったので、Eに移動。

Warshall Floydで最短と最長が求まるはずで、あとは複数ルートの存在確認だけか。

適当に深さ優先でチェックする。

TLEかもしれんなあと送ったらWA。

(※後で考えたら、複数ルートがあっても、特定二点間に複数ルートが有るかどうかは

分からんので駄目なような気がしてきた)

H

操作が可変なので、パッと見両側探索か?

深さの最大値をとりあえずBFSで求めてみると9と出てきた。

ということは4までやればよい。

適当にmap<string, int>をBFSで生成して、ワーストケースが0.5秒ぐらいか。

送ってみるとやっぱりTLE

もうだめぽ…。

G

ソートするだけにしか見えなかったので、怪しかったがどうせすぐできるので送ってみる。

当然のごとくWA。

ここまで6問送って1AC。

おわとる…。

D

なんとかしないと…。

TLEなのをいじりだすと泥沼になりそうな気がしたので、WAをなおす方向で。

一番といてる人が多いDを選択。

同一直線状の判定を、二つのベクトルのなす角が0度かどうかに変更。

同一円周上の判定を、適当な3点の外心からの距離がもうひとつの点への距離と等しい、に変更。

どっちが効いたのか分からないが、ようやくAC

A

高速化のアイデアがいくつか湧いてきていたのでAに。

まず、0から1<<nまでビットパターンを回して生成していたところを再帰で行うように。</ppp>

20*2^20から2^20になるはず。

二分割した集合の両方で解生成するんじゃなくて、

片方だけ生成して、もう片方は生成しながら二分探索することに。

mapをやめてvectorに貯めてsortに。

でも、手元だとmapより遅くなったのでボツ。

(※懇親会にて、そんなことはないという意見多数。-O2付けるのでも忘れていたか?)

いろいろあって、最終的にAC

B

Bに注釈がついてある高さ以上の橋を全部使うという条件が追加されていたので、

問題が大幅に簡単になった。残り時間少ないがとりあえず書いてみる。

すべての塔から移動できる数がs>=なのと、t<=なのはそれぞれ

単純な範囲なので、二分探索二回やるだけなはず。

書き終わって送信するが、もはや当然のごとくWA。

終了

積み残しが4つもあって、どこから手をつけたらいいのか不明だが、

Bは間違っている気がしないし、Gは解いている人が多かったので、

この二つを中心にデバッグを続けるが、結局どちらも通らず。

無念…。

Hを高速化していた方が良かったかもしれない。


結局BとGの問題文に核地雷が埋めてあったということで、見事にそれにはまっていた。

Hは単純に実装がクソだったというのと、Eは普通にアルゴリズム間違ってたのとで、

自分がしょぼすぎて悲しい…。


トップのwataさんが凄すぎて信じられない。

もはや罠の方からよけて通ってるレベルじゃなかろうか。

4時間で全部とは、やばすぎます。

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

2010-02-19

TLE

03:01 | TLE - tanakhの日記 を含むブックマーク はてなブックマーク - TLE - tanakhの日記 TLE - tanakhの日記 のブックマークコメント

http://felicity.iiit.ac.in/tle/judge/index

http://felicity.iiit.ac.in/tle/judge/ranks

密かに参戦。なんだか7位。ゴルフ力を鍛えたい。

PALIN1

(n^n)%p を出力するプログラムを書け。n,p<10^18。ただしプログラムはxを文字列をして (x[1 : (length(x)-1)])(x)(Reverse(x)) のような形をしていること。

n^nとかは普通にやってたらTLEなので、ビットのたってるところだけ書けてlognでやるあれで。入力がでかいのでそのままかけ算できないので、掛け算を足し算で代用。そのままやると遅いので、ビットのたってるところだけ足すあれで。そうすると、累乗と乗算が同じコードになる。やったー、と思ったときは一位でしたが、最終的にはゴルフ負けした。それと、結局このプログラムの形にさせることになんの意味があったのかはわからずじまい。みんな単に二個目以降をコメントにしてるだけで、だれも謎を解けず。想定解を知りたい。

PALIN2

PALIN1と同じだが、n,p<10^5で、プログラムの形がxを文字列として xxx になっていること。値が小さいので線形ループで間に合う。かけ算すると微妙にintをあふれるので途中long longで計算する必要あり。これもまあ普通にいけてるなあと思ったけど、最後にはゴルフ負け。gets()を無引数で渡しても落ちないとか分からない。forループの融合もやってみたけど、とんとんが精一杯でした。この問題も同じコードを三回繰り返すことの意味はわからず。想定解が知りたい。

PREP

プリプロセッサでFizzBuzzを1000まで出力せよという問題。マクロでの改行の入れ方がわからずに、どうすればまともなスコアが出せるんだ、とゆっくり考えると、なんとか#include __FILE__ を思いついたので、ぎりぎりなんとか。#line が式を受け入れられたらもっといろいろできたのになあとか、__LINE__の値が実際に使われるまで遅延されるとか、いろいろなアイデアをことごとく潰され続けた。結局__INCLUDE_LEVEL__とか、__COUNTER__とか、知らんがなという感じの答えがトップでした。もっとプリプロセッサ勉強しないとなあ。

CARM

制限時間内にカーマイケル数をなるべくたくさん出力せよという問題。この問題はトップがずっとダントツで、ずっと方針に自信がもてなかった。まず、小さい方の奇数からカーマイケル数かどうかを全部調べるという方針でやったら、だいたい200個ぐらい出力できて、スコアが0.01ぐらい。完全にだめ。次に、素数の三つ掛け合わせを全列挙して、カーマイケルすうかどうか調べるというのをやるとだいたい1万個ぐらい出せるようになった。これで2-3点ぐらい。どうにもダメなんで、Wikipediaのリンク先とかで調べると、(6k+1)(12k+1)(18k+1)のそれぞれの項が素数ならこれはカーマイケル数だというのがあったので、これにkをいろいろ入れてやると10点近くになった。そのへんで時間切れ。素数判定を素数で割っていくよりも、ミラーラビンテストの方がはやかったのだけど、ふるいで予め素数判定テーブルを作っておく方がはやかった。1億要素で1秒ぐらいで終わる。で、最終的にはそこから3倍ぐらいは高速化された。トップにはまだ3倍ほど差があるが、もっと時間を使って頑張れば追いつけないことはなかったと思う。

COMP

与えられた文字列を出力するプログラムを書け。なるべく短く。

これもまあよくわからないけど、とりあえず圧縮と聞くとLZ77かなと思ったので、LZ77作る。途中アスキーアートが入ってるので、ランレングスでもいいのかなあと思ったが、LZ77でも縮むだろうと。符号化がちょっと悩んで、文字列に含まれない文字種で、かつCの文字列に含めてエスケープが必要ない文字を列挙すると36文字ぐらいあったので、それで24+12ぐらいに分けて、位置と長さをエンコード。イマイチな結果。トップのコードはCの文字列にバイナリを含めたりしているのだけど、バイナリを含める方法がわからなかった。あんまりわからんわからん言っててもあれなのだけども。バイナリ含めるんだったら、大幅に使える文字種が増えたので、だいぶ短くなっていたはずではある。あと、MTFとかエントロピー圧縮もできたのかなあ?

SHORTEN

与えられたプログラムと同じ動作をするプログラムを作れ。なるべく短く。

与えられるプログラムはよく読んでないが、()(()) みたいなかっこのみで構成された文字列が与えられるので、それが左右の対応が取れているかどうか調べるというもの。もとのプログラムはツリーを使ってごちゃごちゃやっていたが、普通に毎回なめるプログラムが通ったので、大幅に短くなる。うほお短くなった、とサブミットしたときは余裕の1位でほくほくだったが、終盤にはやっぱりゴルフ負けする。もうだめぽ…。

KEY

ある数のサブセット(ビットを倒した数の集合)のうち、ビットを左右反転させた時のビットの違いの箇所がp以下の物の数を求めよ。ただし、プログラム中の予約語とか、セミコロンとか、空白に対してすごいペナルティーがかかるので、なるべくそれらを使わないで書くこと。

問題文の難しさが半端ない。三時間ぐらいずっと読んで、結局わからなかった。フォーラム検索して、reverseって書いてあるのが、ずっと01反転だと勘違いしていたことに気づく。なんというわかりづらさ。プログラム自体はすぐ。それで、とりあえずforを潰すためにプログラムを末尾再帰な関数呼び出しに変えて、return書きたくないので、CPSぽくして、とりあえず予約語は全部消したが、なんかあんまり楽しくなかったので、それ以降は手をつけず。

CQUINE

nに対して、それを超えない最大の2^aな数を出力するという問題Aと、それを超える最小の2^aな数を出力するという問題Bがある。プログラムAは、問題Aをとき、かつ、-1が入力されたときはプログラムBを出力する。プログラムBは、問題Bをとき、かつ-1が入力されたときはプログラムAを出力する。プログラムAをサブミットせよ。

山手線クワインとかと同じような感じで、あれ見たとき完全に変態だなあと思ってたのに、まさか自分が書くことになるとは思いもよらなかった。クワインただでさえ苦手なのに、さらにループさせて、ゴルフもしないといけないのは相当厳しいと思われたが、やってみると意外と楽しかった。とりあえずintの変数が0か1かでそれぞれのプログラムを表すことにして、プログラム出力するときにそれを切り替えればいい。あとはひたすらゴルフゴルフで、文字列出力の際にエスケープしたくないから、%と、"を全部消去。%を消去するために文字列をintにしたりした。まあでも所詮はクワイン初心者で、ゴルフもアマチュアレベルなので、トップには遠く及ばず。

まとめ

二日目の最初のあたりまではトップで、あれ、結構いけるんじゃないかなと思ったけど、二日目寝ておきたら7位になってて、もうだめぽな感じだった。ある程度まで短くするのは問題ないのだけど、最後の1バイト2バイトの勝負になってくるともう勝てる気がしない。練習を積むしかないなあ。しかしこういうのは言語仕様の重箱をつつく結構いい勉強になるので楽しかった。今回も知らないテクニックを沢山知ることができた。とくにcppの仕様は今までほとんど気にしたことがなかったので面白かった。来年もあるかもしれないので、それまでゴルフ場でトレーニングすることにする。

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

2010-02-14

SRM461

16:11 | SRM461 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM461 - tanakhの日記 SRM461 - tanakhの日記 のブックマークコメント

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

2209->2200 奇跡的な踏みとどまり

500 Opened

さて始まった。問題をあけようとすると、うわあああ指が滑って500開けてしもた。おわた…。というわけで望まぬ500からのスタート。500は毎回解けるとは限らないので、とても不安。

街が幾つかあって、街の間の距離がmaxDirect以下なら移動できる。好きなところに中継地点を追加して、ある街からある街まで、maxTravel以下の移動距離で移動できるようにしたい。最低何個追加すればいいか?

まず中継地点をどういう風に置いたらいいのか考える。スタートからゴールまでを結ぶ経路は一本道になっているはずなので、自由に動かせる中継地点は直線上になるように配置されるはず。つまり、街の間の直線に載せればいい。必要な個数は距離をmaxDirectで割ればいい。

追加個数と最短距離を同時に求める方法が良く分からなかったので、x個追加したときの最短距離がmaxTravel以下か?という判定で解を二分探索することにする。x個追加で行けるかどうかは、ダイクストラで出来そう。つまりノードを位置と残り追加可能個数に拡張してゴールまでダイクストラすればいい。追加個数の最大は2000/1で2000か?計算量は、log2(2000)*(2000*50*50)log(2000*50)ぐらいか?いけそうな、だめそうな。まあ書いてみるか。

書いた。しかし遅い。全然間に合わない。うんうんうなるが良く分からない。残り35分ぐらいになって、300みんな結構時間かかってて、このままでは300間に合わないかもしれないと思い、500は中断。

300 213.82 AC

長方形を円で覆うような問題。

問題が良く分からない。とりあえず二色の円で長方形を覆ってほしそうなことは分かったが、細かい条件がほとんど無意味に見える。赤青交互に並べるだけでいいんじゃないのか?

でまあ書く。あまりにも簡単。ほんとにこの理解で合っているのか激しく不安。

500

500に戻る。残り10分ほど。あれこれ、二分探索する必要なくないか?残り追加可能個数じゃなくて、今までに追加した個数にすれば一回ダイクストラするだけじゃないか…。自分のアホさ具合にうんざりしながら書きなおすが、それでも最悪ケースが手元で5秒かかる。がんばって高速化しようとするが時間切れ。

Challenge Phase

500はTLEいそうだなあと思いつつも、怖いので手を出せず。300は他の人のコードも自分の理解と同じっぽいので、読んで安心して終了。

感想

300が通る。300なのは英語がむずかったせいだという理解。500からだとやっぱり調子がでない。でも、今回はちゃんと見切りが出来てよかった。500の周りが結構落ちたので、今回レート激減かなと思ってたのが、微減ですんだ。500の速度が遅いと思ってたのは、手元で-O2つけ忘れていたせいだと判明…。おい自分、ふざけてるのか。しかし、System Testは落ちる。答えが合わない。よく見てみると、ダイクストラのコードが間違ってる。おい…。今回はもう3重にミスを重ねたので、自分には猛省を促す。次回までには何とかしたい。

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

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

2010-01-15

SRM458コード

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

昨日の問題は全部一行で書けるそうなので、書いてみる。けどC++だとよくわからないので、Haskellで。一行に収まってないけど。900は解き方わからないので書けず。

expectBounces x t =
  sum [ 0.25 | a<-x, b<-x, a<b, b-a <= 2*t ]

main = do
  print $ expectBounces [5, 8] 2
  print $ expectBounces [5, 8] 1
  print $ expectBounces [91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592] 458
  print $ expectBounces [75432] 386
  print $ expectBounces [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 3
import Data.MemoTrie

minCoins price = sum price - f (1::Int) where
  f = memo $ \c -> maximum (0: [ f n + sum [ p`div`n*(i-1) | p<-price] | i<-[2..100000`div`c], let n=i*c ])

main = do
  print $ minCoins [25, 102]
  print $ minCoins [58]
  print $ minCoins [1, 4, 5, 9, 16]
  print $ minCoins [1, 1, 1, 1, 1]
  print $ minCoins [28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498]

SRM458

00:23 | SRM458 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM458 - tanakhの日記 SRM458 - tanakhの日記 のブックマークコメント

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

2196…赤コーダーを神回避。

250 228.80 AC

一直線上に同じ質量の体積0の玉が幾つかあって、それらが左右どちらかに一定の速度で動いている。ある時間までに、それらは何回衝突するか?

衝突はすり抜けと同じなので、それらが時間以内に距離0まで近づくかどうか調べればいい。あとは、玉の数が12個しかないから、2^12全部試せば期待値が出るが、玉を二つ選んだ時、それらが互いに近づく方向向いてる確率は1/4だから、全部試さなくても距離が近い対の数に0.25を掛けるだけで良かった。

450 192.07 AC

いくつかの商品を買うのだけど、通貨を適当に決めて、最小の枚数のコインで支払いたい。コインの価値は下から整数倍になってないといけない。支払うのに必要な最小枚数は?

ちょっと考えて、これはコインの組み合わせそんなに多くないんじゃないかと思ったので、とりあえず探索を書くことにする。全組み合わせを求めて、それからそれぞれ最小枚数を求める。ひとまずかけたが、サンプルでかなり遅い。余計なコインがあっていいので、新しいコインを追加するときに、前のコインの素数倍だけ試せばいいということに気づく。10倍ぐらい早くなるが、まだ10倍ぐらい足りない。枝刈りをやりたいが、枝刈りをするには途中の経過が必要だ。そのためには、再起のたびに何か計算しないといけない。さらに少し考えるに、新しいコインを一個作る度に、何枚コインを減らせるかがわかるはずだ。それの最大値を求めればいい。そうすると、最後に最小枚数を計算する必要がなくなって、全体が速くはずだ。そういうわけで、組んでみる。確かに速い。最悪ケースでも間に合いそうだ。しかし答えが全然合わない。どうしたことか。計算にあんまり自信がないので、そもそもこれ間違ってるんじゃないかと、さっきのコードに戻して高速化することにする。しばしうなる。アイデアが浮かばない。さらにうなる。うーむ、やっぱりさっきのはあってるような気がする。コードがバグってるだけじゃなかろうか。一つ目のケースが間違っていたので、ゆっくり原因を探っていくと、a*(b/c)と書くべきところがa*b/cになっていた。なんというしょぼいミス。それを直して正しくなったのでサブミット。サブミットしてから気づいたが、この探索、どのコインを作ったかを覚えて置く必要がないので、簡単にDPにできるのか。よくできてるなあ。

900 Opened

約数として、4の剰余が0のものをa個、1のものをb個、2のものをc個、3のものをd個もつような数が存在するかどうかをO(1)で確かめるような問題。

450に時間をとられすぎて、残り15分ほど。無理っぽいが一応読んだ。でもやっぱりだめだった。

Challenge

結構入力が親切だったので、コーナーケースみたいなのは作れず。450が他の人が結構TLEで落ちたっぽい。自分のも探索だったせいか二回ほどChallengeもらった。まあぎりぎりで出したわけではないので、ちゃんと確認はしてます。

反省

3回連続で100位付近で、そろそろいい順位がとりたい。すんドめが続いて辛い。450なんでこんなに時間かかったのか。デバッグで20分ほどロスしたのが痛い。900もゆっくり考えたかった。

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