AtCoder Beginner Contest 365

A,B,Cの3完。

レートは880→863の-17となり、ついにレートダウンを経験してしまった。

ABCはかなり迅速に解けたが、D問題のDPに手こずって結局ACすることができなかった。

先週先々週とDPの練習問題を解いていたが、DPの脳みその使い方が薄れている感じがして

A - Leap Year

いわゆるFizzBuzz問題。

整数 $Y$ が与えられるので、以下の条件にしたがって出力せよ。

$Y$ が $4$ の倍数でない年は $365$ 日
$Y$ が $4$ の倍数で、かつ $100$ の倍数でない年は $366$ 日
$Y$ が $100$ の倍数で、かつ $400$ の倍数でない年は $365$ 日
$Y$ が $400$ の倍数である年は $366$ 日

ベン図を意識して、条件が厳しいところから先に出力していけばOK。

ll N;

int main()
{
	cin >> N;
	if (N % 400 == 0) cout << 366 << endl;
	else if (N % 100 == 0) cout << 365 << endl;
	else if (N % 4 == 0) cout << 366 << endl;
	else  cout << 365 << endl;
	return 0;
}

B - Second Best

要素 $N$ 個の整数列が与えられる。整数列の要素の全てが異なる値の時、2番目に大きい要素は整数列の何番目にあるか、という問題。

要素の値とその値があった場所を記録しておきソートし、2番目に大きな要素の場所を出力すればOK。

ll N;
ll A[1000009];
vector<pair<ll, ll>> dp;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		dp.push_back({A[i], i});
	}
	sort(dp.begin(), dp.end());
	cout << dp[N - 2].second + 1 << endl;
	return 0;
}

C - Transportation Expenses

以下公式の問題をほぼそのまま掲載します。

あるイベントには $N$ 人が参加し、$i$ 番目の人の交通費は $A_i$ 円でした。

イベントの主催者である高橋くんは、交通費補助額の上限額 $x$ を設定して、人 $i$ には交通費補助額として $\min(x, A_i)$ 円を支給することとしました。ここで $x$ は非負整数である必要があります。

高橋くんの予算が $M$ 円であり、$N$ 人に渡す交通費補助額の総和を $M$ 円以下にしたいとき、交通費補助額の上限額 $x$ は最大でいくらにできますか？

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりにinfiniteを出力してください。

可惜得られる$A_i$ を昇順にソートし、小さい人から1人ずつの$A_i$ が $x$ にすることを考える。一番大きな$A_i$ を $x$ にした場合でも $M$　に満たない場合はいくらでも上限を上げられるので infinite を出力する。

途中で $M$ を超える場合は、$i + 1$ 人分 $x$まで上げているので、1ずつ減らして$M$ を超えないラインを模索する。

ll N, M;
vector<vector<ll>> dp;

int main()
{
	cin >> N >> M;
	vector<ll> A(N);
	ll total = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		total += A[i];
	}
	sort(A.begin(), A.end());
	total += A[0];
	int i = 0;
	while (i < N - 1)
	{
		if (total >= M) break;
		total += (A[i + 1] - A[i]) * (i + 1);
		i++;
	}
	if (i == N - 1 && total < M)
	{
		cout << "infinite" << endl;
		return 0;
	}
	if (i != 0) i--;
	ll ans = A[i+1];
	while (total < M)
	{
		total -= i + 1;
		ans -=	1;
	}
	cout << ans << endl;
	return 0;
}

D - AtCoder Janken 3

以下公式の問題の説明を引用します。

高橋くんと青木くんが $N$ 回のじゃんけんを行いました。

青木くんが出した手は $R, P, S$ からなる長さ $N$ の文字列 $S$ で表されます。青木くんが $i$ 回目 ($1 \leq i \leq N$) のじゃんけんに出した手は、$S$ の $i$ 文字目が $R$ のときグー、$P$ のときパー、$S$ のときチョキです。

高橋くんが出した手について、次の条件を満たすことがわかっています。

高橋くんは青木くんに1度も負けなかった。
$i = 1, 2, \ldots, N - 1$ について、高橋くんが $i$ 回目のじゃんけんに出した手と $i + 1$ 回目のじゃんけんに出した手は異なる。

高橋くんが勝った回数としてありえる最大値を求めてください。

ここで、条件を満たすような高橋くんの手が存在することが証明できます。

$N$ の制約が $10^5$ オーダーだったので、for分1回分なら回しても大丈夫なラインである。

#include <iostream>
using namespace std;

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

    int rock = 0;
	int scissors = 0;
	int paper = 0;

    for (int i = 0; i < N; ++i)
	{
        char c = S[i];
        int new_rock = max(scissors, paper);
        int new_scissors = max(rock, paper);
        int new_paper = max(rock, scissors);

        if (c == 'R')
		{
            new_scissors = 0;
            new_paper++;       
        }
		else if (c == 'S')
		{
            new_paper = 0;
            new_rock++;
        }
		else if (c == 'P')
		{
            new_rock = 0;
            new_scissors++;
        }

        // 新しい値を元の変数に戻す
        rock = new_rock;
        scissors = new_scissors;
        paper = new_paper;
    }

    // rock, scissors, paper の中で最も大きい値を出力
    int ans = max(max(rock, scissors), paper);
    cout << ans << endl;

    return 0;
}

// コンテスト中に提出しようとしていたWAコード。
ll N;
string S;

int main() {
    cin >> N >> S;
    ll ans = 1;

    // ジャンケンの勝つ手をマッピング
    map<char, char> winHand;
    winHand['R'] = 'P'; // R (グー) に勝つ手は P (パー)
    winHand['P'] = 'S'; // P (パー) に勝つ手は S (チョキ)
    winHand['S'] = 'R'; // S (チョキ) に勝つ手は R (グー)

    // 高橋くんが初めに出す手を決定
    char prevHand = winHand[S[0]];
    char prepreHand = prevHand; // 2回前の手は初回は同じ手と仮定

    for (int i = 1; i < N; i++) {
		if (S[i] == S[i-1])
		{
			// if (i != N -1 && S[i -1] != S[i - 2])
			// {
			// 	prepreHand = prevHand;
			// }
			if (winHand[S[i]] != prevHand)
			{
				ans++;
				prevHand = winHand[S[i]];
			}
			else 
			{
				prevHand = S[i];
			}
        } else {
            if (i != N-1 && S[i-1] == S[i-2] && winHand[S[i]] == prevHand && prepreHand != S[i-1])
			{
				prepreHand = winHand[S[i-1]];
				prevHand = winHand[S[i]];
			}
			else if (winHand[S[i]] != prevHand)
			{
				ans++;
				prepreHand = prevHand;
				prevHand = winHand[S[i]];
			}
			else
			{
				prepreHand = prevHand;
				prevHand = S[i];
			}
        }
    }

    cout << ans << endl;
    return 0;
}