最後に三つ目のケースです。これができればこの問題が解けたことになります。書きましたがこのパートがこの問題の本質です。ルークの配置はL字型をしているので、ルークのうち二つは障害物を挟まず縦に並んでいます。残りの一つのルークはその二つのルークのうちどちらかの横に障害物を挟まず並んでいるはずです。よって、縦に並べるルークを決めたとき、残り一つのルークの置き方がいくつあるかを全て列挙することを考えますが、勿論これを満たす配置はかなり多いので普通に数えていては話になりません。縦に並んでいるルーク二つの配置について考えます。障害物が置かれていない列が隣り合っている場合は圧縮することができる*1ので圧縮します。よって、端から端まで列を順に考えていくことが可能なサイズになるので、端から順に処理をしていきます。今いる列について、その各要素の左右にはどれだけスペース*2が空いているのかを考えます。求めることができます。各要素について上下のスペースも求めることができれば、(左右のスペース)*(上下のスペース)を計算することで、その要素をL字の角の部分にするL字を全て列挙することができます。各要素について上下のスペースは入力時に受け取った情報からすぐにわかります。よって、各列の全ての要素について(左右のスペース)*(上下のスペース)を求めることで全てのL字を列挙することができます。なってしまい、間に合いません。七つ目の思考において、今いる列の各要素について(左右のスペース)*(上下のスペース)を計算しましたが、これを効率よく計算できないかと考えます。(上下のスペース)はそのスペースに属しているマスと共通であることがわかります。それを一つのグループとみなします。すると、そのグループにおけるL字の数を求めるには各要素の左右のスペースの総和を求めればいいことになります。これは各要素の左右のスペースをBITで管理をすることによって対数時間で処理をすることができます。よって、これらをまとめると解けます。実装なんとなく察してきたと思いますが、この問題は実装がメンドイです*4。僕もたくさんバグらせてしまいました。最後に僕のコードを貼って終わりにしますが、僕自身もコードを読解したくないぐらいなので真面目に読むものじゃないです。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。