topcoder SRM775 参加記

SRMそんなに出ないしすぐ忘れるのでコンテスト参加記を残そうかなあと思ったので（すぐ飽きそう）

前回、初回にして爆死はこちら→wk1080id.hatenablog.com

まともにACして早く灰色から脱出したいところ。
直前にtopcoderでのコードの書き方を前回の記事を見ながら思い出す。（提出はmain関数以外全部とか）

div2Easy

長さLで使われる文字がアルファベット最初のS文字であるような文字列のうち、文字列集合forbiddenに属するどの文字列とも完全に違う文字列はいくつあるか。
完全に違うとは、長さNの2つの文字列s,tがあったときに0以上N-1以下のすべてのiについてs[i] != t[i]をみたす。
Sは1以上26以下
forbiddenの要素数は1以上30以下
forbiddenの要素の長さはすべてL
Lは1以上6以下

完全に違うの定義を誤解していて時間をたくさん使ってしまった。
i文字目に使える文字の種類を調べて、それらをかけていけばいい。

div2Med

2次元のマップcaveが与えられる。マップは何もないマス'.'と岩のマス'#'と岩に隠れているkoboldがいるマス'K'のいずれか。
マップでは4方向に移動でき、'.'は連結。
desiredAreaという数が与えられるので、'#'のマスを'.'に変更してマップの'.'の数をdesiredArea個にしたい。
ただし変更後の'.'は連結で、koboldに隣接するマスは'#'でなければならない。
この条件をみたすようにマップの'.'の数をdesiredArea個にしたときにありうる変更後のマップを1つ出力せよ。（そのようなマップが存在しないときは空のvectorを出力する）
マップの縦の長さは1以上50以下
マップの横の長さは1以上50以下
desiredAreaは最初の'.'の個数以上、マップのマスの個数以下

'#'から'.'にできない（koboldと隣接している）マスを初めに調べておいて、あとで足りない個数分だけ色ぬりすればよい。
最初、連結に気づかなくて、変更できる'#'を上から順に塗っていたけど、連結なのでbfsで書いた。
challengeフェーズで部屋の人のコードを読むとみんなdfsで書いてたし前計算とかしてなかった。

div2Hard

Nとindexが与えられる

for sum = 0 .. 3*N-3:
    for x = 0 .. N-1:
        for y = 0 .. N-1:
            for z = 0 .. N-1:
                if x+y+z == sum:
                    visit (x,y,z)

の順でN*N*Nの3次元座標にアクセスするとき、index番目(0-indexed)にアクセスする座標を答えよ。
Nは1以上10^6以下
indexは0以上N^3 - 1以下

わからねー
xがiのときの通り数は(i+2)(i+1)/2なのでそれを使ってO(N)かけてsumを確定させて、そのあとはxを0から順に調べてyを順に調べて…
でできると思ったんだけど、sumを確定させるときのそれは嘘であることが終了直前にわかり、無（x,y,zはN-1以下でないといけないので）

challengeフェーズ

ルームのhard提出が1、med提出が3とかで、無
ルーム内challengeはなかった…

システス

Med落ちたけど
というかルームでMed落ちてるの自分だけ…
（Med落ちたということは、Medの日本語問題文が間違っている可能性があります）

レート

レート変動見るの難しすぎか？一度ログアウトしてログインしなおします。
734 -> 781(+47)
灰色コーダーの旅はこれからだ！〜次回作にご期待ください〜