AtCoder Beginner Contest 360
A,B,C,Dの4完。
B問題に出題ミスがあったらしく、まだレートの更新は行われていない。
そこそこD問題まで早く解けた回だったので、きちんとrate反映されることだけを祈る。全員レート更新になることだけはやめてほしい。笑
A - A Healthy Breakfast
アルファベット大文字S,M,Rの3文字が並び順が変わって入力される。
'R'よりも'M'が右にあるかどうかを判定せよ、という問題。
左の文字から見ていって、先にどちらの文字が来るかで判定すればOK。
string S;
int main()
{
cin >> S;
for (int i = 0; i < S.size() ; i++)
{
if (S[i] == 'R')
{
cout << "Yes" << endl;
return 0;
}
if (S[i] == 'M')
{
cout << "No" << endl;
return 0;
}
}
return 0;
}
B - Vertical Reading
文字列$S$と$T$が与えられる。
$1≤c≤w<∣S∣$ という条件の時に、以下の整数の組が存在するか判定せよ。
$S$ を先頭から順に
$w$ 文字毎に区切ったとき、長さが
$c$ 以上の文字列の
$c$ 文字目を順番に連結した文字列が
$T$ と一致する
区切る文字$w$を1から$S$の文字列の長さまで動かしつつ、抽出する$c$文字目は1から区切る文字数$w$まで動かしながら、Tに一致する文字列になるかひたすら試していく。
int N;
string S, T;
int main()
{
cin >> S >> T;
for (int i = 1; i < S.size() ; i++)
{
for (int j = 1; j <= i ; j++)
{
string tmp;
int sep = j - 1;
while (sep < S.size())
{
tmp += S[sep];
sep += i;
}
if (tmp == T)
{
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
return 0;
}
C - Move
$N$ 個の箱があり、$i$番目の荷物は箱$A_i$に入っており、その重さ$W_i$が与えられる。
1回の移動に重さ$W_i$と同等のコストがかかる時、全ての箱の中に荷物が1つだけ入っている状態にするまでにかかる最小のコストはいくらか、という問題。
最小コストで移動させたい場合は同じ荷物が1回以上移動することはなく、どの箱に移動させるかはコストに関係ないので、同じ箱に2つ以上荷物が入っている場合は、一番移動コストの高い、重い荷物をその箱に残し、そのほかの荷物は任意の空の箱へ移動させていく。
つまり全ての荷物の重さから、それぞれの箱に入っている一番重い荷物の重さを引いた数がかかる最小のコストになる。
int N;
int A[100009];
int W[100009];
vector<int> boxex[100009];
int main()
{
cin >> N;
for (int i = 1; i <= N ; i++) cin >> A[i];
for (int i = 1; i <= N ; i++) cin >> W[i];
for (int i = 1; i <= N ; i++)
{
boxex[A[i]].push_back(W[i]);
}
ll ans = 0;
for (int i = 1; i <= N ; i++)
{
if (boxex[i].size() > 0)
{
sort(boxex[i].begin(), boxex[i].end());
for (int j = 0; j < boxex[i].size()-1; j++)
{
ans += boxex[i][j];
}
}
}
cout << ans << endl;
return 0;
}
D - Ghost Ants
数直線上に$N$匹のありがいる。それぞれの蟻は重複しない$X_i$座標におり、正負のどちらに向いているかの情報が与えられる。
それぞれの蟻が向いている方向へ毎秒1ずつ進む時、今から$T+0.1$秒までの時間ですれ違う蟻の数はいくらか、という問題。
左向きの蟻を固定し、右向きの蟻が$2 × T+0.1$進むと考えて、右向きの蟻がすれ違う左向きの蟻の数の合計が答え、と考えても同じ状況のため、以下のプログラムではその考え方を用いている。
特定の右向きの蟻1匹に注目した時、最初の位置の一番近い右側にいる左向きの蟻から、移動終了後の一番近い右側にいる左向きの蟻 -1 まですれ違うことになる。
その数を二分探索を用いて求め、全ての右向きの蟻に対して足し合わせたものが答えである。
ll N, T;
string S;
ll X[200009];
vector<ll> left_ants, right_ants;
int main()
{
// 入力
cin >> N >> T >> S;
for (int i = 0; i < N ; i++)
{
cin >> X[i];
if (S[i] == '0') left_ants.push_back(X[i]);
else right_ants.push_back(X[i]);
}
// ソート
sort(left_ants.begin(), left_ants.end());
sort(right_ants.begin(), right_ants.end());
// 答えを求める
ll ans = 0;
for (ll x : right_ants)
{
// 左向きの蟻とのすれ違いをカウント
ans += lower_bound(left_ants.begin(), left_ants.end(), x + 2 * T + 0.1) - lower_bound(left_ants.begin(), left_ants.end(), x);
}
cout << ans << endl;
return 0;
}