なぜｄｐ「やるだけ」なのか ～動的計画法について考える その１～ - kuuso1のブログ
これは、Competitive Programming Advent Calendar 2016の17日目の記事です。 競技プログラミング（以下，競プロ）においてよく出題される動的計画法（Dynamic programming，通称dp）について，「dpやるだけ」という表現を稀に見かけます．競プロを始めた人のうち，多くの人が（少なくとも自分にとっては）最初の壁のうちの一つと言ってもいいdpというジャンルがなぜ「やるだけ」などというパワーワードを伴ってしまうのか．今回はそういうところから，ふわっと動的計画法について考えてみようと思います．どちらかといえばテクニック的な内容というよりは自分がdpの問題に触れるときに意識しているようなことを書いているだけなので，参考になったりならなかったりすると思いますがご容赦のほど． 動的計画法とは 動的計画法 wikipedia によると「対象となる問題を複
基礎的な動的計画法（5題） - Fuji Haruka's blog
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ いわゆる「蟻本」である。この章末で紹介されている練習問題をひたすら解いている。 今回は基礎的な動的計画法。基礎的といっても最後の問題とか難しかったから他の人の解法を見た... dpをうまく定義することと、漸化式を正しく作ること、これに尽きる。 dpを定義する着想は深さ優先探索っぽく最初は考えて、これdpにしたらどうなるの？っていう順番で考えると思いつきやすいかも。 POJ3176 Cow Bowling 3176 -- Cow Bowling 問題概要 0以上99以下の数字をピンにしてボーリングをする 例:5列のピン 7 3 8 8 1 6 2 8 4 4 4 5 2 6 5 ボールがこのピンを通過する。いちばん上から始めて、下の二つの数のどちらかに下っていき、一番下の列
回文 - Eating Your Own Cat Food
回文のアルゴリズムとか 回文の判定 反転したものと一致するかを見る def is_palindrome(s): return s == s[::-1] 回文の全列挙 文字列sに含まれる回文をすべて求める． 例えば，abracadabraには[a, b, c, d, r, aca, ada]がある． これは，すべての中心となる箇所について，文字が一致する限り左右に伸ばしていけばいい． # 文字列sの回文の集合を求める(O(N^2)) def palindromes(s): palindromes_set = set() for i in range(len(s)): # iを中心とした回文 left = i right = i while 0 <= left and right < len(s) and s[left] == s[right]: palindromes_set.add(s[l
素直なDPが普通に解けるようになってきた - はむこの勉強記録
概要 5次元だろうが、素直なDPならば結構思いつくようになったし、バグって無限時間溶かすことがなくなってきました。僕は青コーダーなんで、ほんまあまり役に立たない記事ですが、ある種の「アルゴリズム設計者の発達過程」として見てもらえれば良いです。 できるようになったこと あまりDPをバグらせない。バグっても直せる。 そもそも「こんなんDPじゃなきゃ無理ｗ」という感覚がついた（これは結構前に）。凸凹感覚というか、全探索しないといけなそうだけど2nとかn!とかで、他に解放が思いつかない場合など。隣と関係なさそう感（一番近い回文数列みたいなやつはきついよなあ）みたいなのもわかる できなかった時との比較 少し考察を眺めに取るようにした。厳密に考えるようになった。紙にきちんと数式に書くようになった。（これはDPの状態と遷移をコードに明示することともつながっていそう） デバッグ時、自分の目で経路復元をする
回文に親しもう - pixiv inside [archive]
こちらは ピクシブ株式会社 Advent Calendar 2014 の12月22日の記事です。 こんにちは、おはようございます、こんばんは、エンジニアのneo-nanikakaです。 他のエンジニアの皆さんが、Webサービスやってる会社っぽいエントリーを書いていますが、空気を読まずにWebっぽくないエントリーを書きます。趣味なんだから、仕方ないね。でもこういうのが許されるのは大変良い社風だと思います（唐突なヨイショ）。 回文について もしかしたら、回文（かいぶん）という言葉を聞いても何のことやらと思う方もいるかもしれません。回文とは、「しんぶんし」「私、負けましたわ」のように、上から読んでも下から読んでも意味が通る言葉や文を使った言葉遊びです。「山本山」も漢字のままなら回文です。西尾維新さんも「NISIO ISIN」とローマ字表記すれば回文です。 回文の言葉遊びは日本語に限った話ではなく
![回文に親しもう - pixiv inside [archive]](https://cdn-ak-scissors.b.st-hatena.com/image/square/649650be00c35aecad2db1e7f5abf8372cc4f08e/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F11696248318756278971%2F8454420450077730553%2F1419241303)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AOJ 2035 It Prefokery Pio - Algoogle
Efficient data transfer through zero copy
