【c++】ABC357 A-E問題解説【ACコード付き】

# AtCoder Beginner Contest 357
A,B,C,Dの3完。

Eももう少しで到達できそうであったが、有向グラフということを気づかずにUnion-findで実装してしまった。

レートは584→635の+51となり、+50を継続するのが目標だったので最低ラインはクリア。パフォーマンスも過去最高の985となった。（早くパフォ1000の壁を超えて、水色パフォ安定的に出せるようになりたい、、！）


今週は競プロにあまり時間を割くことができなかったが、毎日ABCが継続できたのは自分を褒めたい。A,B,C問題を埋め切って、D問題埋めに入れるのを楽しみにして、これからも積み上げていきたい。

来週は空港滞在中など時間が取れそうであるので、初中級者が解くべき過去問精選100問を今週の分まで進めたいところ。

https://atcoder.jp/contests/abc357

## A - Sanitize Hands
$M$ 本の手を消毒できるボトルを持っている。

$N$ 人の宇宙人がそれぞれ $H_{i}$ 本手を持って並んでいる時、何人目の宇宙人までが全ての手を消毒できるか。

1人ずつ消毒していき、途中でなくなった場合はその人の前まで全員消毒できたと判定して数を出力する。

```cpp
int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> H[i];
	for (int i = 1; i <= N; i++)
	{
		M -= H[i];
		if (M < 0)
		{
			cout << i - 1 << endl;
			return 0;
		}
	}
	cout << N << endl;
	return 0;
}
```

## B - Uppercase and Lowercase
アルファベット大文字と小文字からなる文字列 $S$ が与えられるので、大文字か小文字か多い方に統一せよ、という問題。

大文字か小文字かはisupper()関数とislower()関数で判定できる。

大文字への変換はc = toupper(c)、小文字への変換はc = tolower(c)。

この辺りは42tokyoでC言語の基本ライブラリを実装したので知っていた。学んだことが活かせる問題で素直に嬉しい。

```cpp
string S;

int main()
{
    cin >> S;
    int up = 0;
    int low = 0;

    for (char c : S)
    {
        if (isupper(c)) up++;
        else if (islower(c)) low++;
    }

    if (up > low)
    {
        for (char &c : S) c = toupper(c);
    }
    else
    {
        for (char &c : S) c = tolower(c);
    }

    cout << S << endl;
    return 0;
}
```

## C - Sierpinski carpet
再帰関数で実装する問題。説明するのが難しいので公式の問題をほぼそのまま貼ります。

非負整数 
$K$ に対して、以下のようにレベル 
$K$ のカーペットを定義します。

レベル 
0 のカーペットは黒いマス 
1 個のみからなる 
1×1 のグリッドである。
$K>0$ のとき、レベル 
$K$ のカーペットは 
$3^K × 3^K$  のグリッドである。 このグリッドを 
$3^{K-1} × 3^{K - 1} $
  のブロック 
9 個に分割したとき、
中央のブロックはすべて白いマスからなる。
他の 
8 個のブロックは、レベル 
($K$−1) のカーペットである。
非負整数 
N が与えられます。
レベル 
N のカーペットを出力の形式に従って出力してください。

```cpp
long long N, tmp;
bool board[730][730];

bool ft_check(int i, int j, int size)
{
    // ずっとsizeを小さくしていって、一度も中央のグリッドに属さなければfalse('#')
    if (size == 1) return false;
    
    int newSize = size / 3;
    // 中央のグリッドだったらtrue('.')
    if ((i / newSize) % 3 == 1 && (j / newSize) % 3 == 1) return true;
    return ft_check(i, j, newSize);
}

int main()
{
    cin >> N;
    tmp = 1;
    for (int i = 1; i <= N; i++) tmp *= 3;
    
    for (int i = 0; i < tmp; i++)
    {
        for (int j = 0; j < tmp; j++)
        {
            // そのマスが('.')か('#')を再帰関数で判定
            board[i][j] = ft_check(i, j, tmp);
        }
    }
    
    for (int i = 0; i < tmp; i++)
    {
        for (int j = 0; j < tmp; j++)
        {
            if (board[i][j] == false) cout << "#";
            else cout << ".";
        }
        cout << endl;
    }
    
    return 0;
}
```

