2022-05-24

ABC212 E - Safety Journey（配るDP → 貰うDPにして高速化する）

数え上げ貰うDP DP高速化競プロ雑メモ

今日参加したあさかつで解いた問題が貰うDPを利用した勉強になる問題だったので、そのメモ

（最後にお世話になった参考記事、動画のリンクを載せてあるので、そちらを先に見てもらった方が分かりやすいかもです。）

問題

atcoder.jp

考察（間に合わずTLEするバージョン）

まずは、愚直なDPの考察から。こんな感じで考えて、DPを組んでいった。

頂点数5000、日数5000なので O(N * K) が間に合いそうだな
となると、i日目に、頂点jにいるような組み合わせdp[i][j] として、dp[k][0] (0-indexed) が答えだ！
なので、とりあえず壊れた辺を除外してグラフ構築して、DPやろう！！

で、組んだDPが以下。めでたく O(N² * K) となりTLEしました。
配るDPで組んでいて、配る度に壊れてない橋でつながった頂点分(= O(N))だけ計算量がかかるのでダメだった。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
long long MOD = 1000000007;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
#define all(obj) (obj).begin(), (obj).end()
using Graph = vector<vector<int>>;

// 変数宣言------------------

// 関数定義------------------

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  using mint = modint998244353;

  int n, m, k;
  cin >> n >> m >> k;

  Graph g(n);

  set<pint> broken;  // 壊れた辺
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (v < u) {
      swap(u, v);
    }
    broken.insert({u, v});
  }

  // 壊れてない辺だけ, 張る
  for (int u = 0; u < n - 1; u++) {
    for (int v = u + 1; v < n; v++) {
      if (broken.find({u, v}) == broken.end()) {
        g[u].push_back(v);
        g[v].push_back(u);
      }
    }
  }

  // i日目に, 都市j にいるような組み合わせ dp[i][j]
  vector dp(5100, vector<mint>(5100, 0));
  dp[0][0] = 1;
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < n; j++) {
      for (auto v : g[j]) {
        dp[i + 1][v] += dp[i][j];
      }
    }
  }

  cout << dp[k][0].val() << endl;
}

考察（ACするバージョン）

（結局自力ではダメだったので、以下は解説読んだあとの考察。）
何かしら考察をする必要があるが、壊れた橋が少ない（max 5000）ことがポイント。
これをうまく使ってDPを構成する。自力ACに必要だと感じた考察は以下。

壊れた橋が少ない（5000）のでうまく使えないか？
橋が全てかかっている場合から、壊れた橋の分だけうまく引けないか？
橋が全てかかっている場合は高速に計算できないか？

更に考察していくと、以下のようになる

i日目のdp[i][j]に関して、(i-1)日目の全ての頂点の組み合わせの総和sum(dp[i-1][0] + ... + dp[i-1][n-1]) はO(N) で求められる
dp[i][j] に足したくないのは、以下のふたつ
- 壊れた橋からの移動 → i日目に引きたいものは、O(M)で計算できる（ここが一番理解が難しかった、、）
- 自分自身(j)からの移動 → O(1) で分かる
したがって、各iに対してやることは以下。
- 全ての橋が正常な状態の組み合わせの総和を求める O(N)
- 各頂点について壊れた辺からの組み合わせを引く O(M)
- 自分自身から移動してきた組み合わせを引く O(1)
よって、全体の計算量はO(K * (N+M)) で間に合う

補足

最初の愚直なDPは配るDPで書いていたけど、しれっと貰うDPに変更している。
これは、貰うほうじゃないとうまく高速化ができないから。（もしかして配る方でも高速化できるかもだけど、私は分かんないです）
「なんで貰うの方がいいの？」という部分は、自分もまだ理解が曖昧だが、現状はこんなイメージ。
伝わる、、かな、、伝わらないかも、、

図にあるように、配る側はまとめるのが難しそうだが、貰う側は配る方の総和を計算しておけば、あとは各頂点に足すだけ。

