AtCoder Beginner Contest 367

A,B,Cの3完。

レートは898→の-22となり、レート900の壁にまた阻まれてしまった。

若干の停滞期に入っている気がして、9月の入水の実現可能性が低くなってきているのが悲しい。

ただ、まだまだ成長の余白は大きく感じるので、ここで辞めてしまいたくはない。

C問題までは時間をかければ確実に解けるようになってきたので、D問題は安定的に解ける、E問題も時々解ける、というレベルに早く到達したい。

A - Shout Everyday

久しぶりにA問題に5分以上かけてしまった。

問題としては、就寝時間と起床時間を与えられるので、特定の時間に起きているか寝ているかを判定するもの。

日をまたぐ場合とそうでない場合をシンプルに場合分けをすれば良いのだが、変数を見間違えたりして少し手間取ってしまった。問題文をちゃんと読もう。（自戒）

ll A, B, C;

int main()
{
	cin >> A >> B >> C;
	if (B < C)
	{
		if (!(B < A && A < C))
		{
			cout << "Yes" << endl;
			return 0;
		}
	}
	else
	{
		if (!(A < C || B < A))
		{
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

B - Cut .0

この問題もそこそこ時間をかけてしまい、A問題と合わせてここまで25分かかっている。

小数点以下3桁までの数字を受け取り、最も末尾の桁が0であったらそれは省略して出力せよ、という問題。

解説を見て驚愕したが、なんとcppだと以下の通りただ入力を受け取って出力するのみでACらしい。その仕様を知っていれば5秒で終わる問題だった泣

// 解説見て驚愕したプログラム
int main()
{
  double x;
  cin >> x;
  cout << x << "\n";
  return 0;
}

自分は小学生みたいなゴリゴリ分岐をしてしまったのでエラーも起きやすいし時間もかかってしまったが、while(x.back()=='0'){x.pop_back();}のように条件判定と末尾の削除をstring型の特性を活かして行うべきであった。stringにこのようなメソッドがあるのかと勉強になった。

float N;

int main()
{
    cin >> N;
    string S = to_string(N);

	int i = 0;
    while (true)
    {
		if (S[i] == '.')
		{
			if (S[i+1] == '0' && S[i+2] == '0' && S[i+3] == '0')
			{
				cout << endl;
				return 0;
			}
			cout << S[i];
			break;
		}
		cout << S[i];
		i++;
    }
	i++;
	if (S[i+1] == '0' && S[i+2] == '0')
	{
		cout << S[i];
		cout << endl;
		return 0;
	}
	if (S[i+2] == '0')
	{
		cout << S[i] << S[i+1];
		cout << endl;
		return 0;
	}
	cout << S[i] << S[i+1] << S[i+2];
    cout << endl;
    return 0;
}

C - Enumerate Sequences

以下の2つの条件を満たす長さ $N$ の整数列を辞書順で小さい方から順に全て出力せよ、という問題。

$i$ 番目の要素は $1$ 以上 $R_i$ 以下
総和が $K$ の倍数

問題の制約的に $N \leq 8$ と非常に小さいので、maxでも $10^8 - 10^7$のループで計算できるので、 $N$ 桁の数を全探索する方針をとった。

ll N, K;
ll R[1000009];
vector<ll> G[1000009];

bool ft_check(ll n)
{
	string s = to_string(n);
	for (int i = 0; i < N; i++)
	{
		if (s[i] > R[i]) return false;
		else if (s[i] < R[i]) return true;
	}
	return true;
}

int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> R[i];
	for (int i = pow(10, N); i < pow(10, N+1); i++)
	{
		if (ft_check(i)) cout << i << endl;
	}
	return 0;
}

D - Pedometer

池の周りに休憩所が $N$ 個あり、それぞれの区間の距離が与えられる。

休憩所2箇所をピックした時、時計回りに移動した場合の区間の長さが $M$ の倍数となるような区間の組み合わせの数を求めよ、という問題。

解説を読んで累積和を実装したのが以下のプログラム。

2箇所のピックは $N \times (N-1) / 2$ 通りあるので、単純に計算していると $O(N^2)$ となり、$N \leq 2 \times 10^5$ なので間に合わない。ループ1回で計算できるように工夫する必要がある。

今回は、累積和を使って、区間の和を $M$ で割った余りを計算している。その際、余りが同じ区間の数をカウントしているので、そのカウントを使って計算していけば、 $O(N)$ で計算できる。

単純な累積和ではないのでハードルが高かったが、このような問題を解けるようになると気持ちがいいのだろうなと思う。

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<ll> cum_mod(N + 1, 0);
    for (int i = 0; i < N; i++) {
        cum_mod[i + 1] = (cum_mod[i] + A[i]) % M;
    }
    ll L = cum_mod[N];
    ll ans = 0;
    vector<ll> cnt(M, 0);
    for (int i = 0; i < N; i++)
    {
        ans += cnt[cum_mod[i]];
        ans += cnt[(cum_mod[i] - L + M) % M];
        cnt[cum_mod[i]]++;
    }
    cout << ans << endl;
    return 0;
}