arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC089 D - Practical Skill Test を解いてみた

問題リンク

atcoder.jp


問題概要

 H W 列のマス目がある。マス目には 1 H \times W の整数が重複なく書かれており、マス (i, j)に書かれている整数は  A _ {ij} である。 |x-i| + |y-j| のコストをかけてマス  (i, j) からマス  (x, y) に移動させることができる。
 Q 個のクエリが与えられる。 i 個目のクエリでは以下の処理を行う。

  • 初めに駒が、整数  L _ i に置かれている。
  • 駒の置かれているマスに書かれている整数を  x とする。 x R _ i でない限り、 x+D のマスに移動することを繰り返す。 x R _ i に一致したら終了する。
  • ただし、 R _ i - L _ i D の倍数になることは保証されている。

それぞれのクエリに対して、移動にかかるコストの総和を求めよ。

例:
f:id:arimatti:20210618102854j:plain

制約

 1 \leq H, W \leq 300
 1 \leq Q \leq 10 ^ 5


ポイント

  • 愚直に 1 クエリごとに  L から  R までたどって 総コストを求めると  O(QHW/D) かかり間に合わないため、各クエリに高速に答える工夫が必要である。
  • マス目に書かれているある数  i から  i+D への移動コストを図にすると以下のようになる。

f:id:arimatti:20210618114448j:plain

  • クエリで問われていることが( d-1 個飛ばしであるが)区間の総和であることを考えると累積和が使えそうである。
  • 自分より右側に辿れるだけ辿った時の総コストを  a[i] と表すと、 L から  R の総コストは  a[L] - a[R] で表せることがわかる。

f:id:arimatti:20210618142015j:plain

  • 「自分より右側に辿れるだけ辿った時の総コスト」を求める際も工夫が必要。前から求めると  O((H*W) ^ 2) かかり間に合わない。これを後ろから求めると、漸化式的に a[i] = a[i+D] + (i → i+D のコスト) で計算でき、 O(H*W) で収まる。

f:id:arimatti:20210618140044j:plain


コード

※問題は 1-indexed であるが 0 - indexed に変換している

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  int h, w, d;
  cin >> h>> w >> d;
  int n = h*w;
  vector<vector<int>> A(h, vector<int>(w));
  rep(i, h) rep(j, w) {
    cin >> A[i][j];
    A[i][j]--;
  }
  map<int, P> mp; // キー:マス目の数字、バリュー: マス目(i, j)
  rep(i, h) rep(j, w) mp[A[i][j]] = {i, j};

  vector<int> a(n); // 自分より右に辿れるだけ辿った時の総コストを格納
  for (int i=n-1; i>=0; i--) {
    if (i+d > n) continue;
    int vx = mp[i].first;
    int vy = mp[i].second;
    int ux = mp[i+d].first;
    int uy = mp[i+d].second;
    int cost = abs(vx-ux)+abs(vy-uy);
    a[i] = a[i+d] + cost;
  }
  int q;
  cin >> q;
  rep(iq, q) {
    int l, r;
    cin >> l >> r;
    l--; r--;
    int ans = a[l] - a[r];
    cout << ans << endl;
  }
  return 0;
}

ABC007 D - 禁止された数字 を解いてみた

問題リンク

atcoder.jp

問題概要

正整数  A, B が与えられる。 A 以上  B 以下の整数のうち,桁に  4 または  9 を含むものがいくつあるか求めよ。

制約

 1 \leq A \leq B \leq 10 ^ {18}

ポイント

  • 桁 DP の典型問題(?)。
  • DP 遷移する上で、管理しておきたいのは ①先頭何桁を見てきたか、②その中で既に 4 or 9 を含んでいるか、③ 既に  N 未満であることが確定しているか。①③は 桁DPにおける基本の管理事項で、そこに本問題特有の②が加わった形である。
  • したがって、dp テーブルとして dp[頭から何桁目か][ 4 or 9 を含むか][整数  N 未満か] を設定する。
  •  f(N)=「上記の DP を行い  1 以上  N 以下で 問題の条件を満たすものの個数を返す関数」とすると、答えは  f(B)- f(A-1) で求まる、

感想

桁 DP は解き方のテンプレートがあって、何問か解いて慣れてきた気がする。
こちらの記事が参考になる。
Digit DP 入門 - torus711 のアレ
桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜 - けんちょんの競プロ精進記録

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