というわけで実装。

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
long long MOD = 1000000007;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
#define all(obj) (obj).begin(), (obj).end()

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  using mint = modint998244353;

  int n, m, k;
  cin >> n >> m >> k;

  // 使えない辺
  vector<int> a(m);
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }

  // i日目に 都市j にいるような組み合わせ dp[i][j]
  // 高速化したいので, 貰うDPで考える
  vector dp(5100, vector<mint>(5100, 0));
  dp[0][0] = 1;

  for (int i = 1; i <= k; i++) {
    // 一つ前のすべての頂点から経路
    mint sum_all = 0;
    for (int j = 0; j < n; j++) {
      sum_all += dp[i - 1][j];
    }

    // 壊れた橋の頂点からの経路を引いていく
    for (int j = 0; j < m; j++) {
      dp[i][a[j]] -= dp[i - 1][b[j]];
      dp[i][b[j]] -= dp[i - 1][a[j]];
    }

    // dp[i][j] = すべての頂点からの経路 - 壊れた橋の頂点からの経路 - 自分からの経路
    // すべての頂点を足して、自分自身からの経路を引く
    for (int j = 0; j < n; j++) {
      dp[i][j] += (sum_all - dp[i - 1][j]);
    }
  }

  cout << dp[k][0].val() << endl;
}

お世話になった記事、動画

2022-05-24

競プロ用の組み合わせ前計算テンプレート（階乗、順列、組み合わせ、重複組合せ）

競プロ数え上げ組み合わせライブラリ

二項係数nCr、1<=r<=n の範囲を事前計算してテーブル作れば、前計算O(n)、以後O(1)だし割と困らない？？
— なかしー (@nakashiii2020) 2022年5月23日

ということで、以下の4つをO(n)で前計算して、O(1)で呼び出せるようにする

階乗
順列 nPr
組み合わせ nCr
重複組み合わせ nHr

実装

ちょっと補足

DPとかで使えるように AtCoderライブラリのModint を使っている
変数はグローバルに宣言してあって、mainで対象の関数を呼び出して初期化する
【注意】きちんと動作確認していないので、バグっていたらごめんなさい

// modを問題文にあわせること！！！忘れずに！！！！！！
using mint = modint1000000007;

vector<mint> fact;  // rの階乗
vector<mint> nPr;   // n個から r個取り出す 順列
vector<mint> nCr;   // n個から r個取り出す 組み合わせ
vector<mint> nHr;   // n個から r個取り出す 重複組み合わせ

void pre_calc(ll n) {
  // 初期化
  fact.assign(n + 10, 1);
  nPr.assign(n + 10, 1);
  nCr.assign(n + 10, 1);
  nHr.assign(n + 10, 1);

  // 組み合わせ用
  for (ll r = 1; r <= n; r++) {
    fact[r] = fact[r - 1] * r;
    nPr[r] = nPr[r - 1] * (n + 1 - r);
    nCr[r] = nPr[r] / fact[r];
  }

  // 重複組合せ用
  mint top = 1;     // 分子
  mint bottom = 1;  // 分母
  for (ll r = 1; r <= n; r++) {
    top *= (n + r - 1);
    bottom *= r;
    nHr[r] = top / bottom;
  }
}

// これをmainで呼ぶ. nは取り出す母数
// pre_calc(n);

おまけ

この問題を解いている時に欲しくなった。 E - Roaming

もし上記の実装間違っていたら、Twitter、もしくはブログコメントで教えて頂けるとうれしいですm(_ _)m

2022-05-08

AtCoder Beginner Contest 246 E - Bishop 2 雑メモ（01-BFS, 枝刈りBFS）

競プロ雑メモ枝刈り 01BFS

01-BFSと枝刈りBFSを忘れかけていたので、見返す時用の雑なメモ 01-BFSで解ける問題は、枝刈りBFSでも解ける問題が多いっぽい？

