Div.1 が開催されてなかったので、強者もこちらに参戦していた. 自分は、ABCの3問が解けて3完. 部屋一位であった. どちらとも初めてなので嬉しい.
1559 -> 1667正しく数えるだけ.
\([1, m)\) と \((m, n]\) に分けて可能性が大きく残ってる方に賭ける. 可能性が同じときは、インデックスが小さい方 (i.e. \([1,m)\)) を使う. 具体的には、\(m-1\) か \(m+1\) のどちらかを出力すればよい. 簡単なコーナーケースとして、\(n=1\) のときは仕方がないので \(1\) を出力するしかない.
文字列は単に . のゾーンと、そうでないアルファベット a のゾーンとにグルーピングして、その長さだけ管理しておけばよい.
.b..bz....
=> [ (. 1) (a 1) (. 2) (a 2) (. 4) ]\(f(s)\) の計算は、つまるところ、. のグループだけを見て、 長さ\(-1\) の和を取ればよい.
f([ (. 1) (a 1) (. 2) (a 2) (. 4) ]) = (1 - 1) + (2 - 1) + (4 - 1)文字の置換 (. または a を . または a へ変更する) は、グループのリストを上手く変更しなければならない. そのようなデータ構造を知らず、また、Div2のC問題なので、簡単にできるだろうと予測した. グループのリストを表現するようなデータ構造はやめる. 考え方としては使うけど、 直接的に扱うデータ構造は、元の文字列そのものとする. std::string は何文字目を変更するっていうのが出来ないはずなので std::vector<char> に変換する. しかも文字は '.' であるかだけを気にすれば良いので std::vector<bool> とした.
a を a へ変更する場合: 文字列は何も変わらない. を . へ変更する場合: 文字列は何も変わらない
a を . へ変更する場合: . のグループが生まれるか伸びるか連結される. いずれになるかは結局、その両隣を見ればよい
a(n) a a(m) を a(n) . a(m) に変更する場合 (アルファベットが\(n\)個並んでるものを a(n) と表記した): . のグループは新しく生まれる. ただしその長さは \(1\) なので、\(f(s)\) は変わらないa(n) a .(m) を a(n) . .(m) に変更する場合: 既に存在する. のグループの長さが\(1\)伸びるだけだから \(f(s)\) は\(1\) 増える.(n) a a(m) を .(n) . a(m) に変更する場合: 上と同じ.(n) a .(m) を .(n) . .(m) に変更する場合: \(f(s) = C + (n-1) + (m-1)\) であったのが、 \(f(s) = C + (n+1+m - 1)\) になるから、実は \(2\) 増えるだけ. を a へ変更する場合: 先ほどの逆 (増えるのが減る) になるだけ！
のように、文字置換する前の \(f(s)\) から、置換後の \(f(s)\) は計算できる
int n; cin >> n;
int m; cin >> m;
vi xs(n, 0);
rep (i, m) {
vi ys(n, 0); cin >> ys;
int mx = *max_element(begin(ys), end(ys));
rep (j, n) {
if (ys[j] == mx) {
xs[j]++;
break;
}
}
}
{
int mx = *max_element(begin(xs), end(xs));
int ans = -1;
rep (j, n) {
if (xs[j] == mx) {
ans = j;
break;
}
}
cout << ans+1 << endl;
} int n; cin >> n;
int m; cin >> m;
if (n == 1) {
cout << 1 << endl;
}
else {
if (m-1 < n-m) {
cout << m + 1 << endl;
}else {
cout << m - 1 << endl;
}
} int n; cin >> n;
int m; cin >> m;
vector<bool> cs; // 文字列の表現
vector<int> dots; // dot のグループの長さの列
{
string s; cin >> s;
cs.push_back(false);
for (char c: s) cs.push_back(c == '.');
cs.push_back(false);
int i = 0;
while (i < n) {
while (i < n and s[i] != '.') ++i;
int k = 0;
while (i < n and s[i] == '.') { ++k; ++i; }
dots.push_back(k);
}
}
// trace(cs);
// trace(dots);
// 初めの文字列 s の f(s)
int ans = 0;
for (int d: dots) ans += max(0, d-1);
rep (_, m) {
int pos; char c; cin >> pos >> c;
bool b = c == '.';
if (cs[pos] != b) {
if (b) { // dot
if (cs[pos-1] and cs[pos+1]) { // 両辺 dot
ans += 2;
}
else if ((not cs[pos-1]) and (not cs[pos+1])) { // 両辺 a
ans += 0;
}
else { // 片側 dot
ans += 1;
}
}
else {
if (cs[pos-1] and cs[pos+1]) {
ans -= 2;
}
else if ((not cs[pos-1]) and (not cs[pos+1])) {
ans -= 0;
}
else {
ans -= 1;
}
}
}
cout << ans << endl;
cs[pos] = b;
}