ll f (string s) {
  // dp[i桁目][4or9を含んでいるか][n未満かどうか]
  ll dp[20][2][2];
  rep(i, 20) rep(j, 2) rep(k, 2) dp[i][j][k] = 0;
  dp[0][0][0] = 1;
  int n = s.size();
  rep(i, n) rep(j, 2) rep(k, 2) {
    int nd = s[i] - '0';
    rep(d, 10) {
      int ni = i+1, nj = j, nk = k;
      if (d == 4 || d == 9) nj |= 1;
      if (k == 0) {
        if (d > nd) continue;
        if (d < nd) nk = 1;
      }
      dp[ni][nj][nk] += dp[i][j][k];
    }
  }
  return dp[n][1][0] + dp[n][1][1];
}

int main() {
  ll s, t;
  cin >> s >> t;
  s--;
  string ss = to_string(s);
  string tt = to_string(t);
  ll ans = f(tt) - f(ss);
  cout << ans << endl;
  return 0;
}

ABC204 C - Tour を解いてみた

問題リンク

atcoder.jp

問題概要

 N 個の都市と  M 個の道路がある。道路  i を通って都市  A _ i から 都市  B _ i へ行くことができる。どこかの都市から出発し、 0 本以上の道路を通って、どこかの都市に到達することを考えるとき、スタート地点とゴール地点の組み合わせはいくつあるか。

制約

 2 \leq N \leq 2000
 0 \leq M \leq min(2000, N(N-1))

ポイント

  • あるスタート地点から BFS や DFS で到達できる都市を探索する。
  • スタート地点をすべて試す。

コード(BFS)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  int n, m;
  cin >> n >> m;

  // to[a] = {aから行ける都市の集合}
  vector<vector<int>> to(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    //都市を1はじまりから0はじまりにする
    a--; b--; 
    to[a].push_back(b);
  }

  int ans = 0;
  // スタートする都市をすべて試す
  rep(i, n) {
    // BFS
    queue<int> q;
    q.push(i);

    // visited:各都市に訪れることができるか
    vector<bool> visited(n, false);
    visited[i] = true;
    while(!q.empty()) {
      int v = q.front(); q.pop();
      for (int next_v : to[v]) {
        if (visited[next_v]) continue;
        visited[next_v] = true;
        q.push(next_v);
      }
    }
    rep(j, n) if (visited[j]) ans++;
  }
  cout << ans << endl;
  return 0;
}

コード(DFS)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

vector<vector<int>> to;
vector<bool> visited;

void dfs(int v) {
  if (visited[v]) return;
  visited[v] = true;
  for (int next_v : to[v]) {
    dfs(next_v);
  }
  return;
}

int main() {
  int n, m;
  cin >> n >> m;

  // to[a] = {aから行ける都市の集合}
  to.resize(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    //都市を1はじまりから0はじまりにする
    a--; b--; 
    to[a].push_back(b);
  }

  int ans = 0;
  // スタートする都市をすべて試す
  rep(i, n) {
    visited.assign(n, false);
    dfs(i);
    rep(j, n) if (visited[j]) ans++;
  }
  cout << ans << endl;
  return 0;
}

ABC204 B - Nuts を解いてみた

問題リンク

atcoder.jp

問題概要

 N 本の木があり、 i 番目の木には  A _ i 個の木の実がなっている。次のルールに従って、全ての木から木の実を収穫する。

  • 木の実が  10 個以下の木からは木の実を収穫しない。
  • 木の実が  10 個より多い木からは木の実を  10 個残して残り全てを収穫する。

収穫する木の実の合計は何個になるか。

制約

 1 \leq N \leq 1000
 1 \leq A _ i \leq 1000

ポイント

  • 木の実が  10 個以下の木からは  0 個の木の実を収穫すると考えると、各木からの収穫量は  max(A[i]-10, 0) で表すことができる。
  • for 文を回して上記を足しこんでいけば答えとなる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int ans = 0;
  rep(i, n) ans += max(a[i]-10, 0);
  cout << ans << endl;
  return 0;
}

ABC204 A - Rock-paper-scissors を解いてみた

問題リンク

atcoder.jp

問題概要

3 人でじゃんけんをする。うち 2 人が出した手を表す文字  x, y が与えれる。 グーは 0 、チョキは 1、パーは 2 で表される。じゃんけんがあいことなるときの手を表す文字を出力しなさい。

