競プロDPL_2_A – 巡回セールスマン問題 問題のリンク この問題のポイント dfs(depth first search)でメモ化再帰頂点数が少ないので、bitで状態を管理可能(詳しくは以下、提出したコード参照) 提出コード #include <bi... 2021.08.09競プロ精選100プログラミング
競プロJOI 2014 予選 4 – 部活のスケジュール表 問題のリンク D - 部活のスケジュール表 (Schedule) この問題のポイント bit状態同士を比較してdpを更新 提出したコード #include <bits/stdc++.h> #inc... 2021.08.09競プロ精選100プログラミング
競プロAtCoder Beginner Contest 134 E – Sequence Decomposing 問題のポイント 各色の最大値を管理するバッファを用意最長増加部分列と同じ考え方で、配列を順に見ていく際にどの色に所属させるべきかが一意に決まる。また、その判定に二分探索が使える新たな色を追加する際に一番小さい最大値になるので、pus... 2021.08.09競プロ精選100プログラミング
競プロJOI 2017 予選 4 – ぬいぐるみの整理 この問題のポイント 種類の並び替えと比較するbitDPで計算量をN!から2^Nに削減する 提出したコード #include <bits/stdc++.h> using namespace std; using... 2021.08.09競プロ精選100プログラミング
競プロAOJ1611 Daruma Otoshi この問題のポイント 区間DPの基本である、「区間幅」「開始位置」「区間内の区切り位置」によってDP更新を行う上記に加えて、「区間幅」更新の最後に、だるまが全て打ち抜けた場合の更新を行う 提出コード #include &l... 2021.08.09競プロ精選100プログラミング