ABC003を解いてみた
A問題
期待値を求める式は
10000 * (1/N) + 20000 * (1/N) + … + N*10000 * (1/N)
= 10000 * (1/N) * (1 + 2 + … + N)
= 10000 * (1/N) * (1/2) * N(N+1)
= 5000 * (N+1)
と変形できたので5000*(N+1)を出力します。
B問題
SとTを1文字ずつ先頭から確かめていきます。同じ文字、もしくは片方が@で片方がatcoderのいずれかならばWINのほうを出力しそうでなければLOSEのほうを出力するコードを書きました。@について確かめるところで (a == "a" or a == "t" or … or a == "r") と全部書く方法で実装したんですが、もうちょっといい方法はないのかな…？
C問題
まず見るべき動画は大きいほうからK個であることはわかりました。そして、最初の動画の点数ほど多くの回数2で割られるため小さいものから見たほうがよさそうです。（証明はできてない）あとは入力をソートして上のK個に対して小さい方から順番に処理を行いました。やるべきアルゴリズムは割とすぐにわかったのですが実装でちょっとハマってしまいました…
sort関数を使うためにはデータ構造としてlistを使う必要があります。listの要素のすべてを対象としてint関数を実行するためにはどうすればいいのか調べ、mapを使って実装を行おうとしたのですがどうやらPython2系の情報だったようでした… Python3でこの処理を行うためには内包表記を用いて
list_int = [int(i) for i in list_str]
と書くことで実装できます。
参考サイト
D問題
満点解法は思いつきそうになかったので部分点を取れるようにコードを書きました。まずR×Cマスの中でX×Yマスの長方形を何個作ることができるのか求めます。これは数学的に考えて(R-X+1)×(C-Y+1)とすることで求められます。次にR×Cマスの長方形の中にサーバーとデスクを置くのは何通りあるのかを求めます。計算自体はD+L個の中からD個を選ぶコンビネーションで求めることができます。
最初にforループを用いて分子と分母をそれぞれ計算しようとしましたが当然ながら変数のメモリが足りるはずもなく失敗。次にscipyのscipy.misc.comb関数を使ったところ計算自体はできたものの実行時間が超過してしまい失敗。次のnCr (mod m)を二次元配列で列挙して求める方法を使って実装したところ無事成功！
www37.atwiki.jp
満点解法についてはサーバーとデスクを置く方法の数え方がそのままではまずくサーバーかデスクがいずれかの辺に接していないパターンはありえないためそのパターンを包除原理を用いて引いてやることで求めてやるとあって納得
A,B,C問題とD問題の部分点まで解けて嬉しいです。が、解くのに3時間かかってしまったのでもっと早く実装できるよう頑張ります…
