問題概要 重さw[i]、価値v[i]の商品がC( 解法 どの商品が中央値にくるかを全探索する。その商品以下の価値からN/2個、それ以上からN/2個選ぶときは重さの小さいものを貪欲に選べばよいので、これはheapを使えば前処理で効率的に計算しておくことができる。

問題概要 山がN個あって各山には石がいくつか置かれている。ふたりでゲームを行う。各プレイヤーは山を一つ選び、石を1個以上取り除く。また、その山に残っている任意個の石を他の山に移すことができる。この際移す山の対象はいくつあってもよい。最後の石を…

問題概要 片方のサイズ26以下の二部グラフが与えられる。完全マッチングを作るときに一位に定まるものを出力する問題。 解法 全てのペアに対して、一度固定してから残りを使って完全マッチングができるかどうかを判定すればよい。二部マッチングは差分のみ計…

問題概要 3色のビーズを使って数珠が何通り作れるか求める問題。 解法 とりあえず反転を無視して回転対称だけ重複を取り除いた個数をx個とする。これは蟻本で紹介されてる問題そのもの。左右対称な個数をr個とすると、求める個数は(x - r) / 2 + rとなる。左…

問題概要 長さQ( 解法 いろいろ解き方があるらしい。 自分のやり方は、各区間をpriority queueに突っ込んで、貪欲っぽく選んでいく。ただし計算量はよく分かっていない。 蟻本にはsegtreeやバケット法を使う問題として取り上げられていた。(よく分からない) …

問題概要 ジョブがN(区間に分割してバッチをいくつか作る。バッチは前から順に起動され、起動する際にS( 解法 コストの式は線形なので分割して考えることができる。後は単純なDP。式は大雑把にはdp[i] = min_{i

問題概要 Permutation(N, M)の末尾の0を取り除いたとき最下位の桁の数がいくつになるか求める問題。N 解法 2と5を分けて考えれば単なるmod 10での計算になる。2と5を全て取り除いた上での積を計算しておけばいいのだが、累積積とかを計算しようとするとMLEす…

問題概要 凸とは限らない多角形が与えられる。多角形の外側に多角形からの距離がL以上離れた囲いを作りたい。囲いの長さは最小いくつにできるか求める問題。 解法 凸包を構成して周の長さに2*L*PIを足すだけ。コード略。

問題概要 カレンダーを1日進めるか1ヶ月進めるか選ぶことができる。ふたりで交互に手を選んだとき、自分の番で特定の日付に遷移できるかどうか判定する問題。 解法 基本的には典型的なゲーム木探索。日付の存在判定なんかは適当に頑張る。サイズが小さいので…

問題概要 数字のペアの列(長さN 解説 某所で日本語解説を見てしまっていたので殆ど自分で考えずに解いてしまった。 Dilworthの定理より、最小パス被覆を求める代わりに最大反鎖のサイズを求める。これはペアをソートした後第二要素の最長狭義減少列を求めれ…

問題概要 ある数aがb個ある。それぞれの数を分割する作業を繰り替えした結果が与えられる。aとして考えられる最小値を求める問題。 解法 探索で頑張る。 長い順に調べた方が枝刈りしやすそうであることは直感的に分かる。 最初は、長い順に元はどの木片であ…

問題概要 1*1, 2*2, ..., 6*6の板を6*6マスの盤に埋め込む。盤は最小いくつ必要か求める問題。 解法 だいたい直感通りに貪欲に詰めていく。こういうのは場合分けを減らしたいんだけど難しい。

問題概要 K個のポストがある。ポストを壊すのに爆弾が最低いくつ必要かをしりたい。最低爆弾をいくつ用意する必要があるか求める問題。 解法 状態を(残りポスト、下限、上限)としてDP。

問題概要 N

問題概要 人がN( 考えたこと 速い順にソートする。1番速い人と2番目に速い人の位置とライトの位置とそれ以外の人が何人残っているか、という4つの組を状態としてメモ化再帰する。3番目以降の人の動かし方は、遅い方から動かしていけば良い。

問題概要 Crossing Riverの類題

問題概要 モールス信号を使った簡単な暗号をデコードする問題。 解法 ルールに従って実装するだけ。

問題概要 置換σ(N 解法 各iについて、何乗したら戻ってくるかを求めてそれの最小公倍数が答えになる。

問題概要 長さL( 解法 愚直だとO(N^2 * L)かかるが、DPの状態をあまり時間のみにすることで計算量をひとつ落とせる。

問題概要 牛がN( 解法 夏合宿10とかSRMとかで出たタイプの貪欲。i->jの場合とj->iの場合の損失の式を比べると、-T[j]*D[i] jの順に処理した方がよいことが分かる。あとはこれをキーにしてソートするだけ。

問題概要 長さL( 解法 rotateさせる系の問題は同じものをつなげるのが定石。このときsuffix arrayを構築してやればよい。複数あるとき最小のものを答えたいので末尾に大きい値を加えておく。

問題概要 最長共通部分文字列の長さを求める。文字列長 解説 連結した文字列のLCPを用いる。コード略。

問題概要 文字列S,T(長さ10^5以下)が与えられる。number {(i,j,k) | k>=K,S[i,k]=T[j,k]}を求める問題。 解法 f(X)をnumber {(i,j,k) | k>=K, i!=j, X[i,k]=X[j,k]}とする。このときf(S$T)-f(S)-f(T)を返せば良い。なのでf(X)について考える。 f(X)はLCPから…

問題概要 長さN( 解法 答えに関して二分探索する。あらかじめXをソートしておけば差がある値以上になる組み合わせの個数を二分探索でO(N*log N)で求められるようになる。

問題概要 平均値の最大化。

問題概要 重み付き区間スケジューリング問題。 解法 DP。

問題概要 長さN( 解法 重さと力の和が大きいやつから順に並べれば良い。

問題概要 平面上にN( 解法 ビットDP。3点以上が角にくるような長方形がコーナーケースで前処理をかけておく必要がある。

問題概要 ノード数V( 解法 DAGなのでDP。スタックオーバーフローするので再帰は避ける。

問題概要 スライド最小値。定数倍厳しい。