ikeh1024のブログ

ZennやQiitaに書くにはちょっと小粒なネタをこちらに書いています

【学習記録】AtCoder Programming Guide for beginners (APG4b)_02

AtCoder C++ 競プロ

AtCoder Programming Guide for beginners (APG4b)

M - 1.12.文字列と文字

-w437

-w687

-w695

EX12 - 足したり引いたり / 1.12

模範解答では、1文字ずつスライスして、1の場合は何も処理しないようにしていた。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    string S;
    cin >> S;
    
    int sum = 1;
    for (int s_i = 1; s_i < S.size(); s_i+=2) {
        if (S.at(s_i) == '+') {
            sum++;
        } else if (S.at(s_i) == '-') {
            sum--;
        } else {
            cout << "erorr" << endl;
            break;
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

A - 居合を終え、青い絵を覆う / UOIAUAI

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    char c;
    cin >> c;
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
    
    return 0;
}

模範解答。 findを使う方法もありとのこと。

https://marycore.jp/prog/cpp/std-string-find-search/#find%EF%BC%8Frfind

std::string s = "a-b-c";
auto pos = s.find("-"); // pos == 1 (先頭から検索)
pos = s.rfind("-");     // pos == 3 (末尾から検索)

s.find('b');              // 2 (文字型による検索)
s.find(std::string("c")); // 4 (std::string型による検索)
s.find("");               // 0
s.find("9");              // std::string::npos (見つからなかった場合)

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    char c;
    cin >> c;
    const string vowel = "aeiou";
    if (vowel.find(c) == string::npos) {
        cout << "consonant" << endl;
    } else {
        cout << "vowel" << endl;
    }
    
    return 0;
}

A - AtCoder *** Contest

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    string a, b, c;
    cin >> a >> b >> c;
    cout << "A" << b.at(0) << "C" << endl;
    
    return 0;
}

A - 添字

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    string s;
    int i;
    cin >> s >> i;
    cout << s.at(i-1) << endl;
    
    return 0;
}

A - お茶

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    string s;
    cin >> s;
    int lastCharIndex = int(s.size()) - 1;
    if (s[lastCharIndex] == 'T') {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

模範解答。方法1は上記の通り。下記の方法もあるそうで。

string s;
cin >> s;
if (*s.rbegin() == 'T') {
    cout << "YES" << endl;
} else {
    cout << "NO" << endl;
}

B - Minesweeper

回答できず。模範解答を見る。 ・周りのマス目へのオフセット値を定義しておき、forで検索する。 ・数値 + '0' = 数字

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfRows, numberOfColumns;
    cin >> numberOfRows >> numberOfColumns;
    
    vector<string> board(50);
    
    for (int row_i = 0; row_i < numberOfRows; row_i++) {
        cin >> board[row_i];
    }
    
    // 周りのマス目へのオフセット値
    const vector<int> offsetOfX = {1,0,-1,0,1,-1,-1,1};
    const vector<int> offsetOfY = {0,1,0,-1,1,1,-1,-1};
    
    for (int row_i = 0; row_i < numberOfRows; row_i++) {
        for (int column_i = 0; column_i < numberOfColumns; column_i++) {
            if (board.at(row_i).at(column_i) == '#') {
                continue;
            }
            
            int numberOfAdjacentBombs = 0;
            for (int around_i = 0; around_i < 8; around_i++) {
                const int aroundRow    = row_i + offsetOfY.at(around_i);
                const int aroundColumn = column_i + offsetOfX.at(around_i);
                
                // 対象のrowが先頭行または最終行のときは無視
                if (aroundRow < 0 || numberOfRows - 1 < aroundRow) {
                    continue;
                }
                // 対象のcolumnが左端または右端のときは無視
                if (aroundColumn < 0 || numberOfColumns - 1 < aroundColumn) {
                    continue;
                }
                
                if (board.at(aroundRow).at(aroundColumn) == '#') {
                    numberOfAdjacentBombs++;
                }
            }
            board.at(row_i).at(column_i) = char(numberOfAdjacentBombs + '0');   // 数値 + '0' = 数字
        }
    }
    
    for (int row_i = 0; row_i < numberOfRows; row_i++) {
        cout << board.at(row_i) << endl;
    }
    
    return 0;
}

N - 1.13.配列

-w694

-w730

-w1096

-w939

配列の使い所 配列とfor文を組み合わせると、大量のデータを扱うプログラムを書くことができます。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    
    int N;
    cin >> N;
    
    vector<int> math(N);
    vector<int> english(N);
    
    for (int i = 0; i < N; i++) {
        cin >> math.at(i);
    }
    
    for (int i = 0; i < N; i++) {
        cin >> english.at(i);
    }
    
    for (int i = 0; i < N; i++) {
        cout << math.at(i) + english.at(i) << endl;
    }
    
    return 0;
}

