投稿

1月, 2019の投稿を表示しています

AtCoder:ABC110-C(String Transformation)を解いた

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 むずい。 本番でもできなかった(テストケースに不備があってunratedになった回) 復習しててもなかなか解けなかった かなしい ## 問題 C - String Transformation SとTという二つの同じ長さの文字列が与えられ、文字を二つ決めて、Sに含まれる全てのその二つの文字をswapするという操作を行う。 この操作を行ってSをTに変えられるかどうかを判定する問題。 ## 考察 普通にシミュレーションする(先頭から見ていって、毎回これまでに作用させた変換を見に行って変換していくと)と、$O(N^2)$かかる。 じゃあどうやんだ、ってなってからいろいろ実験するも、うまくいかず。 実験してる最中も間違えて実験してたりしたので変な考えにはまってしまった。 ちゃんと実験しよう。。。 $c_1$と$c_2$を選んで変換するときに、間違えて$T$の方も変換したりしてたので、ダメな例もうまくいくなあ、となってはまったのが原因。 ## 解法 ちゃんと実験すれば、SからTへ違う文字から同じ文字へ写像されるとダメだし、ある文字から複数の文字へ写像するのもだめで、そういうのがない一対一の変換ができればおっけー、ということに気づく。 普通にやろうとすると、前者の「SからTへ違う文字から同じ文字へ写像されるとダメ」をチェックするのが$O(N)$かかるので全体で$O(N^2)$。 解説にもあるとおり、SからTの写像をみるのと同じようにTからSをみることをすれば$O(N+N)=O(N)$ですみます。 ```python S = input() T = input() def check(A, B[Numeron App](https://numeron-app.herokuapp.com)[i] elif d[A[i]] != B[i]: return False return True print("Yes" if check(S, T) and check(T,

AtCoder:ABC112-D(partition)を解いた

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 ## 問題 <a href="https://atcoder.jp/contests/abc112/tasks/abc112_d">D-Partition</a> N,Mが与えられて、N個の自然数の列${a_i}$を考える。 この数列の和がMになるもののうち、この数列の最大公約数を最大にする数列を考えて、そのときの最大公約数を出力する問題。 最大公約数の最大、こんがらがる〜 ## 考察 和が制約になっているときの最大公約数って関係ありそうだけどよくわからん、ってなったので数式にしてジッと睨む。 最大公約数が$d$だと、$d$でくくってあげることができるので、制約式の両辺を$d$で割る変形ができそう 割ったあとの左辺(数列の和の方)はN個項があって、それぞれ1以上でなきゃいけないから左辺はN以上、右辺はもちろん割り切れてなきゃいけない。 と、ここまで考えて、あー、逆にすればいいのか、と気づき、制約式の両辺を$d$で割るのではなく、括られた数式の方で割るようにしてみる。 とすれば、求める最大の最大公約数は * Mの約数であり * Mを割ったときの商がN以上 の中で最大のもの、となる。 <div class="separator" style="clear: both; text-align: center;display:none;"><a href="https://pbs.twimg.com/profile_images/378800000000403108/c8cfcb35c76ca5fc55fc2dc680685e8c_400x400.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://pbs.twimg.

AtCoder:ABC114-D(756)を解いた

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 これです。 <a href="https://atcoder.jp/contests/abc114/tasks/abc114_d">D - 756</a> ## 問題 Nが与えられる。 N!の約数のうち、約数の個数が75個であるものはいくつあるか、という問題。 約数の約数か、こんがらがる〜 ## 考察 N!は大きいけど、約数なら素因数分解した結果だけもっておけばよくて、一個ずつ素因数分解して素因数と指数をもっておくdictionaryがあれば大丈夫そう。 Nが小さいから素因数分解も工夫しなくて良さげだったけど、 一応$\sqrt{n}$までで止める試し割りみたいなかんじでやろう。 そのあとどうすればいいのかな、って少し考えて、 75を素因数分解するとそこまで複雑じゃなさそうなので、約数の個数が75になるパターンが少なそう、とおもって調べて四つしかないことを確認して一個ずつ書けばいいのかな ## コードの修正 最初に提出したコード。 汚すぎて笑える. とりあえず考え方があってるかなーと思ってだしてAC ```python from collections import Counter N = int(input()) c = Counter() for n in range(2, N + 1): i = 2 while i**2 <= n: count = 0 while n % i == 0: n //= i count += 1 if count != 0: c[i] += count i += 1 if n > 1: c[n] += 1 d = Counter() for v in c.values(): if 2 <= v: d["3"] += 1 if 4 <