問題

E - Bishop 2

枝刈りBFS

基本は通常のBFS
「明らかに探索しなくていいいパターン」が出現したら、その頂点以降の探索を打ち切る

01-BFS

次の点へのコストを0 or 1として考える
最短距離がなるべく小さい点から探索したいので、以下のようにdequeを使って探索する頂点を以下のように管理する
- 次のコストが0 → dequeの先頭に追加
- 次のコストが1 → dequeの末尾に追加

実装

枝刈り全探索

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
long long MOD = 1000000007;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
#define all(obj) (obj).begin(), (obj).end()
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};
using Graph = vector<vector<int>>;

// 変数宣言------------------

// 関数定義------------------

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  int n;
  cin >> n;

  int ax, ay, bx, by;
  cin >> ax >> ay >> bx >> by;
  ax--, ay--, bx--, by--;

  char s[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> s[i][j];
    }
  }

  // ななめ4方向
  vector<int> dirx = {1, -1, -1, 1};
  vector<int> diry = {1, -1, 1, -1};

  // d 最短手数
  // q 探索キュー
  vector<vector<int>> d(n, vector<int>(n, IINF));
  queue<pint> q;

  // 初期化
  q.push({ax, ay});
  d[ax][ay] = 0;

  // bfs
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();

    for (int i = 0; i < 4; i++) {
      for (int add = 1; add < n; add++) {
        int nx = x + add * dirx[i];
        int ny = y + add * diry[i];

        if (nx < 0 || ny < 0 || nx >= n || ny >= n || s[nx][ny] == '#') {
          break;
        }
        // TODO: ここで枝刈りする
        // 小さい時 → キューにpush
        // 同じ時 → 素通り
        // 大きい時 → 枝刈り
        if (d[nx][ny] > d[x][y] + 1) {
          q.push({nx, ny});
          d[nx][ny] = d[x][y] + 1;
        } else if (d[nx][ny] < d[x][y] + 1) {
          break;
        }
      }
    }
  }

  if (d[bx][by] == IINF) {
    cout << -1 << endl;
  } else {
    cout << d[bx][by] << endl;
  }
}

01-BFS

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
long long MOD = 1000000007;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
#define all(obj) (obj).begin(), (obj).end()
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};
using Graph = vector<vector<int>>;

// 変数宣言------------------

// 関数定義------------------

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  int n;
  cin >> n;

  int ax, ay, bx, by;
  cin >> ax >> ay >> bx >> by;
  ax--, ay--, bx--, by--;

  char s[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> s[i][j];
    }
  }

  vector<vector<vector<int>>> d(n,
                                vector<vector<int>>(n, vector<int>(4, IINF)));

  // ななめ4方向
  vector<int> dx = {1, -1, -1, 1};
  vector<int> dy = {1, -1, 1, -1};

  // (x, y, dir);
  deque<tuple<int, int, int>> q;
  for (int i = 0; i < 4; i++) {
    q.push_back({ax, ay, i});
    d[ax][ay][i] = 1;
  }

  while (!q.empty()) {
    auto [x, y, dir] = q.front();
    q.pop_front();

    for (int ndir = 0; ndir < 4; ndir++) {
      int nx = x + dx[ndir];
      int ny = y + dy[ndir];

      if (nx < 0 || ny < 0 || nx >= n || ny >= n || s[nx][ny] == '#') {
        continue;
      }

      int cost = (dir == ndir ? 0 : 1);
      // 距離更新できるなら, 探索対象にする
      if (d[nx][ny][ndir] > d[x][y][dir] + cost) {
        if (cost == 0) {
          q.push_front({nx, ny, ndir});
        } else {
          q.push_back({nx, ny, ndir});
        }
      }
      // 最短距離更新
      d[nx][ny][ndir] = min(d[nx][ny][ndir], d[x][y][dir] + cost);
    }
  }

  // 4方向のうち, 最も小さい手数がこたえ
  int ans = IINF;
  for (int i = 0; i < 4; i++) {
    ans = min(ans, d[bx][by][i]);
  }

  if (ans == IINF) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
}

