AtCoder Beginner Contest 308
結果
A - New Scheme : AC(3:40)
B - Default Price : AC(12:35)
C - Standings : AC(49:48)(1ペナ)
D - Snuke Maze : AC(76:42)(1ペナ)
E - MEX : 提出無し
A - New Scheme
$${8}$$個の整数からなる数列が与えられ、それが広義単調増加であり、全ての項が$${100}$$以上$${675}$$以下かつ$${25}$$の倍数であるかを判定する問題
自分の回答
int main(){
vector<int> S(8);
for(int i = 0; i < 8; i++){
cin >> S[i];
}
bool y = true;
for(int i = 1; i < 8; i++){
if(S[i - 1] > S[i]){
y = false;
}
}
for(int i = 0; i < 8; i++){
if(S[i] % 25 != 0 || S[i] < 100 || S[i] > 675){
y = false;
}
}
printf(y ? "Yes\n" : "No\n");
}
そのまま
公式解説
省略
B - Default Price
高橋君が回転寿司で$${N}$$皿食べ、食べた料理の皿の色$${C_{i}}$$が与えられる
料理の価格は皿の色と対応し、$${D_{i}}$$色の皿の値段は$${P_{i}}$$円であり、ここで示されていない色の皿は$${P_{0}}$$円である
高橋君が食べた料理の価格の総和を求める問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
vector<string> C(N);
map<string, int> D;
vector<int> P(M);
int p0;
for(int i = 0; i < N; i++){
cin >> C[i];
}
for(int i = 0; i < M; i++){
string s;
cin >> s;
D[s] = i;
}
for(int i = -1; i < M; i++){
int n;
cin >> n;
if(i == -1){
p0 = n;
}
else{
P[i] = n;
}
}
int ans = 0;
for(string s : C){
if(D.count(s)){
ans += P[D[s]];
}
else{
ans += p0;
}
}
printf("%d\n", ans);
}
色とそのインデックスを持つmapから価格を入れたvectorにアクセス
公式解説
省略
C - Standings
$${N}$$人がコイントスを何回かし、人$${i}$$は$${A_{i}}$$回表を出し$${B_{i}}$$回裏を出した
コイントスの成功率$${(\frac{A_{i}}{A_{i}+B_{i}})}$$の高い順に、成功率が同じ場合は番号の小さい順に並び替える問題
自分の回答
int main(){
int N;
cin >> N;
vector<tuple<int, int, int>> pro(N);
for(int i = 1; i <= N; i++){
int a, b;
cin >> a >> b;
pro[i - 1]={a, b, i};
}
auto cmp=[](const tuple<int, int, int> &x, const tuple<int, int, int> &y){
int64_t a1 = get<0>(x), b1 = get<1>(x), a2 = get<0>(y), b2 = get<1>(y);
if(a2 * (a1 + b1) == a1 * (a2 + b2)){
return get<2>(x) < get<2>(y);
}
else if(a1 * (a2 + b2) < a2 * (a1 + b1)){
return false;
}
else{
return true;
}
};
sort(pro.begin(), pro.end(), cmp);
for(auto [a, b, i] : pro){
printf("%d ", i);
}
printf("\n");
}
小数を出さないようにして比較関数を作成
最初確率そのままでやってWA
公式解説
省略
D - Snuke Maze
$${H}$$行$${W}$$列のグリッドがあり、各マスには英小文字が書かれている
辺で隣接するマスに移動することを繰り返して$${(1,1)}$$から$${(H,W)}$$まで移動した時、通ったマスに書かれていた文字がs→n→u→k→e→s→…である経路が存在するかを求める問題
自分の回答
int main(){
int H, W;
cin >> H >> W;
vector<vector<char>> M(H + 2, vector<char>(W + 2, '#'));
for(int i = 1; i <= H; i++){
for(int j = 1; j <= W; j++){
cin >> M[i][j];
}
}
queue<tuple<int, int, char>> bfs;
vector<int> goi = {0, 1, 0, -1}, goj = {1, 0, -1, 0};
bfs.push({1, 1, M[1][1]});
M[1][1] = '#';
while(!bfs.empty()){
int nowi = get<0>(bfs.front()), nowj = get<1>(bfs.front());
char nowc = get<2>(bfs.front());
bfs.pop();
for(int i = 0; i < 4; i++){
int nexti = nowi + goi[i], nextj = nowj + goj[i];
if((nowc == 's' && M[nexti][nextj] == 'n') || (nowc == 'n' && M[nexti][nextj] == 'u') || (nowc == 'u' && M[nexti][nextj] == 'k') || (nowc == 'k' && M[nexti][nextj] == 'e') || (nowc == 'e' && M[nexti][nextj] == 's')){
bfs.push({nexti, nextj, M[nexti][nextj]});
M[nexti][nextj] = '#';
}
}
}
printf(M[H][W] == '#' ? "Yes\n" : "No\n");
}
今いるマスの文字を持っておいて幅優先探索
到達マスの更新タイミングを間違えてTLE
公式解説
省略
E - MEX
$${0,1,2}$$からなる長さ$${N}$$の数列$${A=(A_{1},A_{2},…A_{N})}$$と「M」「E」「X」からなる長さ$${N}$$の文字列$${S}$$が与えられる
$${\text{mex}(a,b,c)}$$を$${a,b,c}$$のいずれとも一致しない最小の非負整数とし
$${1 \leqq i \leqq j \leqq k \leqq N}$$かつ$${S_{i}S_{j}S_{k}=}$$MEXを満たす整数の組$${(i,j,k)}$$すべてにおける$${\text{mex}(A_{i},A_{j},A_{k})}$$の総和を求める問題
自分の回答
計算量削減の方法が一切思いつかなかった
公式解説
using ll = long long;
int mex(int x, int y, int z) {
for (int i = 0; i < 3; i++) {
if (x != i and y != i and z != i) return i;
}
return 3;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int &i: a) cin >> i;
string s;
cin >> s;
vector cnt_l(n + 1, vector<int>(3));
vector cnt_r(n + 1, vector<int>(3));
for (int i = 0; i < n; i++) {
cnt_l[i + 1] = cnt_l[i];
if (s[i] == 'M') ++cnt_l[i + 1][a[i]];
}
for (int i = n - 1; i >= 0; i--) {
cnt_r[i] = cnt_r[i + 1];
if (s[i] == 'X') ++cnt_r[i][a[i]];
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] != 'E') continue;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
ans += (ll) cnt_l[i][j] * cnt_r[i + 1][k] * mex(j, a[i], k);
}
}
}
cout << ans << endl;
}
https://atcoder.jp/contests/abc308/editorial/6708より
Eが出てきた時にそこ以前のMの数×以降のXの数がそのEを使ってできるMEXの数だからM,Eを数字毎に何回出たかを記録することでmexと掛けたものを足していくのか
なるほど
この記事が気に入ったらサポートをしてみませんか?