AtCoder 勉強記録[C++] その39

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
[私のアカウント](https://atcoder.jp/users/nanami_brother)
[解いた問題](https://kenkoooo.com/atcoder/#/table/nanami_brother)
# 本日解いた問題
## B - Number Box
[B - Number Box](https://atcoder.jp/contests/abc258/tasks/abc258_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define m 998244353

vector<ll> x = {1, -1, 0, 0, 1, 1, -1, -1};
vector<ll> y = {0, 0, 1, -1, 1, -1, 1, -1};

int main() {
  ll n;
  cin >> n;
  vector<vector<ll>> a(n, vector<ll>(n));
  
  rep(i, n) rep(j, n) {
    char c;
    cin >> c;
    a[i][j] = c-'0';
  }
  ll res = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < 8; k++){
        ll now = 0;
        ll dx = i, dy = j;
        for(int l = 0; l < n; l++){
          now *= 10;
          now += a[dx][dy];
          dx += x[k];
          dy += y[k];
          dx += n;
          dy += n;
          dx %= n;
          dy %= n;
        }
        res = max(res, now);
      }
    }
  }
  cout << res << endl;
}

```
### 解法
まず、スタート地点をすべてのマス目の中で全探索する。その後、決めたスタート地点から8方向すべての場合を探索し、その中で1番大きいものを出力する。
## B - Everyone is Friends
[B - Everyone is Friends](https://atcoder.jp/contests/abc272/tasks/abc272_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, m;
  cin >> n >> m;
  vector<vector<ll>> x(n, vector<ll>(0));
  vector<ll> k(n);
  for(int i = 0; i < n; i++){
    cin >> k[i];
    for(int j = 0; j < k[i]; j++){
      ll a;
      cin >> a;
      x[i].push_back(a-1);
    }
  }
  vector<vector<bool>> jud(n, vector<bool>(n));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < k[i]-1; j++){
      for(int l = j+1; l < k[i]; l++){
        jud[x[i][j]][x[i][l]] = true;
        jud[x[i][l]][x[i][j]] = true;
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(i == j) continue;
      if(!jud[i][j]) {
        cout << "No" << endl;
        exit(0);
      }
    }
  }
  cout << "Yes" << endl;
}
```
### 解法
2人が同じ舞踏会に参加したかを判定する2次元配列を用意しておき、2人が同じ舞踏会に参加している場合に`True`とすることで判定できる。最後に`jud[i][j]`において`i=j`以外の場合において、`false`が存在する場合`No`、存在しない場合`Yes`を出力する。
## C - digitnum
[C - digitnum](https://atcoder.jp/contests/abc238/tasks/abc238_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define m 998244353
#define inv2 499122177

int main() {
  ll n;
  cin >> n;
  ll res = 0;
  ll p = 10;
  ll tmp, x;
  for(int i = 1; i <= 18; i++){
    ll l = p / 10;
    ll r = min(n, p-1);
    if(l<=r){
      x = r-l+1;
      x %= m;
      tmp = x;
      tmp *= (x+1);
      tmp %= m;
      tmp *= inv2;
      tmp %= m;
      res += tmp;
      res %= m;
    }
    p *= 10;
  }
  cout << res << endl;
}
```
### 解法
1~18において`f(x)`の値の法則性を考えることで計算することができる。オーバーフローを起こさないために計算行うたびに`mod 998244353`を取る。
## C - 1111gal password
[C - 1111gal password](https://atcoder.jp/contests/abc242/tasks/abc242_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define m 998244353

int main() {
  ll n;
  cin >> n;
  vector<vector<ll>> dp(n+10, vector<ll>(10));
  for(int i = 1; i <= 9; i++) dp[1][i] = 1;
  for(int i = 2; i <= n; i++){
    for(int j = 1; j <= 9; j++){
      for(int k = max(1, j-1); k <= min(9, j+1);k++){
        dp[i][k] += dp[i-1][j];
        dp[i][k] %= m;
      }
    }
  }
  ll res = 0;
  for(int i = 1; i <= 9;i++){
    res += dp[n][i];
    res %= m;
  }
  cout << res << endl;
}
```
### 解法
簡単なDPを用いて解いていく。すべての桁において、i+1桁の求める数はi桁の数の末尾に-1,+0,+1した値であるため、1桁目からDPを用いて考えることで結果が求まる。