めもめも

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

089 - Partitions and Inversions(★7)の解説

何の話かと言うと atcoder.jp上記の問題について、AVL 木(ソート済みのリストに対して、ソートを保った挿入・削除を で実行できるデータ構造)を用いた別解を紹介します。 再帰処理による解法 まずは直感的にわかりやすい再帰的な解法を考えます。与えられ…

081 - Friendly Group(★5)の解説

何の話かというと atcoder.jp上記の問題の別解です。公式解説 では、身長と体重を 2 次元にプロットして、身長と体重を対称に扱う解法が示されています。あえてこれらを非対称に扱うことも可能です。 身長だけの場合 仮に、身長についてだけ考えればよいとす…

074 - ABC String 2(★6)の解説

何の話かというと atcoder.jp上記の問題は、公式解説にもあるように、具体例を試しながら隠された規則性を発見する必要があります。どのような試行錯誤で、正解に至れるのか、一例を紹介します。 まずはしらみつぶし まずは、しらみつぶしで、文字列が変化す…

072 - Loop Railway Plan(★4)の解説

何の話かというと atcoder.jp上記の問題をネタに「キューを用いた全件探索」の話をします。 キューを用いた全件探索 enakai00.hatenablog.com上記の記事では、キューを用いて木構造データを探索するという話をしています。木構造データに限らず、複数の選択…

071 - Fuzzy Priority(★7)の解説

何の話かというと atcoder.jp上記の問題をネタに、「極端に小さな制約条件に注目する」という話をします。まぁ、下記のネタと似たような話です。enakai00.hatenablog.com の場合 ポイントは、 という条件です。一般には、もっとたくさんの順列が選べるはずな…

070 - Plant Planning(★4)の解説

何の話かというと atcoder.jpこの問題をネタに L1 ノルムの最小化の話をします。 L2 ノルムの最小化 平面上の点の集合 に対して、各点との「ユークリッド距離の2乗の話」 を最小にする点 は、 の条件から、与えられた点の集合の重心に一致することがわかりま…

068 - Paired Information(★5)の解説

何の話かというと atcoder.jp上記の問題をネタに、Union-find の解説と、Union-find の特徴を利用した別解を紹介します。 Union-find Union-find の基本的な実装はこちらになります。 group_parent = defaultdict(lambda:None) def create_group(x): global …

060 - Chimera(★5)の解説

何の話かと言うと atcoder.jp上記の問題の簡単な解説です。(特に捻りはありません・・・。) 単調増加部分列の長さ 基本は、与えられた数列を順番にスキャンしながら、・dp[k] = v # 長さ k の部分列を取り出した際の最後の値(の最小値)が vを更新してい…

054 - Takahashi Number(★6)の解説

何の話かと言うと atcoder.jpこの問題、公式解説では、「新たな頂点を追加してリンク数を削減する」というテクニックが紹介されています。実は、これを知らなくても、もう少し自然な発想で「本質的に同じ解法」にたどり着けるという話をします。 基本的な考…

043 - Maze Challenge with Lack of Sleep(★4)の解説

何の話かと言うと atcoder.jpこの問題をネタに「重み0のリンクで結合されたノードを同一視する」という話をします。 一般的な解法 まず、この問題の一般的な解法は、01-BFS になります。方向転換を考慮する必要があるので、座標 (x, y) + 方向(上下方向 or …

040 - Get More Money(★7)の解説

何の話かと言うと atcoder.jpこの問題、公式解説では、最小カット問題(=最大フロー問題)に帰着して、Dinic 法で解くという解法が紹介されていますが、もうちょっと素朴な「ナップサック問題」としても解ける(解けた)ので紹介します。 ナップサック問題…

039 - Tree Distance(★5)の解説

何の話かと言うと atcoder.jpこの問題をネタに、「頂点についてのループと辺についてのループ」の話をします。・・・・というのは、ちょっと無理矢理感があって、ぶっちゃけは、別解を紹介したいだけです。 辺についてのループ 一般に、グラフの問題は、「N …

029 - Long Bricks(★5)の解説

何の話かと言うと atcoder.jpこの問題をネタにして、条件によってアルゴリズムを場合分けする、という話をします。 2つの解法 まず、この問題の模範解答は「遅延評価セグメント木」を使った解法になります。詳しくは、公式解説を参照してください。一方、も…

021 - Come Back in One Piece(★5)の解説

何の話かと言うと atcoder.jpこの問題をネタに、「(閉路を含む)有向グラフの深さ優先探索」の実装方法に関する話をします。問題の解法については公式解説に譲りますが、解法の中で「強連結成分分解」が使われており、これを実装する際に、「(閉路を含む)…

017 - Crossing Segments(★7)の解説

何の話かと言うと atcoder.jp上記の問題をネタに、計算量の観点から解法を考える、という話をしたいと思います。 問題の内容 問題では、円周上の点になっていますが、点 1 のすぐ左で切って円を開けば、1 〜 N の区間に複数の区間 (-----) がばら撒かれてお…

009 - Three Point Angle(★6)の解説

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

008 - AtCounter(★4)の解説

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

006 - Smallest Subsequence(★5)の解説

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

003 - Longest Circular Road(★4)の解説

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

002 - Encyclopedia of Parentheses(★3)の解説

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

E - Shiritori の解説

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

D - Send More Money の解説

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

D - RGB Coloring 2 の解説

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

D - Cooking の解説

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

Union-find をグラフ探索で代替できる例

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

Q - Flowers の解説

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

P - Independent Set の解説

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

M - Candies の解説

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

N - Slimes の解説

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

L - Deque の解説

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