Hatena::Grouptopcoder

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

 | 

2009-01-21

SRM433

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

なんかむずかったぞー。

250 204.78 AC

文字列の集合が与えられるので、

それらを連結してできた文字列のうちmagic wordであるものの数を数えよ。

magic wordとは、文字列を任意文字ローテートしてできた文字列のうち

もとの文字列と等しいものの数がK個である様な文字列である。

文字列の数が8個まで、長さがそれぞれ20まで、なので、

馬鹿サーチをすると8!*(8*20)^2でちょっと厳しいかなあと思ったのですが、

別にそんなことはなかったらしい。

普通に、文字列sに対して、kmp_count(s+s.substr(0, s.length()-1), s)==Kかどうかで判断。

250にしてはなんかむずい予感。

最初、文字列をsortしてnext_permutationに書けたが、重複がなくなっちゃうので間違い。

500 204.26 AC

N*Mの格子が与えられるので、格子点から四点をえらんでひし形になる選び方の数を求めよ。

N, M<100。

最初DPかなあと思って考えたが、分割しても全然問題が単純にならない。

で、同じ部屋の人たちも全然サブミット来ないからなんか難しいのかなあとか思った。

いろいろと考えていると、ひし形は、中心ともう一点決めるとあとの点のありうる数は

O(1)でもとまることに気付いたので、がんばってごしごし実装。

式がややこしくなりすぎて正確に書ける自信がなかったので、

O(N)で求める版も作って慎重に検算。

解が一致することとTLEのチェックなどしてゆっくりサブミット。

50分ぐらいかかった…。

なんか他の人のコード見てると解き方はいろいろあったみたいだなあ。

1000 未読

読めず。

チャレンジ

なんか間違ってそうだなあと思ってずっと見てたソースが

実はあってて、結局何もできなかった。

手元で250の馬鹿サーチを試すのを忘れてたので、

チャレンジするかせざるか見極められなかった。

サンプルに最大のテストケースがあったので、

さすがにTLEはなさそうだと思ってチャレンジしなかったのだが、

結果的にそれは良かった。

今度からは準備しようと思う。

感想

400点ちょいなのになぜかルームトップ。

ちょっとだけうれしい。

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