（この記事の続き↓） politeness.hatenadiary.com前回の記事に引き続き、以下のコンテストで出題された問題を使ってDPに慣れていこう。atcoder.jp D . Knapsack 1 問題個の品物があります。 品物にはと番号が振られています。 各について、品物の重さはで、…

はじめに（別に読まなくて良い） 私がAtCoderを始めたのには2つの理由がある。ひとつは友達に勧められたからである。芯がない男なので勧められたものはやる。当たり前だ。もうひとつは、Pythonに慣れたかったからである。元々私は機械学習に興味がありKaggle…

動的計画法というものがあるという噂を聞いた。あまり詳しくはない*1が、簡単な漢字のみで構成されているのでまあ余裕であろう。この記事を書く上で以下の記事を大いに参考にした。Viva インターネッツ。qiita.com 動的計画法とは ja.wikipedia.orgWikipedia…

LRUキャッシュ 計算時間を短縮したいときに使えるテクニック。ある引数に対する計算結果を保存しておいて、同じ引数の計算を行うときに以前の計算結果を再利用することを言うらしい。 メモ化再帰と同じことかな? from functools import lru_cache #上手くい…

(前回の記事↓の続きです)politeness.hatenadiary.com上に貼った記事の中で1つ、挑戦しようとしたが「難しくね？」と思い直し一旦保留にしていた問題があった。それがABC176-D問題である。問題自体は後ほど掲載するとして、この問題ではBFS(幅優先探索)の中で…

AtCoderをやっていく上で必ずぶつかるのがこのBFS。グラフ探索の手法である。ここでは原理の復習から実装までを行う。なおこの記事を書く上で以下の記事をものすごく参考にさせてもらった。ほんま感謝やでえ。qiita.com BFSの動作 BFSは重みなしグラフ(もし…

ABC172のE問題は次のような問題であった。 以上以下の整数からなる長さの数列 との組であって、以下の条件をすべて満たすものの個数を求めてください。 なる任意のについて なる任意の について かつ ただし、答えは非常に大きくなる可能性があるので、で割…

本題の前に世界で一番どうでも良い報告 この記事以降、ですます調はやめます。 見ず知らずのあなたに敬語を使うことに疑問を持ってしまいました。 敬語好きの方には申し訳ないですが、悪しからず。 この記事について 「これもう2度と使わないだろ」って手法…

どんな問題も入力を読み込めなければ何も始まりません。 標準入力の受け取り方を状況ごとにまとめます。 1つの文字列をstr型で受け取る 標準入力を受け取る際にはinput関数を用います。 #入力:apple a=input() 1つの整数をint型で受け取る #入力:13 a=int(in…

はじめるきっかけ 先日、友達と話している時に お前の学科でAtcoder*1をやっていないのはお前だけだ ということを言われました。長い物には巻かれよ、右へ倣え、権威主義、といった言葉を信条に生きてきた僕としては見逃せません。以前からプログラミング力…