-w1035

-w1041

-w630

EX13 - 平均との差 / 1.13

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    
    int numberOfPerson;
    cin >> numberOfPerson;
    vector<int> scoresOfAi(1000);
    
    int sum = 0;
    for (int person_i = 0; person_i < numberOfPerson; person_i++) {
        cin >> scoresOfAi.at(person_i);
        sum += scoresOfAi.at(person_i);
    }
    
    int average = sum / numberOfPerson;
    
    // 結果出力
    for (int person_i = 0; person_i < numberOfPerson; person_i++) {
        cout << abs(scoresOfAi[person_i] - average) << endl;
    }
    
    return 0;
}

B - Picture Frame

自分の回答

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int height, width;
    cin >> height >> width;
    vector<string> lines(height);
    for (int line_i = 0; line_i < height; line_i++) {
        cin >> lines.at(line_i);
    }
    
    // 上辺
    for (int i = 0; i < width + 2; i++) {
        cout << "#";
    }
    cout << endl;
    
    // 中段
    for (int line_i = 0; line_i < height; line_i++) {
        cout << "#" << lines.at(line_i) << "#" << endl;
    }
    
    // 下辺
    for (int i = 0; i < width + 2; i++) {
        cout << "#";
    }
    cout << endl;
    
    return 0;
}

模範解答

B: Picture Frame最初に，縦H+ 2行，横W+ 2列の文字配列bを用意し，#で埋めておきます．次に，各1iH,1jWごとにai;jをbi+1;j+1へコピーします．最後に，配列bの内容を出力すればよいです．ちなみに，迷路などが入力として与えられたとき，この問題のようにあらかじめ外壁で囲んでおくと，その後の実装が簡単になることがあります

B - Counting Roads

自分のコード。 配列を用意して++していくあれ。解説どおり。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfCities, numberOfRoads;
    cin >> numberOfCities >> numberOfRoads;
    vector<int> numberOfRoadsInCityN(numberOfCities);
    for (int road_i = 0; road_i < numberOfRoads; road_i++) {
        int startCity, endCity;
        cin >> startCity >> endCity;
        numberOfRoadsInCityN.at(startCity-1)++;
        numberOfRoadsInCityN.at(endCity-1)++;
    }
    
    for (int city_i = 0; city_i < numberOfRoadsInCityN.size(); city_i++) {
        cout << numberOfRoadsInCityN.at(city_i) << endl;
    }
    
    return 0;
}

B - Trained?

諦めて答えを見ました。 イメージとしては連結リストになるんでしょうか。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfButtons;
    cin >> numberOfButtons;
    vector<int> buttons(numberOfButtons);
    
    for (int button_i = 0; button_i < numberOfButtons; button_i++) {
        int nextButtonIndex;
        cin >> nextButtonIndex;
        nextButtonIndex--;
        buttons.at(button_i) = nextButtonIndex;
    }
    
    int currentButtonIndex = 0;
    for (int count = 0;; count++) {
        if (currentButtonIndex == 1) {  // ボタン2が光っている場合
            cout << count << endl;
            break;
        }
        
        // ボタンの数以上にループをしている場合 = ボタン2が押せない場合
        if (count >= numberOfButtons) {
            cout << -1 << endl;
            break;
        }
        
        currentButtonIndex = buttons.at(currentButtonIndex);
    }
    
    return 0;
}

B - Two Colors Card Game

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    
    // input
    int numberOfBlueCard;
    cin >> numberOfBlueCard;
    vector<string> stringOfBlueCards(numberOfBlueCard);
    for (int blueCard_i = 0; blueCard_i < numberOfBlueCard; blueCard_i++) {
        cin >> stringOfBlueCards.at(blueCard_i);
    }
    
    int numberOfRedCard;
    cin >> numberOfRedCard;
    vector<string> stringOfRedCards(numberOfRedCard);
    for (int redCard_i = 0; redCard_i < numberOfRedCard; redCard_i++) {
        cin >> stringOfRedCards.at(redCard_i);
    }
    
    // process
    int maxValue = 0;
    for (int blueCard_i = 0; blueCard_i < numberOfBlueCard; blueCard_i++) {
        int currentValue = 0;
        // blueCardの探索
        for (int blueCard_j = 0; blueCard_j < numberOfBlueCard; blueCard_j++) {
            if (stringOfBlueCards.at(blueCard_i) == stringOfBlueCards.at(blueCard_j)) {
                currentValue++;
            }
        }
        // redCardの探索
        for (int redCard_j = 0; redCard_j < numberOfRedCard; redCard_j++) {
            if (stringOfBlueCards.at(blueCard_i) == stringOfRedCards.at(redCard_j)) {
                currentValue--;
            }
        }
        maxValue = max(maxValue, currentValue);
    }
    
    cout << maxValue << endl;
    
    return 0;
}

