AtCoder Beginner Contest 184をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 184を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Determinant

求める値は$ad-bc$となるので, それを出力します.

B - Quizzes

「クイズに正解すると$1$点増え, 不正解だと$1$点減る」を律儀に行って, 出力します.

C - Super Ryuma

「超竜馬」にびびってしまいますが, 中身は意外と単純だったようです.

マス目を移動できる条件を再掲.

• A：$a+b = c+d$
• B：$a-b = c-d$
• C：$|a-c| + |b-d| \leq 3$

移動A・Bを多くても$2$回(もちろん$1$回の場合もあります)行えば, 全マス目の半分の場所(市松模様にしたときに同じ色の場所)には移動できます. もう半分だけは, 移動A・Bに加えて移動Cが必要になります.

したがって, $0$回, $1$回, $2$回で移動できるかどうかを判定すれば, それ以外を$3$回で移動できると判定することでよくなります.

• $0$回：同じマスかどうかの判定
• $1$回：上記3つの移動可能条件のどれかに当てはまるかの判定
• $2$回：
  • 移動A・Bの組み合わせは$((a-c) + (b-d)) \, \mathrm{mod} \, 2 = 0$
  • 移動C・Cの組み合わせは$|a-c| + |b-d| \leq 6$
  • 移動A・Cの組み合わせは$|(a-c) + (b-d)| \leq 3$
  • 移動B・Cの組み合わせは$|(a-c) - (b-d)| \leq 3$

D - increment of coins

再帰関数を使うのだろうなということまでは推察できたのですが…….

金貨が$X$枚, 銀貨が$Y$枚, 銅貨が$Z$枚のときの操作回数の期待値を$f(X,Y,Z)$とします. $X$, $Y$, $Z$のいずれかが$100$のときに操作が完了するので, 操作回数の期待値は$f(X,Y,Z) = 0$となります. それ以外のときは, 各々の硬貨を引く確率を考えれば,

となります. これを再帰関数で実装すればよいです.

実行時間が膨大になるので, 「メソッドのある引数に対する計算結果を保存しておき, 後で同じ引数が与えられた時, 計算結果を再利用する」機能であるlru_cacheを用いました. これは実行時間と引き換えにメモリを消費するということでよいのでしょうか……？

あるいは, 必要な回数を全部格納した配列を作成し求めてしまおう作戦も可能でしょう(こちらの方が一般的？).

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 184」
  Editorial - AtCoder Beginner Contest 184

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• Kotaro Adachi様による「Python3でLRUキャッシュを用いてプログラムを高速化」
  🍺Python3でLRUキャッシュを用いてプログラムを高速化 - Qiita

  　卒論でPythonのプログラムを回していたが時間がかかりすぎてうんざりしていた. Python初心者の僕がいろいろ調べていたら高速化のために以下の二つに関するポストが頻繁に見られた. Numba Pythonを速くしたいときにやっ...