問題概要 (A[i]*k, B[i])(k in [1,inf) i in [1..N( 解法 優先順位付きキューから取り出しては時間を進めて再び突っ込んでいく。

問題概要 循環小数が与えられる。ただし循環の単位は分からない。分母が最小になるように有理数で表す問題。 解法 反復単位がどうなってるか全探索する。制約がよく分からなかったので多倍長で。

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

問題概要 コインがN( 解法 (何枚目まで見た、いくら)を組にして必要な最小枚数でDP。よくある01ナップザック。

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

問題概要 W*W(W 解法 もっとも愚直にやるとW^4。両端を固定して考えるとW^3で、通すだけならこれで十分。実はW^2で解くことができる。各行について蟻本p280の問題に落とせばよい。

問題概要 ナップザック。

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

問題概要 いわゆる連鎖行列積。復元もあり。 解法 [from, to)型のDPの典型例。

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

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

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

問題概要 8円のコーラをN( 解法 動的計画法。dp[i本買った][残り1円][残り5円][残り10円]=最小枚数とすると状態数が多くてTLEしそう。残り硬貨の枚数を全部覚えておく必要はなくて、2種類について枚数が分かれば残りの枚数は引き算で求められる。これで状態…

問題概要 N

問題概要 キング+上下に動くようなクイーンに対して、Nクイーンが何通りあるか求める問題。いくつかのクイーンは配置が指定されている。 解法 ごくごく素直なDPだとO(N^3)。?のとき全部に配るのを止めて、全体に配って近くだけ差っ引くというやりかたをすれ…

問題概要 LIS。N 解法 練習のつもりでO(N*log N)解を書く。入力の変換が最も面倒。

問題概要 整数の集合A,B(濃度はいずれも100以下)がある。A、Bからいくつかの要素を除いて、Bの任意の要素がAのどの要素の倍数にもなっていないようにしたい。最小でいくつ取り除く必要があるか求める問題。 解法 二部グラフを構成すると、求めるものは最小点…

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

問題概要 ノード数N( 解法 ICPCの国内予選に出たAnd Then. How Many Are There?に似てる。ビットDPするだけ。

問題概要 長さL( 解法 strとrev(str)のLCSを計算する。LCSに含まれない部分だけを追加すればよい。LCSの復元の方法はちゃんと文字が一致するかどうか確かめないと駄目。

問題概要 N( 解法 部分和問題のNが大きい番。半分全列挙は使えないが、値が小さいのでDPで作ることのできる部分和を全て求める。

問題概要 長さL(最長共通部分列を求める問題。 解法 片方の数列に現れる順序で数字に番号を振りなおして、もう片方の数列で最長増加部分列を求めればよい。

問題概要 N

問題概要 4近傍でflood fillして池の数を数える問題。

問題概要 長さN(sign[i]*A[i] = Fとなるような符号の付け方に関して、一意に定まるものは正か負かを、定まらないものはその旨出力する。どうやってもできないときはその旨出力する。 解法 今いくつの数字を持っているかをキーにしてDP。詳細はコード参照。 …

問題概要 N*N(N 解法 前処理で累積和を持っておいて全探索する。トーラス云々は4倍にしたテーブルの上でやっておけば特に意識せずに処理できる。計算量はO(N^4)で危ないがそんなに複雑な処理をしてるわけではないので何とか間に合う。

問題概要 長さN( 解法 余りの値といくつ使ったかを見ながらDP。オーバーフローや、値の重複に注意すること。

問題概要 都市がN( 解法 (i日目、どの都市にいるか)を状態のキーにしてDPするだけ。

問題概要 D(入れ子にして最大いくつ詰めることができるか求める問題。どの順に積めるかも出力する。 解法 ソートして順序を適切に定めた上でLIS。

問題概要 長さN( 解法 連続する区間を残すので[from, to)型のDP。 入力がファイル読み込みって書いてあったけど実際は標準入力からの読み込みだった。