精選問題日記：DP・Bit探索・Priority Queue
Dynamic Programming (DP)
A - Frog 1 (EDPC)
見たことあるけど解けなかった問題。でも、DPの初歩的な問題なので、なんとなく思った通りに解くことができました。
反省点：初期値の設定には注意が必要。貰うDPと配るDPの違いには気づいたものの、使い分けはいまだによくわかっていません。
コードを表示
#include
using namespace std;
int main(void){
int n;
cin >> n;
vector dp(n, 1e10), h(n);
for(int i = 0; i < n; i++){
cin >> h[i];
}
dp[0] = 0;
for(int i = 0; i < n-1; i++){
dp[i+1] = min(dp[i+1], dp[i] + abs(h[i]-h[i+1]));
if(i < n-2){
dp[i+2] = min(dp[i+2], dp[i] + abs(h[i]-h[i+2]));
}
}
cout << dp[n-1] << endl;
return 0;
} B - Frog 2 (EDPC)
Aの拡張で解ける問題。計算量的に $O(NK)$ で間に合うんだ...と感じました。
制約：
$2 \le N \le 10^5$
$1 \le K \le 100$
$1 \le h_i \le 10^4$
コードを表示
#include
using namespace std;
int main(void){
int n, k;
cin >> n >> k;
vector dp(n, 1e9), a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
dp[0] = 0;
for(int i = 0; i < n; i++){
for(int j = 1; j <= k; j++){
if(i + j < n){
dp[i + j] = min(dp[i + j], dp[i] + abs(a[i] - a[i + j]));
}
}
}
cout << dp[n-1] << endl;
return 0;
} C - 柱柱柱柱柱 (ABC040)
Frog 1と同じ制約下で解ける問題。この問題を難なく実装できたので、初歩的なDPはできるようになったかも？
コードを表示
#include
using namespace std;
int main(void){
int n;
cin >> n;
vector dp(n, 1e10), h(n);
for(int i = 0; i < n; i++){
cin >> h[i];
}
dp[0] = 0;
for(int i = 0; i < n-1; i++){
dp[i+1] = min(dp[i+1], dp[i] + abs(h[i]-h[i+1]));
if(i < n-2){
dp[i+2] = min(dp[i+2], dp[i] + abs(h[i]-h[i+2]));
}
}
cout << dp[n-1] << endl;
return 0;
} C - Typical Stairs (ABC129)
最初はわからなかったが、解説を見て納得。フィボナッチ数列のように解くことができます。
未来の自分へ：これを解説無しで解けるようになっていただきたい。。。
コードを表示
#include
using namespace std;
int main(void){
int n, m;
cin >> n >> m;
vector dp(n+1, 0), a(m);
dp[0] = 1;
dp[1] = 1;
for(int i = 0; i < m; i++){
cin >> a[i];
dp[a[i]] = -1;
}
for(int i = 2; i <= n; i++){
if(dp[i] == -1){
continue;
}
if(dp[i-1] != -1){
dp[i] += dp[i-1];
}
if(dp[i-2] != -1){
dp[i] += dp[i-2];
}
dp[i] %= 1000000007;
}
cout << dp[n] << endl;
return 0;
} Bit探索
C - Popcorn (ABC358)
選ぶ店と選ばない店をBit探索し、選んだ店ですべての味をコンプリートできるか全探索。コードがぐちゃぐちゃになってしまったので、きれいに書けないか模索中。
コードを表示
#include
using namespace std;
int main(void){
int n, m;
cin >> n >> m;
vector s(n);
for(int i = 0; i < n; i++){
cin >> s[i];
}
int ans = 100;
for(int i = 0; i < (1 << n); i++){
bool t = true;
vector tmp;
int l = i;
int j = 0;
while(l != 0){
int a = l % 2;
l /= 2;
if(a == 1){
tmp.push_back(j);
}
j++;
}
for(int k = 0; k < m; k++){
bool f = false;
for(int p = 0; p < tmp.size(); p++){
if(s[tmp[p]][k] == 'o'){
f = true;
}
}
if(!f){
t = false;
}
}
if(t){
int u = tmp.size();
ans = min(ans, u);
}
}
cout << ans << endl;
return 0;
} Priority Queue
B - Get Min (ABC419)
最も簡単なpriority_queueの問題だと思います。最大値出力と最小値出力で宣言方法が少し違うので、しっかり覚えておきたい。
コードを表示
#include
using namespace std;
int main(void){
int q;
cin >> q;
priority_queue, greater> que;
for(int i = 0; i < q; i++){
int t;
cin >> t;
if(t == 1){
int x;
cin >> x;
que.push(x);
}
else {
cout << que.top() << endl;
que.pop();
}
}
return 0;
} C - 木 (Indeedなう)
人生初の水diff AC！グラフ入力後、BFSでpriority_queueに次の位置を格納しつつ、最小値を取り出していくことで解けました。
コードを表示
#include
using namespace std;
int main(void){
int n;
cin >> n;
vector g[100009];
for(int i = 0; i < n-1; i++){
int l, r;
cin >> l >> r;
g[l].push_back(r);
g[r].push_back(l);
}
priority_queue, greater> q;
q.push(1);
vector ans;
vector visited(100009, false);
while(!q.empty()){
int t = q.top();
q.pop();
visited[t] = true;
ans.push_back(t);
for(int i = 0; i < g[t].size(); i++){
if(visited[g[t][i]] == false){
q.push(g[t][i]);
}
}
}
for(int i = 0; i < ans.size(); i++){
if(i == ans.size() - 1){
cout << ans[i];
}
else {
cout << ans[i] << " ";
}
}
cout << endl;
return 0;
} 全体の感想
今回はDPを中心に、苦手なBit探索や応用的なPriority Queueに触れました。貰うDPと配るDPの使い分けなど、まだ曖昧な部分を練習していきたいです。