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;
}