参考

2022-04-18

AtCoder Beginner Contest 248 E - K-colinear Line

競プロ直線上の座標の判定 1次直線の表現方法

直線上の点を数え上げる問題。本番で AC できなかったので解法をメモ

問題

AtCoder Beginner Contest 248 E - K-colinear Line

勉強になったこと

1 次直線をどうやって少数使わずに表現するか（同じ直線かどうかをどう判定するか）
直線上に点があるかの判定方法

考察

問題を見てみると、以下のようなところまではコンテスト中に割とスッと出てきた

頂点数が 300 なので、N³ 解法が間に合いそう
直線は N² で全列挙できる
直線を全列挙したあとに、座標が直線状にあるかを全探索すれば N³ で解ける

なので、あとは実装するだけ。めでたし、めでたし。、、、とはなりませんでした。40 分かけてバグらせて時間切れでした、、

難しかったポイント

個人的に難しかったポイントは以下

「直線」を表現したいけど、普通に y=ax+b の傾き求めたら、a が少数になってしまう
直線全探索すると、同じ直線が出てきてしまう
傾きと切片を使わずに座標が直線状にあるかをどう判定すればいいのか

結果としては、以下のようにすると個人的に一番わかりやすく実装できた

直線は直線上の座標の集合(vector)として表現する
直線は set に入れて、重複除去する
3 点の座標が直線上にあるかは公式使って判定

上記、ひとつずつ説明する。

「直線」を表現したいけど、普通に y=ax+b の傾き求めたら、a が少数になってしまう

「直線」を表現する時、真っ先に思いつくのが、 y=ax+b の(a,b)をペアで管理する方法。ただ、これだと a を計算する時に少数になってしまうことがあって、誤差で同一直線の判定ができないとやだな、、、という感じ

これを回避する方法は、例えば a=dy/dx とすると、dx,dy の最大公約数を求めて、割っておけば同じ直線は必ず同じ dx, dy になるので、その組み合わせで管理すると重複判定ができる。

ただ、コンテスト本番はこの方針で試して、どうもバグが取り切れず時間切れだったので、もう少しシンプルな方針にする。

どうするかと言うと、「直線 = 直線上の座標の集合」 という形で表す

例えば、y=2x+5 なら {(1,7), (4, 13), (10, 25)} みたいな感じ。ここでは説明上、(x,y)という風に管理しているが、実際の実装は座標がを保持している配列のインデックスで管理している。

直線は set に入れて、重複除去する

直線の表現方法が決まれば、重複除去は簡単。set に突っ込むだけ。

3 点の座標が直線上にあるかは公式使って判定

ある点が直線上にあるかの判定は y=ax+b が分かっていれば代入するだけだが、今回は a,b を求めないのでそれができない。なので、公式解説に書いてある、3 点の座標を使って直線上か判定する方法を使う（どうやら直線上の点の典型らしいです）

実装

あとは、

直線は直線上の座標の集合(vector)として表現する
直線は set に入れて、重複除去する
3 点の座標が直線上にあるかは公式使って判定

をそのまま実装するだけ。割とシンプルな 3 重ループになる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 変数宣言------------------

// 関数定義------------------
bool same(ll x1, ll y1, ll x2, ll y2, ll x, ll y) {
  return (x2 - x1) * (y - y1) == (y2 - y1) * (x - x1);
}

