AtCoder Beginner Contest 196

atcoder.jp

oooxox (677th)

oj を verify 以外でも活用していこうかなって思ったので今回から導入した　めちゃくちゃ便利です kimiyuki さんありがとう

github.com

A - Difference Max (100)

$x - y$ の最大値を求めてください

冷静に考えると $x$ を可能な限り大きく、 $y$ を可能な限り小さくしたほうがいいので $b - c$ が答えになる

自信はあったけどペナ怖いしちゃんと試した

B - Round Down (200)

$X$ を文字列として受け取り、'.' より前を出力、'.' が存在しない場合は全部出力

string の find, substr を使えばできると思ったけどコンテスト中はなんか動かなかったので調べるよりはと思ってナイーブに実装

コンテスト後に見たら ≠ と = を間違えていた

C - Doubled (300)

前半だけ探索すればいい、これは最大でも $10^{6}$ 程度なので十分高速

D - Hanjo (400)

$2A + B = HW$ が保証されているので、 $1 \times 1$ の畳は無視してよい　埋まっていないところに自由に埋められるので

あとは $2 \times 1$ の畳の置き方を重複なく数えればいいが、ある状態に対する $(畳の最も左上の座標, 縦置きしたか)$ の集合が一致している置き方を重複して数えなければいいだけなので、これが昇順になるように畳を置いていけば自ずと重複なく数えられる

実装をバグらせた、状態を管理している bit に足し込むときにシフトしていないのが原因　競技プログラミングをやりましょう

E - Filters (500)

求めたいものを $f(x)$ とすると、最終的には $[l, r]$ が $[B, T]$ に移り、 $x < l$ , $r < x$ なる $x$ がそれぞれ $B$ , $T$ に移ることがわかる

$f( -\infty), f(\infty)$ を求めると $B, T$ がわかるので、そこから $l, r$ を二分探索で求めると解ける

$S$ を $t = 1$ のときの $a$ の和とすると $[l + S, r + S ]$ と $[B, T]$ が一致するのでこっちで実装するのと迷った結果二分探索を選択したけど、一回バグらせたし実装もこっちのほうが軽かったのでもう少しだけ考えて実装方針を選択すればよかったな　若干自信がなかったけどもうちょっと考えたら自信が持てたと思うし

F - Substring 2 (600)

$a_i$ を $S$ の $i$ 文字目が $"0"$ かどうか、 $b_i ’$ を $T$ の $i$ 文字目が $"1"$ かどうかの bool 列として、 $b'$ を reverse した列 $b$ を考えると、畳み込みで $S [i, i + |T|]$ と $T$ のうち $S[i + k] = "0"$ かつ $T[k ] = "1"$ となる $k$ の数が求まる　 $"0", "1"$ を逆にして同じことをして足せば求めたいものが求められる

反省

oj の導入

英断

D

サンプルが合わなかったあと一旦パソコンから離れたのは正解、正当性をちゃんと考え直せたのもえらい

デバッグできなくて E, F を読みにいって E 通したあとに 20 分あったし、そのあとで D を修正できた場合は順位が 150 くらい上がったはず
ただ F も解法が出せた上にこっちを通せば 500 くらい上がったことを考えるとどっちもどっちかなあという感じがするので戦略が間違っていたどうかは結果論になりそう　基本的には D の修正をするべきだったかな

バグらせたのはコンテスト中は仕方がないので、実装込みの練習をちゃんとやってリハビリをする

F

10分残っているか残っていないかくらいのときに FFT に気がついたあと、焦って実装をする前にちゃんと細部を詰めようとしたのはよかった

震える手で急いで実装して間に合わなかったのがめちゃくちゃ悔しい

ICPC の練習のときに beet くんから説明をうけて最近畳み込みが何をやっているものなのかを知った程度で慣れていなさすぎる
　いくつか問題解くなどして脳を慣れさせたい

コンテスト全体

久しぶりに負けて悔しすぎて腹が立つやつを経験している　これだよこれこれ　競技プログラミング

