SRM433@TopCoder - nodchipの日記

SRM433@TopCoderに参加しました。まずは各問題の概要と自分の回答状況。

250@Div1

N個の文字列を並べ替えて結合したもののうち、同じ文字列K個の繰り返しのみからなる文字列の並びが何個あるか求めよ。順列組み合わせは重複を許す。

初めにnext_permutation()とrotate()で全部試すという全数精査コードを書いたのですが、最大ケースで8!×160×160=10億となってしまい、サンプルが通りませんでした。
次に同じ文字列がK個含まれているかを判定するルーチンをrotate()を使わずに書いたのですが、aK個(aは任意の自然数)含まれているときに誤った出力をしてしまい、ダメでした。
最終的には結合した文字列の長さのすべての約数について、上記のルーチンを使用して、最も大きい数字がKならカウントするというコードを書き、サンプルが通ることを確認して提出しました。

500@Div1

N×Mの格子上に、頂点が格子の交点に置かれるように菱形を配置する。菱形の配置が何通りあるか求めよ。

N,M<=100だったためO(N^2M^2)のアルゴリズムだろうと当たりをつけて考え始めました。
初めはn<=N、m<=Mとなるn×mのサイズの長方形の4辺と接する菱形の個数をカウントして、これを上下左右に動かした時の個数を数えればよいだろうと考えたのですが、コードを書いてみたものの答えが合いません。
結局解くことができませんでした。

終了後になって"長方形の4辺と接する菱形"では不十分で、2頂点が長方形に接しないパターンもあるということが分かりました。

1000@Div1

N×Mのマスの上に城と進入禁止区域とA〜Zまでの26種類の土地が配置されている。A〜Zを新入禁止区域にするために必要なコストが与えられる。城から上下左右に動いて行った時にマスの外側に到達できないように進入禁止区域を作っていった時、最小のコストを求めよ。最小のコストが同じ場合は新入禁止区域の数が小さいものを求めよ。

初見で深さ優先探索をすれば解けるのかと思ったのですが、計算量が見積もれなかったためあきらめました。

撃墜フェイズ

TLEしそうな人がいたのでコードを見ていたのですが、結局何もできずに終わりました。

システムテスト

250のみ通りました。

レーティング変化

2103->2083でした。思ったよりも落ちなかったため安心しました。

総評

得意な幾何が取れなかったのが悔しいです。もう場合分けを深く考えられるようにしていきたいと思います。