// メイン------------------
int main() {
  int n, k;
  cin >> n >> k;

  ll x[n];
  ll y[n];
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

  if (k == 1) {
    cout << "Infinity" << endl;
    return 0;
  }

  set<vector<int>> line;  // 直線の集合

  // 座標i, j を通る直線を全探索
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      // 頂点を全探索して, 直線上の座標の集合をつくる
      vector<int> pos;
      for (int k = 0; k < n; k++) {
        if (same(x[i], y[i], x[j], y[j], x[k], y[k])) {
          pos.push_back(k);
        }
      }
      // 直線をsetに追加
      line.insert(pos);
    }
  }

  // k以上の頂点がある直線をカウント
  ll ans = 0;
  for (auto it = line.begin(); it != line.end(); it++) {
    if ((int)(*it).size() >= k) {
      ans++;
    }
  }
  cout << ans << endl;
}

感想

直線上の座標を判定する方法と直線を管理する方法を勉強できてよかった。ちゃんと考察すれば、シンプルなコードになるので考察やっぱ大事。

2022-04-12

AtCoder Beginner Contest 247 E - Max Min

競プロしゃくとり法数え上げ最大値や最小値のインデックスを使う

本番ではACできず、解説見たら区間数え上げの典型(？)としてとても勉強になったのでメモ
基本的には以下の2つの解説を（おおよそ）そのまま実装していく

勉強になったこと

しゃくとり法の応用
区間の数え上げの時に、最大値や最小値のインデックスをうまく使う

問題

E - Max Min

前提知識

しゃくとり法

しゃくとり法はけんちょんさんの記事がとっても分かりやすい（私もこの記事で3週間ほど前にしゃくとりデビューしました）
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

考察

公式解説に記載のある以下のサンプルケースを考える
X=4,Y=2
A=(4,2,5,4,3,4,2)

まず、数え上げたい区間の条件は以下

＜条件＞

区間[L,R]において、最大値はX、最小値はY となる区間を数えよ

例えば、以下のような感じ

区間[0, 1] → 最大値は4、最小値は2（OK）
区間[0, 2] → 最大値は5、最小値は2（NG）
区間[4, 6] → 最大値は4、最小値は2（OK）

ただ、このままの条件では数え上げしにくいので、以下のように条件を言い換える。

＜条件＞
以下の2つを満たす区間を数えよ

区間[L,R]において、最大値はX以下、最小値はY 以上
区間[L,R]において、X、Yの両方を含む

ここまでできれば、準備は完了。この問題を解けるファーストステップとして、まずはこの条件の言い換えができるか？が大切（たぶん）
あとは上記の区間をどうやって数えるか？を考える。
制約がN=10⁵くらいあるので、LとRの全探索のO(N²)だと間に合わない。
今回はO(N)で解ける方法を2つ実装していく。

方法1：条件を満たす区間に分割して、それぞれの区間に対してしゃくとり法を繰り返す

まずはしゃくとり法を使う方法。ざっくりと数え上げ手順は以下。

「区間[L,R]において、最大値はX以下、最小値はY 以上」という条件を満たす列をAから抽出する。
上記で抽出した列に対して、しゃくとり法で「区間[L,R]において、X、Yの両方を含む」区間を数え上げ
上記2つを繰り返す

以下は上記の手順を図に示したもの。青色の区間に対してしゃくとり法を適用していく。赤色の区間（値）は条件を満たさないので無視する。

というわけで、しゃくとり法はO(N)なので、全体でもO(N)で数え上げができて、めでたし、めでたし。という感じ。
最後に実装は以下のようになる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 変数宣言------------------
int n, x, y;

// 関数定義------------------
ll syakutori(vector<int>& a, int start, int end) {
  ll ans = 0;
  int r = start;
  int xcnt = 0;  // xの出現回数
  int ycnt = 0;  // yの出現回数

  for (int l = start; l < end; l++) {
    while (r < end && !(xcnt && ycnt)) {
      if (a[r] == x) xcnt++;
      if (a[r] == y) ycnt++;
      r++;
    }

    // x, yの両方が出現する区間だけ数え上げ
    if (xcnt && ycnt) {
      ans += (end - r + 1);
    }

    if (l == r) {
      r++;
    } else {
      if (a[l] == x) xcnt--;
      if (a[l] == y) ycnt--;
    }
  }

  return ans;
}

