Qual Round 2

アルゴリズム部門の予選。550位まで抜けられるのの2回目。1回目は諸事情により不参加。来週の同じ時間から本選が始まるので、時間調整の意味も兼ねて。

最初はコンパイルできないとサーバに言われたらしく15分延長があって、結果表示の終盤でサーバダウン。キャンセルされなければ通るけど、今のところ未定。

250

バスの時刻表(最初のバス、間隔、来る本数)が複数与えられるので、バス停に到着した時刻から次のバスが来るまでの最短の時間を答えよという問題。同時なら0、もう来ないなら-1とする。

実装するだけ。同時判定が微妙に間違っている人をチャレンジしてみた。

500

複数桁の数字を2ないし3桁ずつに分割して覚える。各部分における文字が全部同じなら2点、そうではないときに二つ同じ文字があれば1点として、点数が最大になるように分割する。同点のが複数ある場合には、2桁に切る方を優先する。このとき分割結果を答えよという問題。

単純にスコアでDPするだけ。分割方法を覚えておくので、各場所で2桁ずつなのか3桁ずつなのかを覚えておきましょう。

1000

真っ黒・縦縞・横縞・チェック、のいずれかの長方形を書くとき、黒く塗られた場所の合計を答えよ、という問題。同じマスが何度塗られても1回とカウントする。

各x座標についてy方向の断面を作成して、長方形の下端と上端ごとに、今までの区間がどんな感じだったkを計算するようにすれば時間的には間に合うのかなぁと思って実装したものの、時間切れ。

多分長方形の重なり判定を既に書いた部分に対してやればいいんだと思う。重なった部分を新しい長方形にする。残りの部分を長方形になるように切る。塗りパターンをそれらの作業について更新する。とやって、最後に塗りパターンと座標から各長方形の中の黒いマスを計算しておしまい。問題は長方形の分割で数がどこまで増えるか。

既に塗りパターンを計算した結果黒かったら分割の対象にしない、という処理をうまいこと入れると、若干オブジェクト数が減るかも知れないけれど、エンバグしそうなので最適化する必要があるなら他の部分かなぁ、という感じ。