Adventarの24日目の記事として書かれました。この記事は、僕がたまたま通すことができたAOJ-ICPC難易度1000のThreeRooksという問題を一緒に解いていこうという趣旨のものです。完全にネタバレなのでもし自力で解きたいと思っている人はすぐにブラウザバックをしてください。僕が思考したステップを順にあげていくので途中でわかったらそこから自力で解くのでもいいかもしれません。問題文はhttp://judge.u-aizu.ac.jp/onlinejudge/IMAGE/winter-camp-2011-day3.pdfにあります。個以下の障害物が適当に置かれるのでどのルークも互いに取られないような三つのルークの置き方の組み合わせの数を求めよという問題です。~つ目の思考とか分けていますが、分け方は適当なのであまり気にしないでください。個であり、障害物がおかれていない行や列はまとめて考えることができます。longのサイズを超えてしまいます。適切にmodを取ったり、割り算のときはmodの逆元を取ったりしましょう。二つ目の思考ルークが三つもあると難しいのでとりあえずルーク二つで考えてみます。ルークが二つのときは比較的簡単で、とりあえずルーク二つの置き方を全部列挙して、そのうち条件を満たさないものを除くという考え方に至ると思います。ルーク二つの置き方のうち条件を満たさないものは、行で被るものと列で被るものがあります。行も同様なので列について考えます。障害物が置かれている列については、障害物一つにつき一回分割が増えるだけなので一つ一つ処理をしてやればいいです。三つ目の思考ルークが二つあるときはまずは置き方を全部数えてから条件を満たさないものを除くという考え方がうまくいきました。これを三つのときにも適用してみようと思います。どのようなときに条件を満たさないのかと考えると、次の三つの場合が考えられます。三つのルークがそれぞれ取れる状態で一直線に並んでいる。(間に障害物が含まれていない)二つのルークがお互いに取れる状態になっており、もう一つのルークがどちらのルークにも取られないところにいる。二つのルークがお互いに取れる状態になっており、もう一つのルークがどちらかのルークとだけお互いに取れる状態になっている。(L字型の配置)四つ目の思考まずは一つ目のケースについて考えます。この場合は簡単で、ルークが二つだった場合と本質的に同じことをするだけで式を少し変えるだけです。次に二つ目のケースです。ルーク二つの配置をお互いに取り合うように配置して、残りの一つのルークを適当に置いてみます。すると、1や3のケースも勿論含んでしまうのですが、何回含むのかを計算することができます。1のケースについては3回数えてしまい、2のケースについては2回数えてしまうことがわかります。