がべーじこれくしょん

技術系とかいろいろ

Typical DP Contest D - サイコロ

問題文

atcoder.jp

解法

倍数判定なので、まずはDを素因数分解する。このうち、サイコロの出目は1〜6のみなので、この範囲の素因数のみを考えれば良い。つまり、Dを以下のように分解して考える。

$$D = 2^a \cdot 3^b \cdot 5^c \cdot R$$

あとはDPをする。今回の場合は、出目を列挙する必要はなく、今までに降った中で条件を満たす確率さえわかればよい。そのため、以下のように考える。

N回サイコロを降った時、出目の積の因数のうち、2がa回以上、3がb回以上、5がc回以上含まれている場合、出目の積がDの倍数である確率

遷移式は以下の通り。

\begin{eqnarray} dp[0][0][0][0] &=& & &1 \\ dp[N][a][b][c] &=& & &dp[N-1][a][b][c] \\ && &+&dp[N-1][a-1][b][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a][b-1][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a-2][b][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a][b][c-1] \cdot \frac{1}{6} \\ && &+&dp[N-1][a-1][b-1][c] \cdot \frac{1}{6} \\ \end{eqnarray}

左辺と右辺に注目するとサイコロを振った回数Nの状態は保持しておく必要がないことがわかる。そのため、最終的な遷移式は以下の通り。

\begin{eqnarray} dp[0][0][0] &=& & &1 \\ dp[a][b][c] &=& & &dp[a][b][c] \\ && &+&dp[a-1][b][c] \cdot \frac{1}{6} \\ && &+&dp[a][b-1][c] \cdot \frac{1}{6} \\ && &+&dp[a-2][b][c] \cdot \frac{1}{6} \\ && &+&dp[a][b][c-1] \cdot \frac{1}{6} \\ && &+&dp[a-1][b-1][c] \cdot \frac{1}{6} \\ \end{eqnarray}

提出

今更だけどPythonの関数を使用する際はValueErrorに気をつけような

主にdivertaコン2ndの反省です。

競プロに留まらず、関数の仕様を正しく理解していない状態で使用し、余計なバグを踏むことは非常に愚かな行為です。

組み込み関数や、ライブラリを使用する際は、必ずリファレンスを読み、その関数の使用を十分に理解した上で使用しましょう。

ちなみに、AtCoderで判定結果がREになった際は、例外処理機構(Pythonでいうtry-except文)を用いて、原因箇所を特定していくのがセオリーです。 これについては、以下記事が非常に参考になりました。 qiita.com

今回何があったか

B問題で、なぜか最後のテストケースでREになってしまい通りません。 コードをくまなく目grepしましたが、実装上おかしな部分は見当たりません。 当然、手元でサンプル入出力を試しても正常に動作しています。

try-exceptで様々な部分の例外を調べていたところ、以下の部分がヒットしました。

print(N - max(d.values()))

ここで、dはint型のdefaultdictです。dに格納されているのは、(p,q)をキーとして、座標間の差が(p,q)であるものの数を値として持っています。

この行をtry-exceptで囲み、submitすると、判定がWAに変わりました。この結果から、この部分が悪さをしていると断定できました。ここから詳細な原因の特定まで、かなり時間がかかってしまいました。

結局、N=1の際に、d.values()がempty listとなり、max関数がValueError例外を送出していたことが原因でした。

公式ドキュメントでは、以下の部分で説明されています。

The default argument specifies an object to return if the provided iterable is empty. If the iterable is empty and default is not provided, a ValueError is raised.
Built-in Functions — Python 3.7.3 documentation

Python3.4+から、max関数のオプションとしてdefaultというものが指定できるようになりました。defaultオプションを指定すると、仮にempty listがmax関数に渡された際、ValueErrorを送出せずに、defaultとして指定されている値を返却してくれます。

empty listの最大値を求めるというクエリは確かに不正ですね。この挙動は理にかなっています。

max関数のdefaultオプションの他には、以下のように配列のempty checkを行う方法もあります。こっちのほうがシンプルですね。

tmp = d.values()
if tmp:
   print(N-max(tmp))
else:
   print(N)

そもそもN=0の場合だけはじけばよかった気もします。

まとめ

いずれにせよ、今回はmax関数の仕様を正確に把握していないことが原因です。考えてみれば、送出されているRuntimeErrorは非常に自然なもので、エラーメッセージを見ればすぐに原因がわかります。しかし、AtCoderでは、コンテスト終了までエラーの原因や発生箇所は閲覧することができません。また、実行環境が存在しない場合(コーディング面接中など)には、当然実行してエラーメッセージを確認することはできません。

プログラマーの中には、私のように、関数の呼び出し方法等の「うわべ」だけを見てわかった気になっている愚か者がいます。必ず、リファレンスを見る際は、引数や返り値の型、送出されうるエラーの種類と状況、関数の挙動などをしっかり理解することが大切です。

Happy Coding!

DRECOM サマージョブ 2018に参加してきました

参加したので書こう書こうと思っていたのですがついに年が明けてしまいました…

DRECOMのサマーインターンシッププログラム「サマージョブ2018」に参加してきました!

今回は、サーバーサイドエンジニアとして参加してきました。

続きを読む