俵言スマートフォン用の表示で見る俵言しがない社会人が書く、勉強とかのこと。(A,B,C)昨晩ARC039に参加しました。相変わらずARCはDは解くまでに至らないので省略します。そのうちARCボスラッシュならぬDラッシュで復習記事書きたいですね。999)が与えられるので、AかBのどれか一桁を変えたときの(変えなくても良い)A-Bの最大値を答える問題。一瞬めんどくさいこと考えようとしましたが結局全通りすることに。strでやると楽ですよね。max(chA-inB,inA-chB)Bの一と十の位を0にできることに気付かずにWA出したのは本当にしょうもなかったです。高橋幼稚園N人の園児にK個の飴を配るときその幸福度(各園児の持つ飴の数の積)が最大になるような配り方が何通りか求める問題。場合は、要は園児に出来るだけ均等に配りましょうって事なんですよね。感覚的には納得できるけど、なぜそれで最大化できるのか?って言われると答えられない..勉強します。Kの場合は、どう配ろうが幸福度が0になるので全通りを求める。重複組み合わせの話になります。B問題はこれを知ってるかどうかで100点取れるか決まったようなもんです。Iこれだと園児4が飴を総取りすることになるといった感じに。高校数学は本当に懐かしいです。1000000007偉そうに重複組み合わせの説明したんですけど、実は109+7で割るの忘れてWA出したんですよね。自分の不注意さが情けない。あとpythonだとパスカルの三角形作らなくてよいので実装が楽でした。K回動き回った高橋君の位置を特定する問題。DancingLinksってデータ構造、これからも覚えときたいですね。pythonでどうにかこうにか通せたんですけど、重要なのは遅延評価ですよね。4方向に次に進んだ場合にたどり着く先を全部計算していては間に合わない。右の近傍は自分の右のマスにする左の近傍は移動元(here)のマスの左近傍にする上の近傍は自分の上のマスにする下の近傍は自分の下のマスにするとし、加えて移動元(here)の右の近傍を、移動先(next)の右の近傍にしておくとしました。それで、移動する段階になって初めて、その方向の近傍を繰り返し辿ることで本当の移動先にたどり着きます。here[1]時間制約考えると遅延評価って大事ですね。Treeとかもそのうちちゃんと実装しないといけないなあと思います。結果はボロボロでしたが勉強にはなりました。場合、園児に均等に配ると良いのがどうしてかよくわからんって話だったんですけど、これ普通に計算したら良いんじゃね?と思ったのでやってみることにしました。置くと以下の最大化問題を解くことになります。一つ目の式が最大化したい目的関数、二つ目が制約条件です。計算を簡単にする為に目的関数を対数を取ったものに変更して、を考えます。制約条件の下で最大化するということでラグランジュの未定乗数法を使ってみることにしました。本当は関数の凸性の話とかあるんですが、これについてはまた機械学習の方の記事で書く予定です。今回は仕組みの話はスルーで行きます。以下のラグランジュ関数を考えます。偏微分することにより以下を得ます。これらの式(今回はN+1個)を=0としたときの連立方程式を解くことで、目的関数を最大化することができます。ちなみに式(N+1)=0はそのまま制約条件を表してますね。自然数じゃないとダメなのでこのまま答えにしたらダメなんですけど、できるだけ均等にした方が良いってことは分かりましたね。最初に言ったようにラグランジュの未定乗数法についてはまた書く予定です。最尤推定とかでほぼ確実に使うのでちゃんと復習しようと思います。Bについてその2(5/18に追記)上のおまけを更新後、友人から「いやもっと簡単に示せるやろ」と突っ込みを受けたので紹介します。ついて,が成り立つことを使えば終わりやろって言われました(^_^;)この証明は以下のように簡単に出来ます。これを使って例えばN=3、K=10の場合を考えます。園児2,3に1個づつ飴を与えておいてのようにすると最大値をとるのは飴を出来るだけ均等にした場合であることが分かります。聞いたらなるほどって感じです。僕の頭でっかちさが露呈しました。俵言は、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、Amazonアソシエイト・プログラムの参加者です。はてなブログをはじめよう!Tawaraさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。