-
コンテスト中の考察(WA)
左から順番に見ていって、
#.が出てきたらいい感じに処理すれば良さげ#.の変換先は..か##か.#になる。##や.#はその次が.だった場合に死ぬから良くない。なので、できる限り..に変換したい。ただし、一つ前の要素が#なら##に変換するみたいなことを考えた。一生同じこと考えてしまって抜け出せなかった。
反省
ダメだった所
- ずっと同じ考察をしていた。違う観点の考察を頑なにしなかった。
改善点
- めんどくさがらずに再帰書くべきだった。
- 実験にもなるし、メモ化再帰が思いつけるかもしれない。実際メモ化再帰にできなさそうだから再帰実装しなかったけど、メモ化再帰にできた。
思いつき方
1. 実験してみる
- この問題の実験は簡単で、全探索すれば良い。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
// 「#.」のパターンがないかをチェック
bool check(string t) {
for (int i = 0; i < n-1; i++) {
if (t[i] == '#' and t[i+1] == '.') {
return false;
}
}
return true;
}
void dfs(int idx, string k) {
if (idx >= n) {
if (check(k)) {
cout << k << endl;
}
return;
}
dfs(idx+1, k+'.');
dfs(idx+1, k+'#');
}
signed main() {
cin >> n >> s;
dfs(0, "");
return 0;
}
サンプル1
...
..#
.##
###
サンプル2
.....
....#
...##
..###
.####
#####
サンプル3
.........
.........
........#
.......##
......###
.....####
....#####
...######
..#######
.########
#########
- 実験の結果、最終的な形は「…###」みたいな感じになることがわかる。なので、どこで区切れるかを全探索すれば解くことができる。
- 証明は思いつき方2で言う（そっちの方が自然に思いつけるので）
思いつき方1のコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int N;
string s;
int white[222222];
int black[222222];
signed main() {
cin >> N >> s;
// 1を立てる
for (int i = 0; i < N; i++) {
white[i+1] = s[i] == '.';
black[i+1] = s[i] == '#';
}
// 累積を取る
for (int i = 0; i <= N; i++) {
black[i+1] += black[i];
}
for (int i = N; i >= 1; i--) {
white[i-1] += white[i];
}
int ans = 1e18;
for (int i = 0; i <= N; i++) {
int t = black[i] + white[i+1];
chmin(ans, t);
}
cout << ans << endl;
return 0;
}
2. メモ化できそうな再帰を考える
- 思いつき方1で考えた再帰は
rec(int, string)の形式だった。これはメモ化できない。というよりメモ化する意味がない。結局全ての盤面を列挙することになるため。 -
rec(int, int)みたいな形になると嬉しい。この問題では現在の要素とそのひとつ前の要素さえ分かっていれば良さげ。列挙するのは#.という形が存在しない盤面なので、ひとつ前の要素が#なら現在の要素を.にしないみたいな再帰を書けばいい。
最終盤面が「…###」になることの証明
- 結局最終的な盤面は「…###」みたいになる。左から要素を決めていって、一度「#」を置くとそれより右には「#」しか置けなくなる（ちょっとわかりづらいけど、再帰を書いてみると直感的にわかる）。なので「..##」の形になる。
- まあこの解法では最終盤面なんて考えなくて済むから楽なんだけど。
思いつき方2のコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
vector<int> v; // sを数値に変換した配列。#は1で.は0
int dp[222222][5]; // dp[i][j]: 直前の要素がjで、i番目の要素まで見た時の最小の操作回数
int dfs(int idx, int old) {
if (idx >= v.size()) {
return 0;
}
if (dp[idx][old] != -1) {
return dp[idx][old];
}
int ret = 0;
int a = dfs(idx+1, 1) + (v[idx] == 0); // 現在の要素を'#'にする
int b = (old == 1 ? 1e18 : dfs(idx+1, 0) + (v[idx] == 1)); // 現在の要素を'.'にする
ret += min(a, b);
return dp[idx][old] = ret;
}
signed main() {
cin >> n >> s;
v.push_back(-1); // つじつま合わせ的なやつ
for (int i = 0; i < n; i++) {
int val = s[i] == '#' ? 1 : 0; // ここから先では「#」を1、「.」を0として扱う
v.push_back(val);
}
// dpテーブルを初期化
for (int i = 0; i < 222222; i++) { for (int j = 0; j < 5; j++) { dp[i][j] = -1; } }
int ans = dfs(0, 3); // 3は0番目の要素の前の要素がどの記号化を表す。-1番目の要素は存在しないので適当に3と置いた
cout << ans << endl;
return 0;
}
要点
- よくわからんかったら実験してみる
- 実験は法則性を掴むためにやるもの。最適解を探ってく感じの問題じゃなくて、法則性を見つける問題だったら実験すると良さげ。
- どうせ再帰書いてもTLEだし書くだけ時間の無駄だと思ったけどかいとけば良かったなぁと思った。
- 手元で実験するの下手すぎるけど今回の問題コンピュータで実験できるのありがたい
メモ
- これ、思いつくの結構難しい気がするけど無限人が解いてるし解説でも「はい自明」みたいにサラっと言っててビビる。僕がアホなだけ
- drkenさんの記事