Zenn
👌

【ABC291】AtCoder Beginner Contest 291 A-D 振り返り【Python】【C++】

2023/03/10に公開
C++
Python
AtCoder
tech

https://atcoder.jp/contests/abc291

A - camel Case

Pythonの場合、str型のメソッドのstr.isupper()で大文字の判定をする。C++の場合。isupper(s)で大文字の判定をする。

Python
s = list(input())
 
for i, s_i in enumerate(s):
    if s_i.isupper():
        print(i + 1)
        break
C++
#include<bits/stdc++.h>
using namespace std;
int main() {
    string S;
    cin >> S;
    
    for (int i = 0; i< S.size(); i++){
        if (isupper(S[i])){
            cout << (i+1) << endl;
        }
    }

    return 0;
}

B - Trimmed Mean

評点で昇順ソートを行い、N+1番目から4N番目の平均点を求める。これは先頭からN個取り除いた後に、末尾からN個取り除いた残りの平均点を求めることと同義である。リストの前後を取り除く場合はPythonのスライスを使うことで実装が楽になる。

Python
from statistics import mean

n = int(input())  # 合計人数は 5*n
score_list = list(map(int, input().split()))

score_list = sorted(score_list)  # 昇順ソート

accurary_point = score_list[n:-n]
print(mean(accurary_point))
C++
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n; // 合計人数は 5*n
    cin >> n;

    vector<int> score_vec(n*5); // 評点の配列
    for (int i = 0; i<n*5; i++){
        cin >> score_vec.at(i);
    }

    sort(score_vec.begin(), score_vec.end());

    int sum_point = 0;
    for (int i = n; i<n*4; ++i){
        sum_point += score_vec[i];
    }
    double takahashi_point = (double)sum_point / (double)(3*n);
    cout << takahashi_point << endl;
}

公式解説

C++には、基準となる要素よりも小さい要素が前に来るよう並べ替える std:: nth_elementという関数があるようだ。それを使えば計算時間をO(N)まで減らせるらしい。
https://cpprefjp.github.io/reference/algorithm/nth_element.html

C - LRUD Instructions 2

重複のない値を扱う配列の場合はsetを使うと計算量を大幅に削減できる。Pythonの場合、setの中に配列を挿入することができないため (正確に言えばlistがハッシュ不可能だから)、setにはタプルを挿入する。アルゴリズムの概略は、移動先の座標(x,y)がsetに存在するかどうかを確認し、存在すればYes。しなければ、移動済み座標の集合であるセットに移動後の座標を追加する。以下の処理を繰り返す。

Python
n = int(input())
command_list = list(input())

moved_position = {(0, 0)}  # 移動済みの座標
now_position = [0, 0]

for command in command_list:
    if command == "R":
        now_position[0] += 1
    elif command == "L":
        now_position[0] -= 1
    elif command == "U":
        now_position[1] += 1
    else:
        now_position[1] -= 1

    if tuple(now_position) in moved_position:
        print("Yes")
        exit()
    moved_position.add(tuple(now_position))
print("No")
C++
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    string command_list = "";
    cin >> command_list;

    vector<int> now_position{0, 0}; // 現在の座標 pairクラスでも良い

    set<vector<int>> moved_position;
    moved_position.insert({0,0});

    for (int i = 0; i<command_list.length(); i++){
        char command = command_list[i]; // コマンドの一文字
        if (command == 'R'){
            now_position[0] += 1;
        } else if (command == 'L'){
            now_position[0] -= 1;
        } else if (command == 'U'){
            now_position[1] += 1;
        } else {
            now_position[1] -= 1;
        }

        if (moved_position.find(now_position) != moved_position.end()){
            cout << "Yes" << endl;
            return 0;
        }
        moved_position.insert(now_position);
    }
    cout << "No" << endl;
}

D - Flip Cards

コンテスト中は隣り合う2枚のカードが同じになる組み合わせを求め、全体からの差分を取ることばかり考えていた。実際は条件にあう個数をDPに保存して、繰り返し個数を足していくのがいいらしい。
解法は公式解説が最もわかりやすい。
https://atcoder.jp/contests/abc291/editorial/5838

Python
n = int(input())
card_number = [list(map(int, input().split())) for i in range(n)]

MOD = 998244353

dp = [[0, 0] for _ in range(n)]
dp[0] = [1, 1]  # トランプ一枚の場合、表でも裏でも条件を満たす

for i in range(1, n):  # トランプ一枚は初期値で代入済み
    for pre in range(2):  # pre = 0 は一つ前のカードが表, pre = 1 は一つ前のカードが裏
        for now in range(2):  # now = 0 は現在のカードが表, now = 1は現在のカードが裏
            if card_number[i - 1][pre] != card_number[i][now]:
                dp[i][now] += dp[i - 1][pre]
    dp[i][0] = dp[i][0] % MOD
    dp[i][1] = dp[i][1] % MOD

print((dp[n - 1][0] + dp[n - 1][1]) % MOD)
C++
#include<bits/stdc++.h>
using namespace std;

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

    int card_num[N][2];
    for (int i = 0; i < N; i++) {
        cin >> card_num[i][0];
        cin >> card_num[i][1];
    }

    int MOD = 998244353;
    
    int dp[N][2] = {};
    dp[0][0] = dp[0][1] = 1;

    for (int i = 1; i < N; i++){ // トランプ一枚は初期値で代入済み
        for (int pre = 0; pre < 2; pre++){ // pre = 0 は一つ前のカードが表, pre = 1 は一つ前のカードが裏
            for (int now = 0; now < 2; now++){ // # now = 0 は現在のカードが表, now = 1は現在のカードが裏
                if (card_num[i-1][pre] != card_num[i][now]) {
                    dp[i][now] = dp[i][now] + dp[i-1][pre];
                }
            }
        }
        dp[i][0] = dp[i][0] % MOD;
        dp[i][1] = dp[i][1] % MOD;

    }
    cout << (dp[N-1][0] + dp[N-1][1]) % MOD << endl;
}

Discussion