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

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

トップ > そのまま覚えたいシンプル設定の中堅以上の典型問題

そのまま覚えたいシンプル設定の中堅以上の典型問題

JOI 本選 2019 C - たのしいたのしいたのしい家庭菜園 (AOJ 0660, 難易度 9)

JOI本選 AOJ 文字列 操作:swap 操作 最小回数・最小個数を求める Yes/No判定問題 累積和 DP 前処理 操作:隣接swap 最小コスト JOI DP状態:吸い出しと吸い込み JOI難易度9 要素の並び替えを管理するDP そのまま覚えたいシンプル設定の中堅以上の典型問題 最適化問題

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない…

JOI 予選 2019 E - イルミネーション (AOJ 0656, 難易度 7)

DP DP高速化 DP高速化:累積和 累積和 シーケンシャルDP 区間 区間分割型シーケンシャルDP AOJ AtCoder JOI予選・二次予選 JOI JOI難易度7 累積max 制約条件:区間 区間ソート そのまま覚えたいシンプル設定の中堅以上の典型問題 最大スコア 解空間:O(2^N)通りの選択肢 制約条件:共演NG 最適化問題

区間についてどうのこうのする問題、大抵は DP！ 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …

AOJ 2336 スプリング・タイル (JAG 夏合宿 2010 day2-G) (600 点)

二次元グリッド 二分探索 方程式 期待値 期待値DP コーナーケース AOJ AOJ-ICPC600点 JAG AOJ-ICPC JAG夏合宿 ワープ 回数の期待値 そのまま覚えたいシンプル設定の中堅以上の典型問題 最適化テク:探索候補を絞る 迷路 壁マス 浮動小数点型を扱う問題

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

平方分割 二部グラフ Union-Find グラフ シーケンシャルDP DP 個数重複も考慮したナップサックDP DP値を利用して状態復元 AOJ JAG AOJ-ICPC600点 テク:総和がNになる整数組の種類数はO(√N) 下駄を履かせて負辺除去 AOJ-ICPC JAG春冬コン 均等に分ける そのまま覚えたいシンプル設定の中堅以上の典型問題 中堅以上の典型要素を詰め合わせた教育的問題 思わず解きたくなる興味深い良問

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

AtCoder ARC 081 E - Don't Be a Subsequence (黄色, 600 点)

部分列 部分列DP 辞書順 復元 文字列 AtCoder ARC-E AOJ-ICPC600点 黄色diff 「次の要素」へのポインタを求める そのまま覚えたいシンプル設定の中堅以上の典型問題 DP

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制約 1 <= |A| …

AOJ 2891 な◯りカット (AUPC 2018 day3 C)

なもりグラフ グラフ BFS データ構造 Greedy queue 後退解析 AOJ ACPC DFS 【問題集】DFS・BFSのステップアップ そのまま覚えたいシンプル設定の中堅以上の典型問題 サイクル サイクル検出

サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことを、なもりグラフと呼ぶことにする。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに…

CODE THANKS FESTIVAL 2017 H - Union Sets (600 点)

Union-Find 永続化 部分永続Union-Find 並列二分探索 二分探索 クエリ処理問題 データ構造 クエリ先読み クエリの平方分割 平方分割 マージテク AtCoder unrated公式コン AtCoder600点 Union-Findのマージ過程を表す木を考える そのまま覚えたいシンプル設定の中堅以上の典型問題

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみた！ 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになったか…

AtCoder ABC 091 D - Two Sequences (ARC 092 D) (黄色, 500 点)

各桁ごとに見る XOR 主客転倒 累積和 前処理 条件の言い換え 総和を求める ABC-D AtCoder AtCoder500点 解空間:O(N^2)通りの選択肢 二分探索 二分探索:lower_bound 0と1の問題 各桁がある値を持つ条件を大小関係に関する条件に言い換える ARC-D 黄色diff そのまま覚えたいシンプル設定の中堅以上の典型問題

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

AtCoder ARC 102 E - Stop. Otherwise... (橙色, 700 点)

数え上げ問題 包除原理 戻すDP 二項係数 DP 重複組合せ AtCoder700点 AtCoder ARC-E 数列 グラフ・盤面・数列の個数の数え上げ 橙色diff 制約条件:総和=K サイコロ 入力が定数個 そのまま覚えたいシンプル設定の中堅以上の典型問題

いろんな解法がありそうなんな 問題へのリンク 問題概要 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で通した解法) …