O - 1.14.STLの関数

-w691

C++で用意されている、関数等がまとまっているもののことをSTL (Standard Template Library)といいます。

-w690

-w684

-w694

-w686

EX14 - 三人兄弟の身長差 / 1.14

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    vector<int> heightOfPerson(3);
    cin >> heightOfPerson.at(0) >> heightOfPerson.at(1) >> heightOfPerson.at(2);
    sort(heightOfPerson.begin(), heightOfPerson.end());
    cout << heightOfPerson.at(2) - heightOfPerson.at(0) << endl;
    
    return 0;
}

模範解答。 max, minの二重構造。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int A, B, C;
    cin >> A >> B >> C;
    int maximum = max(max(A, B), C);
    int minimum = min(min(A, B), C);
    cout << maximum - minimum << endl;
    
    return 0;
}

B - Card Game for Two

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfCards;
    cin >> numberOfCards;
    vector<int> cardNumbers(numberOfCards);
    
    for (int card_i = 0; card_i < numberOfCards; card_i++) {
        cin >> cardNumbers.at(card_i);
    }
    
    sort(cardNumbers.begin(), cardNumbers.end());       // 昇順にソート
    reverse(cardNumbers.begin(), cardNumbers.end());    // 降順に変更
    
    int difference = 0;
    int sign = 1;
    for (int card_i = 0; card_i < numberOfCards; card_i++) {
        difference += sign * cardNumbers.at(card_i);
        sign *= -1;
    }
    
    cout << difference << endl;
    
    return 0;
}

回答例。

降順に並べるには、functionalヘッダにあるgreater<型>()を使う。

(i & 1 ? -1 : 1)これはビット演算の論理積？

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int N, a[109];
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a + N, greater<int>());
    int ret = 0;
    for (int i = 0; i < N; i++) ret += a[i] * (i & 1 ? -1 : 1);
    cout << ret << endl;
    return 0;
}

B - Kagami Mochi

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfMochi;
    cin >> numberOfMochi;
    vector<int> diametersOfMochi(numberOfMochi);
    
    for (int mochi_i = 0; mochi_i < numberOfMochi; mochi_i++) {
        cin >> diametersOfMochi.at(mochi_i);
    }
    
    sort(diametersOfMochi.begin(), diametersOfMochi.end(), greater<int>());
    
    int X = 1;
    for (int mochi_i = 1; mochi_i < numberOfMochi; mochi_i++) {
        if (diametersOfMochi.at(mochi_i - 1) == diametersOfMochi.at(mochi_i)) {
            continue;
        }
        X++;
    }
    
    cout << X << endl;
    
    return 0;
}

模範解答 直径をインデックスに用いる。 flagsの大きさに注意 またはsetを使う方法もある。

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    int N, flags[101];
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int diameter;
        cin >> diameter;
        flags[diameter] = 1;
    }
    
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        ans += flags[i];
    }
    
    cout << ans << endl;
    
    return 0;
}

P - 1.15.関数

-w683

-w683

-w679

-w679

-w683

EX15 - 三人兄弟へのプレゼント / 1.15

//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

// 1人のテストの点数を表す配列から合計点を計算して返す関数
// 引数 scores: scores.at(i)にi番目のテストの点数が入っている
// 返り値: 1人のテストの合計点
int sum(vector<int> scores) {
    // ここにプログラムを追記
    int sumOfScore = 0;
    for (int score_i = 0; score_i < scores.size(); score_i++) {
        sumOfScore += scores.at(score_i);
    }
    return sumOfScore;
}

// 3人の合計点からプレゼントの予算を計算して出力する関数
// 引数 sum_a: A君のテストの合計点
// 引数 sum_b: B君のテストの合計点
// 引数 sum_c: C君のテストの合計点
// 返り値: なし
void output(int sum_a, int sum_b, int sum_c) {
    // ここにプログラムを追記
    cout << sum_a * sum_b * sum_c << endl;
}

// -------------------
// ここから先は変更しない
// -------------------

// N個の入力を受け取って配列に入れて返す関数
// 引数 N: 入力を受け取る個数
// 返り値: 受け取ったN個の入力の配列
vector<int> input(int N) {
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec.at(i);
    }
    return vec;
}

int main(int argc, const char * argv[]) {
    
    // input from txt （提出時にこの箇所は削除すること）
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    
    /////////////////////
    // Write code below /
    /////////////////////
    // 科目の数Nを受け取る
    int N;
    cin >> N;
    
    // それぞれのテストの点数を受け取る
    vector<int> A, B, C;
    A = input(N);
    B = input(N);
    C = input(N);
    
    // プレゼントの予算を出力
    output(sum(A), sum(B), sum(C));
    
    return 0;
}