## D - 88888888
正整数 
N に対して、
N を 
N 個つなげた整数を 
V 
N
​
  とします。
より厳密には、
N を文字列とみなしたものを 
N 個連結し、 それを再度整数とみなしたものを 
$V_{N}$とします。
例えば、
$V_{3}=333$, 
$V_{10}=10101010101010101010$ です。

V 
N
​
  を 
998244353 で割った余りを求めてください。

コンテスト中は最小二乗法を使用して実装したが、解説を見てフェルマーの小定理を活用して解く方法を知った。

ついでに気になったのでフェルマーの小定理をヨビノリさんの動画で学んで、証明をqiitaに備忘録としてアップしておいた。

```cpp
const long long MOD = 998244353;

// 繰り返し二乗法を使って (base^exp) % mod を計算する関数
long long mod_exp(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    string N_str;
    cin >> N_str;
    long long N = stoll(N_str);

    // N の桁数を計算
    int length = N_str.length();

    // 10^length を計算
    long long ten_pow_len = mod_exp(10, length, MOD);

    // (10^(length * N) - 1) を計算
    long long ten_pow_len_N = mod_exp(ten_pow_len, N, MOD);
    long long numerator = (ten_pow_len_N - 1 + MOD) % MOD;  // 負数にならないように調整

    // (10^length - 1) を計算
    long long denominator = (ten_pow_len - 1 + MOD) % MOD;  // 負数にならないように調整

    // 分母の逆元を計算
    long long denominator_inv = mod_exp(denominator, MOD - 2, MOD);

    // V_N の余りを計算
    long long result = (N % MOD * numerator % MOD) * denominator_inv % MOD;

    cout << result << endl;

    return 0;
}

```

## E - Reachability in Functional Graph

$N$ 辺 $N$ 頂点、それぞれの点から1箇所へ有向辺が伸びているこのグラフは、**Functional Graph**と呼ばれるグラフらしいです。

Functional Graphの性質として、以下のものがあるらしいです。証明は[ABC256 E - Takahashi's Anguish 解説](https://atcoder.jp/contests/abc256/editorial/4135)に。

> $G$ の連結成分が $K$ 個あって、$C_1, C_2, \ldots, C_K$ とする。このとき、各連結成分には閉路が $1$ つだけ存在する。

functional graphの性質を使用し、深さ優先探索ft_dfs()で閉路を探索し、ft_depth()で深さを調べるように実装しましたが、半分以上のテストケースでREが出てしまっています。

dfs(深さ優先探索)を用いて閉路の探索と、各頂点の深さを求める。

テストケース一部TLEになったが、stackでdfsを管理したらACできた。

```cpp
long long N;
vector<long long> A;
vector<long long> depth;
vector<bool> visited, in_stack;

void dfs(long long v, stack<long long>& stk) {
    visited[v] = true;
    in_stack[v] = true;
    stk.push(v);
    
    long long new_place = A[v];
    if (!visited[new_place]) {
        dfs(new_place, stk);
    } else if (in_stack[new_place]) {
        // 閉路検出
        long long cycle_size = 0;
        while (stk.top() != new_place) {
            depth[stk.top()] = 0;
            in_stack[stk.top()] = false;
            stk.pop();
            cycle_size++;
        }
        depth[new_place] = 0;
        in_stack[new_place] = false;
        stk.pop();
        cycle_size++;
        for (int i = 0; i < cycle_size; ++i) {
            depth[new_place] = cycle_size;
            new_place = A[new_place];
        }
    }
    
    if (!stk.empty() && depth[v] == -1) {
        depth[v] = depth[A[v]] + 1;
        in_stack[v] = false;
        stk.pop();
    }
}

int main() {
    // 入力
    cin >> N;
    A.resize(N + 1);
    depth.resize(N + 1, -1);
    visited.resize(N + 1, false);
    in_stack.resize(N + 1, false);
    
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    // DFSを用いて閉路を見つける
    stack<long long> stk;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i, stk);
        }
    }
    
    // 解を求める
    long long ans = 0;
    for (int i = 1; i <= N; i++) ans += depth[i];
    cout << ans << endl;
    
    return 0;
}

```