- 【学習記録】AtCoder Programming Guide for beginners (APG4b)
- Q - 2.00.第2章について
- AtCoder Beginners Selection
- R - 2.01.ループの書き方
- S - 2.02.多重ループ
- T - 2.03.多次元配列
- U - 2.04.参照
【学習記録】AtCoder Programming Guide for beginners (APG4b)
Q - 2.00.第2章について
AtCoder Beginners Selection
TODO
R - 2.01.ループの書き方
C++には配列の要素に対する処理を簡潔に書くことが出来る範囲for文という構文が用意さています。
範囲for文を用いると上のプログラムは次のように書き直せます。
#include <bits/stdc++.h> using namespace std; int main() { vector<int> a = {1, 3, 2, 5}; for (int x : a) { cout << x << endl; } }
範囲for文はコンテナと呼ばれるデータ型に対して使うことが出来ます。 配列はコンテナの一種です。 その他にも文字列型(string)はコンテナの一種なので、範囲for文を用いることが出来ます。 string型の変数に対して、1文字ずつ処理したい場合に便利です。
#include <bits/stdc++.h> using namespace std; int main() { string str = "hello"; for (char c : str) { if (c == 'l') { c = 'L'; } cout << c; } cout << endl; }
while文が適しているケース 「整数Nがあるとき、Nが2で最大で何回割り切れるかを求める」という処理を考えます。 この処理は配列の要素に対する処理ではありませんし、具体的に何回処理を繰り返せば良いのかということも分かりません。 この処理にはwhile文が適しているでしょう。
次のサンプルプログラムは、入力で与えられた整数Nが2で割り切れる回数を出力するプログラムです。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int count = 0; while (N > 0) { // 2で割り切れなければループを抜ける if (N % 2 > 0) { break; } N = N / 2; count++; } cout << count << endl; }
EX16 - 隣り合う同じ値を探す / 2.01
// 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> data(5); for (int i = 0; i < 5; i++) { cin >> data.at(i); } bool hasNeighbor = false; for (int loopCount = 0; loopCount < data.size() - 1; loopCount++) { if (data.at(loopCount) == data.at(loopCount + 1)) { hasNeighbor = true; break; } } if (hasNeighbor == true) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
S - 2.02.多重ループ
多重ループのbreak/continue
多重ループを抜けるときは、ループを抜けるかどうかを持つ変数(フラグ変数)を用意して、フラグ変数の値に応じてループを抜けるように書きます。
処理の大まかな流れは次の通りです。
bool finished = false; // 外側のループを抜ける条件を満たしているかどうか(フラグ変数) for (int i = 0; i < ... ; i++) { for (int j = 0; j < ... ; j++) { /* 処理 */ if (/* 2重ループを抜ける条件 */) { finished = true; break; // (＊) // finishをtrueにしてからbreakすることで、 // 内側のループを抜けたすぐ後に外側のループも抜けることが出来る } } // (＊)のbreakでここに来る if (finished) { break; // (＊＊) } } // (＊＊)のbreakでここに来る
他の方法 多重ループの部分を関数化し、関数の内部で使えるreturnを使って一気に抜けるという方法もあります。
この方法ではループ内の処理を行なうために必要な変数を引数で渡す必要があり、 余計な処理が必要になることがあるので、基本的にはフラグ変数を用意する方針で処理するようにしましょう。
void func( /* 処理に必要な変数 */ ) { for (int i = 0; i < ... ; i++) { for (int j = 0; j < ... ; j++) { /* 処理 */ if (/* 2重ループを抜ける条件 */) { return; // 関数のreturnはループに関係なく抜けることが出来る } } } } int main() { func(); }
EX17 - 果物屋さんでお買い物 / 2.02
// 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, targetPrice; cin >> N >> targetPrice; vector<int> apple(N), pineapple(N); for (int apple_i = 0; apple_i < N; apple_i++) { cin >> apple.at(apple_i); } for (int pineapple_i = 0; pineapple_i < N; pineapple_i++) { cin >> pineapple.at(pineapple_i); } int numberOfBuyingWay = 0; for (int apple_i = 0; apple_i < N; apple_i++) { for (int pineapple_i = 0; pineapple_i < N; pineapple_i++) { int price = apple.at(apple_i) + pineapple.at(pineapple_i); if (price == targetPrice) { numberOfBuyingWay++; } } } cout << numberOfBuyingWay << endl; return 0; }
int price = apple.at(apple_i) + pineapple.at(pineapple_i); if (price == targetPrice) { numberOfBuyingWay++; }
は下記のようにかける。無駄な変数は使わないでいい。
if (apple.at(apple_i) + pineapple.at(pineapple_i) == targetPrice) {
numberOfBuyingWay++;
}
T - 2.03.多次元配列
#include <bits/stdc++.h> using namespace std; int main() { // int型の2次元配列(3×4要素の)の宣言 vector<vector<int>> data(3, vector<int>(4)); // 入力 (2重ループを用いる) for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { cin >> data.at(i).at(j); } } // 0の個数を数える int count = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { // 上からi番目、左からj番目の画素が0かを判定 if (data.at(i).at(j) == 0) { count++; } } } cout << count << endl; }
// 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 numberOfPeople, numberOfMatches; cin >> numberOfPeople >> numberOfMatches; // 参加者の勝敗記録 vector<vector<char>> matchResults(numberOfPeople, vector<char>(numberOfPeople, '-')); for (int match_i = 0; match_i < numberOfMatches; match_i++) { int winner, loser; cin >> winner >> loser; winner--; loser--; matchResults.at(winner).at(loser) = 'o'; matchResults.at(loser).at(winner) = 'x'; } for (int people_i = 0; people_i < numberOfPeople; people_i++) { for (int people_j = 0; people_j < numberOfPeople; people_j++) { cout << matchResults.at(people_i).at(people_j); if (people_j + 1 != numberOfPeople) { // rowの最後であればスペースを含めない cout << " "; } } cout << endl; } return 0; }
B - Grid Compression
2次元配列を用意してrowとcolumnでそれぞれ判定をしようとしたが、場合分けが複雑になってしまいプログラムできず。 解答を見る。
// 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> a(height); for (int i = 0; i < height; i++) { cin >> a.at(i); } // 黒色のマスがあるrowとcolumnを記録する vector<bool> rows(height, false); vector<bool> columns(width, false); for (int row_i = 0; row_i < height; row_i++) { for (int column_i = 0; column_i < width; column_i++) { if (a.at(row_i).at(column_i) == '#') { rows.at(row_i) = true; columns.at(column_i) = true; } } } for (int row_i = 0; row_i < height; row_i++) { if (rows.at(row_i)) { for (int column_i = 0; column_i < width; column_i++) { if (columns.at(column_i)) { cout << a.at(row_i).at(column_i); } } cout << endl; } } return 0; }
U - 2.04.参照
参照先を変更することは出来ない 一度宣言した参照の参照先を後から変更することも出来ません。
EX19 - 九九の採点 / 2.04
// main.cpp // CppTest #include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; // 参照渡しを用いて、呼び出し側の変数の値を変更する void saiten(vector<vector<int>> &A, int &correct_count, int &wrong_count) { // 呼び出し側のAの各マスを正しい値に修正する // Aのうち、正しい値の書かれたマスの個数を correct_count に入れる // Aのうち、誤った値の書かれたマスの個数を wrong_count に入れる // ここにプログラムを追記 for (int row_i = 0; row_i < A.size(); row_i++) { for (int column_i = 0; column_i < A.at(0).size(); column_i++) { if (A.at(row_i).at(column_i) == (row_i + 1) * (column_i + 1)) { correct_count++; } else { A.at(row_i).at(column_i) = (row_i + 1) * (column_i + 1); wrong_count++; } } } return; } int main(int argc, const char * argv[]) { // input from txt （提出時にこの箇所は削除すること） std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); ///////////////////// // Write code below / ///////////////////// // A君の回答を受け取る vector<vector<int>> A(9, vector<int>(9)); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cin >> A.at(i).at(j); } } int correct_count = 0; // ここに正しい値のマスの個数を入れる int wrong_count = 0; // ここに誤った値のマスの個数を入れる // A, correct_count, wrong_countを参照渡し saiten(A, correct_count, wrong_count); // 正しく修正した表を出力 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cout << A.at(i).at(j); if (j < 8) cout << " "; else cout << endl; } } // 正しいマスの個数を出力 cout << correct_count << endl; // 誤っているマスの個数を出力 cout << wrong_count << endl; return 0; }
