TopCoder Open 2011 Qual 2 - simezi

ikk君やLongCtrlさんと一緒の部屋。

234.02 / 320.14 / Opened
1撃墜1ミス

165位
1603 -> 1656

WとBからなるの文字列が与えられる。
W,Bを前半が全てW,後半が全てBになるように並べ替えたい。
並べ替えはN種類の操作が可能である。i（1≦i≦N)種類目の操作は距離がちょうどiだけ離れた2つを入れ替える。
各操作は高々1度しか行うことが出来ない。

このとき、並べ替えにかかる操作の最小回数を求めよ。
不可能な場合には-1をかえせ。
文字列の長さは50以下。

いきなり難問きた？同じ長さに対する入れ替えは高々1回。。。
って、もっとも外側のBとWを入れ替えて行けば必ずソートは出来るんじゃないのか。

外側から順に入れ替えていく方針でソースコード書いた。
サンプル合った。見直ししまくって送信。

.とCとKからなる長さnの文字列が与えられる。
0文字目からスタートしてn-1文字目になるべく早くたどり着きたい。
1秒ごとにその場に止まる、ひとつ右のマスへ動く、ひとつ左のマスへ動くのどれかを選べる。

CのマスにはtがちょうどCで割りきれるようなt秒目しか入ることができず、
KのマスにはtがちょうどKで割りきれないようなt秒目しか入ることができない。

n-1文字目にたどり着くのにかかる最小の時間を求めよ。
不可能な場合は-1を返せ。
文字列の長さは50以下、整数K,Cは1以上50以下。

dp。。。かと思ったら普通に幅優先探索すればいいだけっぽい。
書いた。サンプル合った。

アリーナ上ででかいケースをテストしてみると、落ちた。
なんでだ！状態数50^4しかないはずなのに……（←勘違い。本当は50^3しかない）
queueに入ってる個数をpair<int,pi>とかやってるからキューが溢れたのだろうか。

整数3つ組を1つの整数に圧縮して書き直ししてみた。
アリーナ上でもう一度テスト。落ちる。
キューのサイズみると数百万。これ別のとこでバグってるんじゃ……

探索の打ち切り条件に+1書き忘れてて間違っててこれだと無限ループになるじゃん。。。
訂正。でかいケースも通った。

送信。めちゃくちゃ時間くったorz

「表現可能な数」をy*d(y)と書ける数と定義する。
ただしd(y)はyの各桁を足す、という操作を答えが一桁になるまで繰り返す関数である。

min以上max以下の「表現可能な数」の総数を求めよ。
min,max≦10^10を満たす。

とりあえずd(y)はyを9で割った余り。（0のときは9として）
んで……どうするんだろう。

30分くらい考えたけど方針たたず。

明らかにおかしいコードがいっぱい。
落とそうとしている間に先をこされるの流れが2、3回。
Div2勢の中には明らかに間違ってるコードサブミットする人結構多いのね。。。

500にアタックして失敗して-25、めちゃくちゃな1000を落として+50

両方通った。