AtCoder ABC 102 D - Equal Cut (ARC 100 D) (青色, 600 点)

しゃくとり法 ある量を固定して考える 全探索 3つのものの真ん中に着目する 数列 前処理 二分探索 累積和 最大値と最小値の差を扱う問題 ABC-D AtCoder AtCoder600点 累積和テク:左右両端からの累積和や累積結果を前処理 青色diff ARC-D 均等に分ける そのまま覚えたいシンプル設定の中堅以上の典型問題 中堅以上の典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題 最小コスト 最大スコア 累積和テク:累積和や累積結果を前処理しておく 【問題集】累積和 最適化問題

かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…

AOJ 2224 Save your cat (JAG 夏合宿 2010 day4-C) (500 点)

グラフ 最小全域木 マトロイド 計算幾何 平面グラフ 条件の言い換え AOJ 二次元平面上のN点の問題 AOJ-ICPC500点 JAG JAG夏合宿 AOJ-ICPC 全域木を考える 個人的要復習 思わず解きたくなる興味深い良問 そのまま覚えたいシンプル設定の中堅以上の典型問題 浮動小数点型を扱う問題

これ面白い！！！！！！！！ 好き！！！！！！！ 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいくつ…

みんなのプロコン 2018 決勝 A - Uncommon (包除原理)(600 点)

数え上げ問題 包除原理 各kに対して 数学(整数問題) バケット 調和級数 約数系包除 前処理 AtCoder unrated公式コン AtCoder600点 制約:数値が10^6以下 エラトステネスの篩 添字GCD畳み込み 高速メビウス変換 メビウス関数 そのまま覚えたいシンプル設定の中堅以上の典型問題 メビウスの反転公式

という制約の意味に気がつくのにかなり時間がかかった。これのおかげで「 の中に の倍数が何個あるか」というのが、 ではなく でできる。 問題へのリンク 問題概要 個の相異なる整数 と、整数 が与えられる。各 に対して、 のうち と互いに素なものが何個あ…

AtCoder AGC 005 D - ~K Perm Counting (赤色, 900 点)

数え上げ問題 包除原理 DP シーケンシャルDP AtCoder AtCoder900点 AGC-D FFT 特殊なmod 赤色diff DEGwerさんの数え上げテクニック集の例題 順列の数え上げ 順列を題材とした問題 そのまま覚えたいシンプル設定の中堅以上の典型問題

包除原理勉強会の一環。なんか最初、0〜N-1 を 2K で割った余りで類別したところで鎖を作って、そこでのサイズ i のマッチングの個数を数えたりしたのだけど、それをマージするのに NTT を使うとか血迷った^^; https://beta.atcoder.jp/contests/agc005/subm…

CS Academy 081 DIV2 E - Fold Polygon

最小全域木 グラフ 密グラフ 解空間:O(N!)通りの選択肢 復元 計算幾何 条件の言い換え 操作 CSAcademy 最小コスト 操作:2つのものを1つにマージ 全域木を考える マルチテストケース問題 多角形 そのまま覚えたいシンプル設定の中堅以上の典型問題 最適化問題

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…

POJ 3692 Kindergarten

グラフ 二部グラフ フロー 最大安定集合・最小点被覆・最小辺被覆 POJ 補グラフを考える 補集合を考える NP困難(特殊構造なので解ける) クリーク 【問題集】フローのステップアップ そのまま覚えたいシンプル設定の中堅以上の典型問題

ARC 099 E - Independence の類題という感じ。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てる。 問題へのリンク 問題概要 人の女の子と、 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知り合いである。 そ…

AtCoder ARC 099 E - Independence (黄色, 700 点)

グラフ 二部グラフ DFS BFS DP シーケンシャルDP ARC-E AtCoder AtCoder700点 補グラフを考える 補集合を考える 黄色diff 均等に分ける そのまま覚えたいシンプル設定の中堅以上の典型問題 中堅以上の典型要素を詰め合わせた教育的問題

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…

AtCoder ARC 097 E - Sorted and Sorted (黄色, 600 点)

DP 前処理 累積和 操作:swap 最小回数・最小個数を求める 操作 AtCoder AtCoder600点 ARC-E 操作:隣接swap ソートすることが目的の操作の問題 最小コスト 黄色diff DP状態:吸い出しと吸い込み 要素の並び替えを管理するDP そのまま覚えたいシンプル設定の中堅以上の典型問題 最適化問題

600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…