// メイン------------------
int main() {
  cin >> n >> x >> y;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  // x <= a[i] <= y となる区間 [l,r) を考える
  ll ans = 0;
  int r = 0;
  for (int l = 0; l < n; l++) {
    // a[l] が条件満たさないのでNG
    if (a[l] > x || a[l] < y) {
      r = l + 1;
      continue;
    }

    // rを求める
    while (y <= a[r] && a[r] <= x) {
      r++;
    }

    // しゃくとりで区間を数える
    ans += syakutori(a, l, r);

    // 次に探索するlはr+1となる
    l = r;
    r++;
  }

  cout << ans << endl;
}

方法2：Xのインデックス、Yのインデックス、NG数値のインデックスを持ちながら、0〜N-1まで順次数え上げ

個人的にはこちらの方法の理解が難しかった。でも実装はこっちの方がグッとシンプルになるし、自分の手札としてもっておけると強そうだと思った。
基本方針としては、以下のようになる

区間の右端Rを0〜N-1まで走査する
その際、以下の3つを順次更新していく
- 区間内で最も右に登場するX
- 区間内で最も右に登場するY
- 区間内で最も右に登場するNG値（= Xより大きい or Y未満）
上記のそれぞれのインデックスをRx, Ry, Rngとすると、(Rng < Rx and Rng < Ry)となる時、条件に合致する区間なので数え上げる。add = min(Rx, Ry) - Rng が条件を満たす区間[L, R]での区間の個数

上記を図示したのが以下。R=2の場合とR=6の場合の2つ。
（図ではRが小文字rになってます、ごめんなさい）

まずは R=2 の場合（Rng < Rx and Rng < Ry の条件NGで、数え上げ区間なし）

最大値と最小値のインデックスを利用した数え上げ問題のイメージ — R=2 の場合

次に R=6 の場合（Rng < Rx and Rng < Ry の条件OKで、数え上げ区間あり）

よって、Rの走査はO(N)、区間のカウントはO(1)でできるので、全体ではO(N)になってめでたし、めでたしとなる。
実装は以下。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 変数宣言------------------
int n, x, y;

// 関数定義------------------

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  cin >> n >> x >> y;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int rx = -1;  // xが出てくる一番右のインデックス
  int ry = -1;  // yが出てくる一番右のインデックス
  int rng = -1;  // xより上 or y未満 が出てくる一番右のインデックス

  ll ans = 0;
  for (int r = 0; r < n; r++) {
    if (a[r] == x) rx = r;
    if (a[r] == y) ry = r;
    if (a[r] < y || x < a[r]) rng = r;
    if (rng < rx && rng < ry) ans += (min(rx, ry) - rng);
  }

  cout << ans << endl;
}

感想

シンプルにしゃくとり法を適用するだけの問題は解いたことがあったが、今回のようにしゃくとり法が適用できるように前処理してから、しゃくとりするのは初めてだったので、勉強になった。
あと、最大値や最小値のインデックスをうまく使うとシンプルなコードで数え上げできたりするのが、とてもビックリした。何回か使いながら、自然と考察で思いつけるようになりたいな〜。

2022-02-19

競プロ精進について雑メモ

今日お風呂で「どうやったら競プロで良い精進ができるのだろう」ってぼんやり考えていたことを雑にメモ現在のレートは500後半

