めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

2021-01-01から1年間の記事一覧

K - Stones の解説

何の話かと言うと atcoder.jpこの問題をネタにして、対戦ゲーム(マルコフ決定過程)の基本的な考え方を説明します。 「負け状態」と「勝ち状態」の非対称な関係 自分の手番の状態 k における状態価値関数の値を dp[k] とします。・・・状態価値関数って何?…

O - Matching の解説(その2)

何の話かと言うと enakai00.hatenablog.comこちらの記事の続きです。 改善のヒントは・・・? 前回の最後に、参加する男性を1人ずつ増やすという発想で、DPの実装に成功しました。しかしながら、まだ実行時間が長すぎるので、さらなる工夫が必要です。前回の…

O - Matching の解説(その1)

何の話かと言うと atcoder.jp上記の問題をネタに・・・うーん。これ、個人的には、「いやよくこんな方法思いついたな」系で、あまりパターン化できないんですが、とりあえずは、できるだけ天下り的な説明はさけて、論理的に正解に近づいていく方法で説明して…

DP演習(問題案)

テンプレートに慣れるための問題 以下の問題について、DP のテンプレートに従ってコードを書いてください。また、それぞれの計算量( など)を答えてください。[テンプレート] # N: データ数 dp = [None] * (N+1) dp[1] = xxxx # 1個の場合の答えを自力で考…

E - Digit Products の解説

何の話かと言うと enakai00.hatenablog.com上記の記事では、「桁DP」について、下から攻める方法と、上から攻める方法を紹介しました。今回は、「上から攻めないとうまくいかない」問題例として、こちらを取り上げます。atcoder.jp 何が難しいの? 問題のパ…

S - Digit Sum の解説(その2)

何の話かと言うと enakai00.hatenablog.comこちらの記事の続きです。 一般の K に拡張する 前回は、K = 99999 と言った(各桁が 0 〜 9 を回る)キリのよい数字という前提で問題を解きました。今回は、K = 38463 と言った一般の場合を考えます。この場合は、…

S - Digit Sum の解説(その1)

何の話かと言うと atcoder.jpこの問題をネタにして、「桁DP」の考え方を説明します。なお、問題文では「1 以上 K 以下の整数」となっていますが、この手の問題では、0 を含めて計算する方が簡単なので、「0 以上 K 以下の整数」として問題を解いておき、得ら…

G - Longest Path の解説(その2)

何の話かと言うと enakai00.hatenablog.com前回の続きです。 ノードを消していく発想(もしくは、トポロジカルオーダーによる処理) 前回のアルゴリズムの計算量を考えてみましょう。 for x in range(1, N+1): for y in range(1, N+1): if dp[y][x] == 0: co…

G - Longest Path の解説(その1)

何の話かと言うと atcoder.jpこの問題をネタにして、最短/最長経路に関する考え方を説明してみます。 経路問題の基本的な考え方 実際にはいくつかの考え方があって、問題にあわせてうまく選ばないといけないのですが、まずは、汎用性の高い考え方をおさえま…

F - LCS の解説

atcoder.jpこの問題を題材にして、DP の組み立て方(どういう思考をたどれば、この問題に適したDPの構成を思い付けるか)の例を示します。答えを知っている方が見ると、まわりくどい・・・と感じるかも知れませんが、あくまで、「まったく答えの見当がつかな…

D - ナップサック問題の解説(その3)

何の話かと言うと enakai00.hatenablog.com上記のエントリーの続きです。はい。 不要な記録をさらに削ぎ落とす(カッコよく言うと刈り込みをする的な何か) 前回の記事の最後に ちなにみ、サブタスク3と言うのは、 かつ という条件があるもので、重さが巨大…

D - ナップサック問題の解説(その2)

何の話かというと enakai00.hatenablog.com上記のエントリーの続きです。はい。 「DPの考え方」に立ち戻る 前回紹介したナップサック問題の解法は、伝統的に言い伝えられて来たものですが、ぶっちゃけ、w0 = 0,...,W のすべて条件を個別に考えるって、気持ち…

D - ナップサック問題の解説(その1)

何の話かというと atcoder.jp(とある事情があって)「DP(動的計画法)の心」がうまく伝わるように説明したいですよねぇ・・・・という会話をしていて、まずは、古典的なナップサック問題を例に取り上げましょうか・・・と思って、適当な過去問を探していて…

E -Mod i の解説

何の話かというと atcoder.jp(とある事情があって)競技プログラミングの過去問をいろいろ調べていたところ、上記の問題に遭遇して、(公式解説もチラ見しながら)なんとか Accept されるコードにたどり着いたのですが、この問題、かなり色々な要素(テクニ…

「[改訂新版]ITエンジニアのための機械学習理論入門」が発売されます

[改訂新版]ITエンジニアのための機械学習理論入門作者:中井 悦司技術評論社Amazon 2015年に初版が発行された「ITエンジニアのための機械学習理論入門」の改訂版が発売されることになりました。2021年7月17日より一般販売がはじまる予定です。カバーする範囲…

Category Theory in Context - Exercise Solutions (Chapter 3)

Category Theory in Context (Aurora: Dover Modern Math Originals)作者:Riehl, EmilyDover PublicationsAmazon 3.1 Limits and colimits as universal cones 3.2 Limits in the category of sets 3.3 Preservation, reflection, and creation of limits an…

Category Theory in Context - Exercise Solutions (Chapter 2)

Category Theory in Context (Aurora: Dover Modern Math Originals)作者:Riehl, Emily発売日: 2016/11/16メディア: ペーパーバック 2.1 Representable functors 2.2 The Yoneda lemma 2.3 Universal properties and universal elements 2.4 The category of…

Category Theory in Context - Exercise Solutions (Chapter 1)

Category Theory in Context (Aurora: Dover Modern Math Originals)作者:Riehl, EmilyDover PublicationsAmazon 1.1 Abstract and concrete categories 1.2 Duality 1.3 Functoriality 1.4 Naturality 1.5 Equivalence of categories 1.6 The art of the di…