お題箱より。 Aizu Online Judge 解法 実は過去の解説記事に類題があります。 Educational Codeforces Round 17 D. Maximum path - ARMERIA Codeforcesの問題は最大化でAOJの問題は数え上げという違いはありますが、解法はほぼ同じです。 左上から右下に向か…

お題箱より。 No.1460 Max of Min - yukicoder 解法 この問題の解法はいくつかのステップで構成されていて、その1つ1つが覚えておくと有用なテクニックだと思います。順に追っていきましょう。 ステップ1 求めたい値 は、与えられた数列の要素に対して と を…

お題箱より。 F - Coprime Present 解法 互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。 集合 とします。求…

A - AtCoder Ad 得点率97.4％で130位でした。 seed値0の入力に対する解のビジュアライザ出力です。 考察 スコアの計算式を見ます。各企業が指定する1マス（以下、指定マスと呼びます）を含めないとその企業からの点は貰えないので、まずこれは含める必要があ…

お題箱より。 C - N!÷K番目の単語 解法 ※この解説の「何番目」という表記は全て1-indexedです。 一般に を 以上 以下の整数として、 個の順列のうち辞書順で 番目にあるものを、前の要素から順番に求めていく方法を考えます。 最初の要素は、 個の順列を辞書…

このたび、マイナビ出版から発行される「アルゴリズム実技検定 公式テキスト（エントリー～中級編）」の執筆をさせていただきました。kenkooooさんとの共著です。 アルゴリズム実技検定 公式テキスト[エントリー~中級編] (Compass Booksシリーズ)作者:岩下 …

B - -- - B 解法 ある整数 を作ることが可能か判定するときには、 を最小のコストで作る操作列だけを考えれば十分です。作りたい整数を最小のコストで作る操作列が、何らかの限定的な特徴を持つことを見つけられると非常に見通しが良くなります。 その特徴を…

お題箱より。 E - Independence 解説 問題文をグラフ理論の言葉で解釈します。 個の頂点を2つの集合 に分け、それぞれの集合内では任意の2頂点間に辺が存在している（すなわち、クリークになっている）必要があります。 の頂点数をそれぞれ とすると、最小化…

お題箱より。 E - Sequence Matching 解法 LCSとの類似性 2つの数列や文字列を操作して一致させる問題では、前から1文字ずつ扱いを決めていくという方針のDPがうまくいく場合があります。特に2つの列の長さを として が間に合う場合はなおさらです。 このよ…