何の話かと言うと atcoder.jp上記の問題をネタに、バイナリーサーチの基本的な書き方を説明します。 問題の考え方 原点となる点を決めて、全体を平行移動した後に、それぞれの点の偏角（x 軸に対する 0 〜 360°の範囲の角度）を求めます。すると、任意の２点…

何の話かと言うと atcoder.jpこの問題を例にして、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」系の話をします。 どういう事？ この問題では、「atcoder」という物凄く具体的な 7 文字を取り出す事…

何の話かと言うと atcoder.jp上記の問題をネタに「ギリギリ間に合う系」、もしくは、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」系の話をします。 実行時間の見積もり PyPy3 での実行時間を調べて…

何の話かと言うと atcoder.jp「トポロジカルオーダーで処理する」系の問題例としてこちらを紹介します。この問題では、無向グラフを取り扱います。有向グラフの例については、下記の記事が参考になります。enakai00.hatenablog.com 考え方 ノード数 N に対し…

何の話かと言うと atcoder.jp上記の問題をネタにキューを使った再起処理の基本を説明します。 キューを使った再起処理 公式解説では、 通りのすべての組み合わせから条件に合うものを抽出する方法が説明されていますが、再帰処理を用いて条件に合うものだけ…

何の話かと言うと atcoder.jpこの問題をネタに「トポロジカルオーダーで処理する」パターンの例を紹介します。トポロジカルオーダーで処理する話については、まずは、下記の記事を参照してください。enakai00.hatenablog.com 考え方 上記の記事では、「始状…

何の話かと言うと atcoder.jpこの問題をネタに「しらみつぶし」系のコードの書き方のパターンを紹介します。 候補のリストをメンテナンスする 上記の問題、公式解説では、「0 〜 9 を重複なく割り当てられる文字は最大でも10種類なので、10! 通りを端から順…

何の話かと言うと atcoder.jp上記の問題をネタに、（木構造とは限らない）単純無向グラフの基本的な取り扱いを説明します。単純無向グラフは、多重リンクや自分から自分へのリンクを含まない無向グラフです。一般には、複数の連結成分に別れます。 データの…

何の話かと言うと atcoder.jp上記の問題をネタに、ナップサック問題の計算量に関するちょっとした考察をしてみます。 「しらみつぶし」がナップサック問題の基本 問題をパッとみて、ナップサック問題に似ていますよね。まず、下記の記事で、ディクショナリー…

何の話かと言うと 要素をグループ分けする問題で、よく Union-Find がテクニックとして取り上げられますが、もうちょっと単純に、同じグループの要素に双方向リンクを貼っていって、最後に、グラフ探索で同じグループの要素をまとめるという手法で間に合う場…

何の話かと言うと atcoder.jpこの問題をネタにして、「ソートされたリストへの挿入位置をバイナリーサーチで高速に検索する」というテクニックを紹介します。ぶっちゃけ、これ難問かも？ ナップサック問題との類似性で考える 「花を取り除く」という立て付け…

何の話かと言うと atcoder.jpこの問題をネタに、木構造データに関する問題の基本を説明します。（DPというよりは、木構造データの取り扱いがメインの問題ですね。） 木構造データの取り扱い データとして与えられるのはノード間のリンク情報のみで、どちらが…

何の話かと言うと atcoder.jp上記の問題は、「前のループで事前に計算できる部分を見つける」というちょっとした工夫で高速化ができるよく知られた問題です。「子供に飴を配る」という立て付けですが、端的には、・ という条件の下に、 を満たす の組み合わ…

何の話かと言うと atcoder.jp「区間DP」でうまく解ける問題の例として、こちらを紹介します。 区間DPとは？ 「一列にならんだもの（A[1],..., A[N]）を操作する系」の問題で、特定範囲 A[i] 〜 A[j] に制限した場合の答えを dp[i][j] とした上で、幅 d = j -…

何の話かと言うと atcoder.jpこの問題をネタにして、対戦ゲーム（マルコフ決定過程）のちょっとだけ応用的な考え方を説明します。基本的な考え方については、まずは、こちらの記事をご確認ください。enakai00.hatenablog.com 状態価値関数の一般的な定義 自…

何の話かと言うと 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 されるコードにたどり着いたのですが、この問題、かなり色々な要素（テクニ…