AtCoder:ABC114-C(755)を解いた

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 与えられたN以下の753数の個数を求める問題。 <a href="https://atcoder.jp/contests/abc114/tasks/abc114_c">C - 755</a> 753数は、3,5,7以外の数字が入ってないかつ3,5,7が一回は必ず入っている数字のこと。 Nが$10^9$のオーダーなので全部調べると間に合わない。 ポイントは、解説で準753数と呼んでいる「3,5,7以外の数字が入ってない数字」を先に列挙して、その中で「3,5,7が一回は必ず入っているかどうか」という条件をcheckするという考え方ができるかどうか、でした。 準753数の個数が少なく、かつN個の数字を全て舐めなくても準753数のリストが得られることに気づけるかどうかが大事な問題な気がします。 準753数の個数の見積もりですが、$p$桁の準753数の個数が$3^p$個である(重複順列)であることを考えれば準753数の個数は等比数列の和になるので、$3^a$($a$は大きくても9とか10ぐらい)しかなくて、これは数万ぐらい。 準753数のリストの作り方は、解説PDFには再帰関数を用いるものが紹介されていました。 後ろに3,5,7をつけていくという感じです。 自分は直積を使うものを先に思いついたのでそっちで書いてしまいました。 準753数を求めることと753数かcheckする部分を分けて書いたのでこれいけましたが、 解説コードのように再帰関数を使えばこの二つはまとめて同時に処理できるので、そっちの方がコード量が少なくていいですね。 せっかく書いたので直積を使うバージョンを載せます。 pythonの`itertools.product`を使います。 重複順列が作れます。 repeatで長さを指定できるので、今回は桁数ごとに重複順列を生成して、頑張ります。 ```python def get_A_product(digits, N): A = [] flag = False p = 3 w

【論文紹介】Neural Factorization Machines for Sparse Predictive Analytics

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 最近、Factorization Machines(FM)を勉強しています。 なぜかというと、去年の年末にこの記事を読んで、おもしろそうだなと思ったからです。 [DeepなFactorization Machinesの最新動向 (2018) - Gunosyデータ分析ブログ](https://data.gunosy.io/entry/deep-factorization-machines-2018) 最近よくこのワードを聞くので、せっかくだし勉強しておくと論文読み会とかで出てきた時に楽しめるようになるかな、というモチベです。 今回は、deep + FMなもので上の記事で紹介されていなかったNeural Factorization Machines for Sparse Predictive Analytics(NFM)を読んだので、紹介記事を書いていきたいと思います。 NFMまでの研究の流れを追ってみようという気持ちのため、これより最近の論文(xDeepFMとか)は読んでないです。 いずれ読みたいです。 論文のリンク↓ <a href="https://arxiv.org/abs/1708.05027">Neural Factorization Machines for Sparse Predictive Analytics</a> (追記) xDeepFMを読みました。 記事書いたのでよろしければ! xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systemsを読んだ ## 下準備 紹介に入る前に、キャッチアップをどんな風に進めていったかも一応書いときます。 協調フィルタリング関連の話題すらほとんど知らなかったので、ちゃんと論文を読めるようになる前にいろいろ前準備として勉強が必要でした(今もそんなに詳しいわけではもちろんないですが笑) まず普通のFMとはなんぞや、というところから調べました。

AtCoder:ABC116-D(Various Sushi)で苦戦したので復習した

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 何気に初めての復習記事かもしれません。 AtCoderのABC116に参加したのですが、Cまでしか解けなかった(しかもBで焦ってWA) ので、Dを復習してみました。 <a href="https://atcoder.jp/contests/abc116/tasks/abc116_d">D - Various Sushi</a> ## コンテスト中 種類数がめんどそうだから種類の数を固定してそれぞれ実験すればいいのかな、と考えました。 それはあってたぽいんですが、そこからがわかりませんでした。 種類の個数を固定した時に得られる最大美味しさポイントをそれぞれ求めればいいわけですが、 どの種類のネタを使うかも調べてたら組み合わせ多すぎて計算終わらんやん、とか、アホなこと考えてました。 1種類ずつ増やしていく、というのが正解なわけですが、コンテスト中に思いついたのは本当に愚直に1種類から増やしていくもので、これで考えていたのでswapする発想にたどり着けませんでした。。。 いや、1種類から増やしていっても、想定解法の貪欲にとっていったときの種類数から増やしていってももちろん同じですが、1種類だからわかりづらかったという言い訳です。 そもそも必ずしも1種類になるように選べるわけじゃないので、これじゃない感を感じてしまいました。。 ## 解説見てから 解説みてみて、種類ごとに決め打ちしてやっていくのはあってたのかーとなりました。 1種類ずつ増やしていくやり方は、解説にもある通り * 現時点で食べることになっている寿司から、食べなくても種類数が減らない寿司のうち美味しさ最小の寿司 と * 現時点で食べることになっていない寿司から、新しい種類の寿司のうち美味しさ最大の寿司 をswapしていくと、種類数を一つ増やしたときの最大美味しさポイントが得られます。 理屈はわかったので早速コンテスト後に実装してみようと思い、解説にあったようにpriority queueを使って実装してみようと思ったのですが、うまくできませんでした。

同じ分布に従う確率変数のうちどれが最大になるか

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 ### 問題 同じ確率分布に従う三つの確率変数$A,B,C$のうち$A$が一番大きい値をとる確率は?という問題を考えます。 普通に考えると、1/3ぽいです。 $A,B,C$は全部同じ条件で、どれかが最大になるので均等に1/3になりそう。 しかし、ある人が違う答えになる解法をもってきました。 Aが最大になることは、「$A>B>C$ または$A>C>B$」と同値で、 これは「$A>B$ かつ $A>C$」と同値です。 なので、$P(A>B) \times P(A>C) = \frac{1}{2} \times \frac{1}{2} =\frac{1}{4}$ あれ、1/4になってしまった笑 どこが間違っているのか、と聞かれたので答えるつもりで記事を書いてみます。 ### いろいろ変 $P(max=A)=P(A>B)\times P(A>C)$としているのがおかしいですね。 正しくは $P(\max=A) = E_A[P(\max A=a)] = E_A[P(a>B)\times P(a>C)]$ ようするに、同じ$A$の値に対して$B$と$C$が$A$より小さいことが$A$が最大になる条件なのに、上では違う$A$でもよくなっているわけですね。 というところもおかしいですし、なにもせずに$P(A>B)=\frac{1}{2}$としていいのなら求めたい確率も1/3で自明なんじゃないか?とも思うのですが。。。 ### 修正案 こんな感じでやればちゃんと1/3になります。 ただの数3でやる置換積分ですが。。。 累積分布関数を微分すると確率密度関数になることを使います。 $f$が確率密度関数、$F$を累積分布関数とします。 $P(\max=A) = E_A[P(a>B)\times P(a>C)]= \int_{-\infty}^{\infty} f(x)(F(x))^2 dx=\int_{0}^{1}t^2 dt=\frac{1}{3}$ ちゃんと1/3