制約

 x, y 0,1, 2 のいずれか

ポイント

  • じゃんけんがあいことなるのはすべての手が同じとき or すべての手が異なるとき。
  • したがって、 x == y であれば、 x を出力し、 x \ != y であればすべての手が異なる場合の合計値が  3 になることから  3-x-y を出力すればよい。

別解

  • あいことなるのは  (0, 0, 0), (1, 1, 1), (2, 2, 2), (0, 1, 2) の組み合わせがあり、全ての組み合わせで和が 3 の倍数となることがわかる。
  • したがって、 ans = (6-x-y)\%3 で簡単に求めることもできる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  int x, y;
  cin >> x >> y;
  if (x != y) cout << 3-x-y << endl;
  else cout << x << endl;
  return 0;
}

コード(別解)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  int x, y;
  cin >> x >> y;
  cout << (6-x-y)%3 << endl;
  return 0;
}

ABC205 C - POW を解いてみた

問題リンク

atcoder.jp

問題概要

3 つの整数  A, B, C が与えられるので、 pow(A, C) pow(B, C) の大小を比較せよ。

制約

 -10 ^ 9 \leq A, B \leq 10 ^ 9
 1 \leq C \leq 10 ^ 9

ポイント

  • 単純に pow を計算するととんでもない桁数になるので工夫が必要。
  •  C の偶奇に着目する。 x ^ C C が偶数の時、偶関数、 C が奇数の時、奇関数となる。
  • 単調増加性を考えると、 C が偶数の時は  abs(A), abs(B) の大小を比較すればよく、 C が奇数の時はそのまま  A, B の大小を比較すればよい。

f:id:arimatti:20210615112340j:plain

別解

  •  C の大きさは問題ではなく偶奇にのみ着目すればよいので、 C が偶数ならば  C=2、奇数ならば  C=1 としてしまう。 pow(A, C) pow(B, C) は十分計算可能な大きさとなるので計算結果を大小比較する。

感想

コンテスト中は焦って、無限 if 文を書き、バグを発生させ、少なからぬ時間を浪費しました。コードを書く前にじっくりと考察した方が結局は速かったと思います。良い教訓となった問題でした。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c%2 == 0) {
    a = abs(a);
    b = abs(b);
  }
  if (a > b) cout << ">" << endl;;
  if (a == b) cout << "=" << endl;;
  if (a < b) cout << "<" << endl;;
  return 0;
}

コード(別解)

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  c = 2 - c%2;
  if (pow(a, c) > pow(b, c)) cout << ">" << endl;;
  if (pow(a, c) == pow(b, c)) cout << "=" << endl;;
  if (pow(a, c) < pow(b, c)) cout << "<" << endl;;
  return 0;
}

ABC082 C - Good Sequence を解いてみた

問題リンク

atcoder.jp

問題概要

長さ N の正整数の列  a = (a _ 1, a _ 2, \cdots. a _ N) が与えられる。各要素  x について、 a に値  x がちょうど  x 個含まれるように要素を取り除くとき、取り除く要素の個数の最小値を求めよ。

例:
 a = \{2, 4, 3, 3, 4, 3, 3, 2\} の場合、要素  3 1 個と  4 2 個取り除くと  a = \{2, 3, 3, 3, 2\} 2 2 個、 3 3 個)となり目的の数列が得られる。取り除く最小の要素数 3 個。

制約

 1 \leq N \leq 10 ^ 5
 1 \leq a _ i \leq 10 ^ 9

ポイント

  • 要素  x の個数が  x より小さい場合、すべて取り除くしかない。上記例で言うと要素  4 はすべて取り除くしかない。
  • 要素  x の個数が  x 以上の場合、「要素  x の個数 -  x 」が取り除く要素の最小の個数。
  • 各要素に対して上記を調べて足し合わせたものが答えとなる。つまり、各要素が何個あるかを管理すればよい。 a _ i の上限が大きいので vector ではなく map で管理する。

感想

貪欲的(?)にやればよいという考察は難しくはないが、各要素の個数管理を map で行うという点が肝であったと思う。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  map<int, int> mp;
  rep(i, n) {
    int a;
    cin >> a;
    mp[a]++;
  }
  int ans = 0;
  for (auto v : mp) {
    if (v.first <= v.second) ans += v.second-v.first;
    else ans += v.second;
  }
  cout << ans << endl;
  return 0;
}