そもそも「良い精進」とは何を指すのか？ここでは「レート上昇効率が良い精進」とするのがよさそう
atcoder problems はめちゃくちゃいい。助かってる
最近１日5ACくらいずつ茶diff解いてるけど、そうするとたくさんACしたくなってくる
その日、まだ1ACくらいしか解いてないと「やばい、なんか少ないしもっと解きたい！」ってなって、簡単な問題をいくつか精進してしまうことがある
なぜAC伸ばすのが楽しいかというと、AC伸ばすとすぐに目に見えるフィードバックがあるからだと思う。具体的には以下のようなもの
- atcoder problemsのpie chart, streak, progress chartあたり
- atcoder scores の精進チャート
逆に、難しい問題を解く行為に対しては、目に見えるフィードバックがほとんどない（もしかしたら見つけられてないだけ？）
自分にとって、いい感じの難易度をおすすめしてくれる機能はrecomendationがある。（めちゃくちゃ最高の機能でこれなしでは生きていけない体になっています）
体感として、解ける問題をたくさん解いても「強くなりにくい」と感じる
「ならない」ではなく「なりにくい」と書いたのには理由があって、実装力は鍛えられるから。ただしあまりに簡単すぎて一瞬で実装できる問題は強くならない。
そもそも、競プロで必要な能力は以下のような分類ができる？
- （考察系）問題を見て解法を導ける考察力
- （考察系）コーナーケースを考えつく能力
- （実装系）解法を実装できる能力
- （実装系）素早く実装してバグを取りのぞける能力
そのため、自分がどの能力が足りなくて、精進したいのかを考えて適切な精進方法を取る必要がある
また、上記の能力はアルゴリズムごとに必要と考えられる。例えば、DPは考察も実装もスムーズにできるけど、グラフは考察まではたどり着いて実装でいつもバグらせる。みたいな

というわけで、「良い精進」にするためには、

実装力をつけたい → 特定のアルゴリズムの問題をググったりして、とにかく集中的に解く
考察力つけたい → まずは座学。その次はrecomendationのmoderate〜dificultあたりの問題をひたすら解く。考察の効率だけを最大化したいなら、全問実装しなくてもいいかも。

という感じですかね？

2022-02-11

部分文字列の全探索（キーエンスプログラミングコンテスト 2019 B - KEYENCE String）

競プロ

部分文字列の抜き出しの仕方が分からなくて困った時に見返すようでメモ。この解説動画がめちゃくちゃ分かりやすい

www.youtube.com

問題はこちら

atcoder.jp

コード

#include <bits/stdc++.h>
using namespace std;

// 変数宣言------------------
string s;

// メイン------------------
int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  cin >> s;
  int n = s.size();
  bool ans = false;

  // i → 何番目から抜き出すか？
  // j → 何番目まで抜き出すか？（jを含まない）
  for (int i = 0; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      string t = s.substr(0, i) + s.substr(j);
      if (s == t) {
        ans = true;
      }
    }
  }

  cout << (ans ? "YES" : "NO") << endl;
}

nakashiiiの自由帳

自由に書きます

ABC212 E - Safety Journey（配るDP → 貰うDPにして高速化する）

問題

考察（間に合わずTLEするバージョン）

考察（ACするバージョン）

補足

お世話になった記事、動画

競プロ用の組み合わせ前計算テンプレート（階乗、順列、組み合わせ、重複組合せ）

実装

おまけ

AtCoder Beginner Contest 246 E - Bishop 2 雑メモ（01-BFS, 枝刈りBFS）

問題

枝刈りBFS

01-BFS

実装

枝刈り全探索

01-BFS

参考

AtCoder Beginner Contest 248 E - K-colinear Line

問題

勉強になったこと

考察

難しかったポイント

「直線」を表現したいけど、普通に y=ax+b の傾き求めたら、a が少数になってしまう

直線は set に入れて、重複除去する

3 点の座標が直線上にあるかは公式使って判定

実装

感想

AtCoder Beginner Contest 247 E - Max Min

勉強になったこと

問題

前提知識

考察

方法1：条件を満たす区間に分割して、それぞれの区間に対してしゃくとり法を繰り返す

方法2：Xのインデックス、Yのインデックス、NG数値のインデックスを持ちながら、0〜N-1まで順次数え上げ

感想

競プロ精進について雑メモ

部分文字列の全探索（キーエンスプログラミングコンテスト 2019 B - KEYENCE String）

コード