けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

LIS

Codeforces Round #617 (Div. 3) E2. String Coloring (hard version)

これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…

yukicoder No.979 Longest Divisor Sequence

LIS の亜種だけど、雰囲気違って面白い! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…

Chokudai SpeedRun 002 L - 長方形 β (600 点)

面白かった 問題へのリンク 問題概要 個の長方形がある。各辺の長さは整数値である。 この長方形から何個か選んでマトリョーシカを作りたい。最大で何重にできるか? 長方形の縦と横をひっくり返してもよい。 制約 考えたこと もし長方形が縦横ひっくり返す…

AtCoder AGC 032 D - Rotation Sort (1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

AtCoder ABC 006 D - トランプ挿入ソート

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…

AOJ 2941 LISum (RUPC 2019 day1-E)

最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…