次はやるぞ

コード

A

void solve() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << b - c << endl;
}

B

void solve() {
  string s;
  cin >> s;
 
  auto idx = s.find('.');
  if (idx == string::npos) idx = s.size();
  cout << s.substr(0, idx) << endl;
}

C

void solve() {
  i64 n = input();

  int ans = 0;
  for (i64 k = 1; ; k++) {
    string s = to_string(k);
    i64 t = (i64)(k * pow(10, s.size())) + k;
    if (n < t) break;

    ans++;
  }

  cout << ans << endl;
}

D

この手のメモ化、これまでは dp[~] が -1 かどうかで used かどうかを判定していたけど、bool で同じサイズの配列を管理したほうがバグらせないし初期化も楽ということに気がついた　これまでの実装は手癖以上の理由がなかったしこの間すごいバグらせかたをしたのでこれからはこう書く

int h, w, a, b;

void next_yx(int &ny, int &nx) {
  nx++;
  if (nx == w) {
    nx = 0;
    ny++;
  }
}

int to_idx(int y, int x) {
  return y * w + x;
}

bool used[16][16][16][1 << 16];
int dp[16][16][16][1 << 16];

int dfs(int y, int x, int cnt, int bit) {
  if (y == h) {
    return cnt == a;
  }

  if (used[y][x][cnt][bit]) {
    return dp[y][x][cnt][bit];
  }

  used[y][x][cnt][bit] = true;
  int &res = dp[y][x][cnt][bit];
  res = 0;

  int ny = y, nx = x;
  next_yx(ny, nx);

  if (x + 1 != w) {
    int a = to_idx(y, x);
    int b = to_idx(y, x + 1);
    if (( not(bit & (1 << a)) ) and ( not(bit & (1 << b)) )) {
      res += dfs(ny, nx, cnt + 1, bit | (1 << a) | (1 << b));
    }
  }

  if (y + 1 != h) {
    int a = to_idx(y, x);
    int b = to_idx(y + 1, x);
    if (( not(bit & (1 << a)) ) and ( not(bit & (1 << b)) )) {
      res += dfs(ny, nx, cnt + 1, bit | (1 << a) | (1 << b));
    }
  }

  res += dfs(ny, nx, cnt, bit);
  return res;
}

void solve() {
  cin >> h >> w >> a >> b;
  cout << dfs(0, 0, 0, 0) << endl;
}

E

void solve() {
  int n = input();

  vector< i64 > as(n), ts(n);
  range(i, 0, n) cin >> as[i] >> ts[i];

  auto fr = [&](i64 x) {
    range(i, 0, n) {
      if (ts[i] == 1) x += as[i];
      if (ts[i] == 2) x = max(x, as[i]);
      if (ts[i] == 3) x = min(x, as[i]);
    }
    return x;
  };

  i64 tp = fr(infll);
  i64 bm = fr(-infll);

  i64 sum = 0;
  range(i, 0, n) if (ts[i] == 1) sum += as[i];

  auto f = [&](i64 x) {
    return clamp(x + sum, bm, tp);
  };

  int q = input();
  range(i, 0, q) {
    i64 x = input();
    cout << f(x) << endl;
  }
}

F

うしくん　ありがとう

ei1333.github.io

void solve() {
  string s, t;
  cin >> s >> t;

  int n = s.size();
  int m = t.size();
  vector< int > cs(n - m + 1);
  for (int k = 0; k < 2; k++) {
    vector< int > as, bs;
    for (auto &c : s) as.emplace_back((c == '0') ^ k);
    for (auto &c : t) bs.emplace_back((c == '1') ^ k);
    whole(reverse, bs);
    auto ds = FastFourierTransform::multiply(as, bs);
    range(i, 0, n - m + 1) {
      cs[i] += ds[i + m - 1];
    }
  }
  
  cout << *whole(min_element, cs) << endl;
}

Luzhiled's memo

メモということです