2021-01-01から1年間の記事一覧
何の話かと言うと atcoder.jpこの問題をネタにして、対戦ゲーム(マルコフ決定過程)の基本的な考え方を説明します。 「負け状態」と「勝ち状態」の非対称な関係 自分の手番の状態 k における状態価値関数の値を dp[k] とします。・・・状態価値関数って何?…
何の話かと言うと enakai00.hatenablog.comこちらの記事の続きです。 改善のヒントは・・・? 前回の最後に、参加する男性を1人ずつ増やすという発想で、DPの実装に成功しました。しかしながら、まだ実行時間が長すぎるので、さらなる工夫が必要です。前回の…
何の話かと言うと atcoder.jp上記の問題をネタに・・・うーん。これ、個人的には、「いやよくこんな方法思いついたな」系で、あまりパターン化できないんですが、とりあえずは、できるだけ天下り的な説明はさけて、論理的に正解に近づいていく方法で説明して…
テンプレートに慣れるための問題 以下の問題について、DP のテンプレートに従ってコードを書いてください。また、それぞれの計算量( など)を答えてください。[テンプレート] # N: データ数 dp = [None] * (N+1) dp[1] = xxxx # 1個の場合の答えを自力で考…
何の話かと言うと enakai00.hatenablog.com上記の記事では、「桁DP」について、下から攻める方法と、上から攻める方法を紹介しました。今回は、「上から攻めないとうまくいかない」問題例として、こちらを取り上げます。atcoder.jp 何が難しいの? 問題のパ…
何の話かと言うと enakai00.hatenablog.comこちらの記事の続きです。 一般の K に拡張する 前回は、K = 99999 と言った(各桁が 0 〜 9 を回る)キリのよい数字という前提で問題を解きました。今回は、K = 38463 と言った一般の場合を考えます。この場合は、…
何の話かと言うと atcoder.jpこの問題をネタにして、「桁DP」の考え方を説明します。なお、問題文では「1 以上 K 以下の整数」となっていますが、この手の問題では、0 を含めて計算する方が簡単なので、「0 以上 K 以下の整数」として問題を解いておき、得ら…
何の話かと言うと enakai00.hatenablog.com前回の続きです。 ノードを消していく発想(もしくは、トポロジカルオーダーによる処理) 前回のアルゴリズムの計算量を考えてみましょう。 for x in range(1, N+1): for y in range(1, N+1): if dp[y][x] == 0: co…
何の話かと言うと atcoder.jpこの問題をネタにして、最短/最長経路に関する考え方を説明してみます。 経路問題の基本的な考え方 実際にはいくつかの考え方があって、問題にあわせてうまく選ばないといけないのですが、まずは、汎用性の高い考え方をおさえま…
atcoder.jpこの問題を題材にして、DP の組み立て方(どういう思考をたどれば、この問題に適したDPの構成を思い付けるか)の例を示します。答えを知っている方が見ると、まわりくどい・・・と感じるかも知れませんが、あくまで、「まったく答えの見当がつかな…
何の話かと言うと enakai00.hatenablog.com上記のエントリーの続きです。はい。 不要な記録をさらに削ぎ落とす(カッコよく言うと刈り込みをする的な何か) 前回の記事の最後に ちなにみ、サブタスク3と言うのは、 かつ という条件があるもので、重さが巨大…
何の話かというと enakai00.hatenablog.com上記のエントリーの続きです。はい。 「DPの考え方」に立ち戻る 前回紹介したナップサック問題の解法は、伝統的に言い伝えられて来たものですが、ぶっちゃけ、w0 = 0,...,W のすべて条件を個別に考えるって、気持ち…
何の話かというと atcoder.jp(とある事情があって)「DP(動的計画法)の心」がうまく伝わるように説明したいですよねぇ・・・・という会話をしていて、まずは、古典的なナップサック問題を例に取り上げましょうか・・・と思って、適当な過去問を探していて…
何の話かというと atcoder.jp(とある事情があって)競技プログラミングの過去問をいろいろ調べていたところ、上記の問題に遭遇して、(公式解説もチラ見しながら)なんとか Accept されるコードにたどり着いたのですが、この問題、かなり色々な要素(テクニ…
[改訂新版]ITエンジニアのための機械学習理論入門作者:中井 悦司技術評論社Amazon 2015年に初版が発行された「ITエンジニアのための機械学習理論入門」の改訂版が発売されることになりました。2021年7月17日より一般販売がはじまる予定です。カバーする範囲…
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 (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 (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…