オフラインリアルタイムどう書く問題作成リハビリ #0 の回答
解きました。
初回回答が70分経過時点。全部パスするけど結構遅い。 そのあと10分くらい経過して全テストケースを27秒（遅いが……）で通しました。Rubyでの実装です。
以下方針について
とりあえず斜めがつらいので時計回りに45度回転して第一象限におく方式で考える。「下」は直線 y = -x + k の k が小さいほどよいので x + y で、「左」は y が大きいほうで考えればよい。テストケースみてサイズ的に数百かける数百程度の探索なのでまあいけるんちゃうと踏んで愚直実装を決め込む。具体的には Hash の Hash でほんとうに盤面を管理する。あと下から左へ、つまり k を 0 からあげて y を k から下げて残りを x として、空いてたらそのサイズの正方形が入るかチェック。入ったら Hash に反映させる。このとき Hash の Hash には size じゃなくて id （input の前からの 0-index とした）で管理しとかないと output つくるときに困る（1敗）。終わったら最大をとって隣接の正方形の id をもって id からサイズに戻して sort して join して終わり。
で、これが遅い。測ってないけど5分くらい？数百x数百程度の探索、かとおもったけどそれに対していれていいかどうかのチェックが走るんで割りと重かったですね……。しょうがないからサイズに対してキャッシュをもっておくようにして早くする。具体的にはもともとこんな感じのことをしていたが
enum = Enumerator.new do |yielder| (0..).each do |k| (0..k).each do |x| y = k - x yielder << [x, y] if b[x][y].nil? # b は hash で使用済みかどうかを管理してる end end end loop do x, y = enum.next end
正方形の size が3のときに k = 8, (x, y) = (3, 5) みたいな点を使うことになったら、size が3以上の正方形は少なくとも k = 8, (x, y) = (3, 5) より右、あるいは上にないと行けない。
なので置き場所が決まったら size => k で覚えておいて、次の正方形のときそのサイズより小さい cache があればそこから開始することができて最初の方の探索をスキップできる。
これで27秒くらい。ここまでで80分くらい経過で終わり。
Ruby コードとしては endless range とか Enumerator とか Comparable とか（使わなかったが）sqs に max かけてるところがみどころでしょうか。sqs からの取り出しはパターンマッチ使えそうでしたがそらでかけなかったので諦めました。 最後の隣接正方形を見つけるところがなんかダサいのでなんとかしたかったですね……↓
27秒でも遅いのでなんとかしたいなーと思うと、正方形を全部埋める必要はたぶんなくて、上端と下端をちゃんともってやればなんか探索がスキップできそうな気がしますがバグらせそうなので諦めました……。
面白かったです
