No.944 煎っぞ! - yukicoder 問題概要 をいくつかに区切ってすべての区間和を等しくするとき、区切った区間数の最大値を求めよ。 解法 Writer解とは違うアプローチをしたので軽く解説する。 まず、最も左の区間を決め打ちすると、その区間は全部で 個存在す…

Minimum(Maximum) Scalar Product 与えられた つの実ベクトル に対して適当な を選び、 を最小・最大化する問題。解法は、最小の場合は をそれぞれ昇順、降順に、最大の場合は をそれぞれ昇順にソートするだけである。 蟻本に証明が載っているが、ちょっとだ…

はじめに 木の最大マッチングとは、直接辺で結ばれたいくつかの 頂点の組 ( 「ペア」と呼ぶ ) からなる集合であって、どの頂点も高々 つのペアに属するようなもののうち、もっともペアの多いものを言う。ここでは、木の最大マッチングが、再帰的に葉を選ぶこ…

No.10 ＋か×か - yukicoder 問題概要 列に並んだ数列 を順番を変えずに加法・乗法で結び、 に等しくなるように式を作る。ただし演算は左から順に行うものとし、辞書順最小の演算子列を求める。 解法 文字列を持ってDP。計算量がちょっとだけ大きいがまあ間に…

No.9 モンスターのレベル上げ - yukicoder 問題概要 味方モンスター(レベルはそれぞれ )を以下の方法でレベル上げするとき、各味方モンスターのレベル上げ最大回数の最小を求める。 最初に、円形に並んだ敵モンスターの始点を定める。 始点から順(添字の昇順…

No.6 使いものにならないハッシュ - yukicoder 問題概要 で素数の連続部分列のうち、桁和ハッシュ( 桁になるまで行う)が衝突しない最大のものを求めよ。 解法 しゃくとり実装面倒だったのでズルをした。素数の個数が対数オーダー、かつハッシュがたかだか 種…

No.2 素因数ゲーム - yukicoder 問題概要 からはじめて、二人交互に、素因数を一つ決めて任意回数ずつ割っていく。先に にした人の勝ち。 解法 典型。素因数分解した後、NimのXOR判定条件を用いる。 struct Factor { inline vector<ll> factorize(ll N) { vector<ll></ll></ll>…

今日から、yukicoderの星 〜 を全埋めしていこうと思います。 No.1 道のショートカット - yukicoder 問題概要 辺のコストが費用、距離の つあるDAGにおいて、費用が 以下になるように頂点 から頂点 へ移動する(距離の)最短経路を求める。 解法 典型。状態 (…