4完3WA

各問題

A - N-choice question

A + B = C となる C の番号をこたえればよいです。

グリッドは小さいので全探索すればよいです。実装がやや面倒かも。

制約によりバツ印同士が混じりあうことはないので、単に左上から右下への並びをチェックしていけばよいです。一度チェックしたものを重複してチェックしないような工夫は何か必要ですが、チェック済みの # は . に変えてしまったりすればよいです。

最初に素数を列挙してからメモ化再帰的なことをすれば通せます。なお列挙する素数は雑に見積もっても 10⁶ 以下でよいです。2² * 3 * 10⁶² > 10¹² なので。

ただし遷移順を工夫しないと間に合いません。具体的には

rec(a, b, c + 1);
rec(a, b + 1, c);
rec(a + 1, b, c);

は通りませんが

rec(a + 1, b, c);
rec(a, b + 1, c);
rec(a, b, c + 1);

は通ります。

これも再帰解を書いてみたんですが、パターンが多すぎて案の定処理終わらず。

散々な出来かと思ったのですが、意外に耐えてました。