『銀髪赤眼の後輩と学ぶ競技プログラミング』サポートページ

https://team-seadrive.booth.pm/items/1324517 https://scrapbox.io/files/62406f340ed64f001ded2ae7.jpg

table:正誤表

版 ページ 誤 正

第1版 p.28 引数 str - pos - 検索を… (削除)

第1版 p.39 log(min A_i) 回 log(max A_i)回

第1版 p.41 型 T は比較演算子 > が定義… 型 T は比較演算子 < が定義…

第1版 p.44 for(int i=0; i=N; i++){ for(int i=0; i<N; i++){

第1版 p.50 (101011 >> 2) → 101100 (101011 << 2) → 101100

第1版 p.53 コード内 sum += stoll(… の下行 ans += sum; を追加

第1版 p.61 DFS の実装コード 最終行 } を追加

第1版 p.62 st.push(data); / st.front(); / st.pop() st を que に変更

第1版 p.66 dijkstra法のコード 下記 4.6.cpp 参照

<= 第2版 p.57 void dfs(int now) void dfs(string now)

<= 第2版 p.57 4.3の図

https://scrapbox.io/files/62406f70d0e6a0001d5a22da.png

コード

code:1.2.cpp

using namespace std;

int main() {

cout << "こんにちは" << endl;

cout << "AtCoder" << endl;

}

code:1.3.cpp

using namespace std;

int main(){

int a, b;

cin >> a >> b;

if((a*b)%2 == 0){

cout << "Even" << endl;

}else{

cout << "Odd" << endl;

}

}

code:1.5.cpp

int main(){

int N;

cin >> N;

vector<int> a(N);

for(int i=0; i<N; i++){

}

int sum = 0;

for(int i=0; i<N; i++){

}

cout << sum << endl;

}

code:2.2.cpp

int main(){

string A, B, C;

cin >> A >> B >> C;

cout << "YES" << endl;

}

else cout << "NO" << endl;

}

code:2.3.cpp

int main(){

string S;

cin >> S;

cout << "YES" << endl;

}

else cout << "NO" << endl;

}

code:2.6.cpp

int main(){

string N;

cin >> N;

int S = 0;

for(int i=0; i< N.size(); i++){

}

if(stoi(N) % S == 0) cout << "Yes" << endl;

else cout << "No" << endl;

}

code:3.3.cpp

int main(){

int ans = 0;

bool div_by_2 = true;

while(div_by_2){

for(int i=0; i<N; i++){

div_by_2 = false;

break;

}else{

}

}

// すべて2で割り切れる

if(div_by_2){

ans++;

}

}

cout << ans << endl;

}

code:3.4.cpp

int main(){

int A, B, C, X;

cin >> A >> B >> C >> X;

int ans = 0;

for(int a = 0; a <= A; ++a) {

for(int b = 0; b <= B; ++b) {

for(int c = 0; c <= C; ++c) {

// 合計

int total = 500*a + 100*b + 50*c;

if(total == X) ans++;

}

}

}

cout << res << endl;

}

code:3.6.cpp

int main() {

int N, K;

cin >> N >> K;

vector<int> l(N);

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

reverse(l.begin(), l.end());

int ans = 0;

cout << ans << endl;

}

code:3.7.cpp

const int INF = 999999999;

int main() {

int N;

cin >> N;

string S;

cin >> S;

vector<int> vW(N+1, 0), vE(N+1, 0);

for(int i=0; i<N; i++){

}

int ans = INF;

for(int i=0; i<N; i++){

if(ans > now) ans = now;

}

cout << ans << endl;

}

code:3.8.cpp

int main() {

int N;

cin >> N;

vector<int> A(N);

vector<long long> v(N+1, 0);

for(int k=1; k<=N; k++){

long long max_total = 0;

for(int i=0; i+k<=N; i++){

max_total = max(max_total, now);

}

cout << max_total << endl;

}

}

code:4.1.cpp

int main() {

int N;

cin >> N;

for(int s=0; s < (1<<N); s++){

vector<int> ans;

for(int i=0; i<N; i++){

// 要素 i を使うかどうか

if(s & (1<<i)) ans.push_back(i);

}

cout << "{";

for(int i=0; i<ans.size(); i++){

// 途中なら","を出力

if(i < ans.size()-1) cout << ",";

}

cout << "}" << endl;

}

}

-----

int main() {

string S;

cin >> S;

long long ans = 0;

for(int s=0; s < (1 << (S.size()-1)); s++){

string now = "";

for(int i=0; i<S.size()-1; i++){

if(s & (1<<i)) now += "+";

}

long long sum=0;

int pos=0; // 数値の始まる位置

while(now.find("+", pos) != string::npos){

// + の位置

int nextpos = now.find("+", pos);

sum += stoll( now.substr(pos, nextpos - pos) );

pos = nextpos+1;

}

sum += stoll( now.substr(pos) );

}

cout << ans << endl;

}

code:4.3.cpp

stack<string> st;

st.push("");

// stが空でない限り

while(!st.empty()){

string now = st.top();

st.pop();

if(now.size() == 3){

cout << now << endl;

}else{

for(int select=1; select>=0; select--){

string next = now + to_string(select);

st.push(next);

}

}

}

-----

void dfs(string now){

if(now.size() == 3){

cout << now << endl;

}else{

for(int select=1; select>=0; select--){

string next = now + to_string(select);

dfs(next);

}

}

}

補足

スタックによる実装と、再帰関数による実装では出力の順番が逆になります。 この違いについて考えてみます。

スタックは"積む"操作であり、for ループが終わるまで順に 1, 0 と積みます。 その後 while ループで取り出されるのは、最後に積んだ 0 になります。0 に続く数字も同様に処理されるので、最終的には 000, 001, 010, … の順番で取り出されます。

一方、再帰関数は"割り込む"操作です。最初に 1 を積みますが、その後 0 を積むのではなく先に 1 に続く数字を処理するのです。結果、11 のあとに続けるのは 1 で、111 ができたから出力、… といった具合に出力が逆転するのです。

code:4.4.cpp

int N, M;

vector<int> visited;

vector<vector<int>> G;

int num_visited = 0;

int ans = 0;

void dfs(int now){

num_visited++;

// すべての頂点を訪れたなら

if(num_visited == N){

ans++;

}

}

num_visited--;

}

int main() {

cin >> N >> M;

G = vector<vector<int>>(N); // サイズを確保する

visited = vector<int>(N, 0);

for(int i=0; i<M; i++){

int a, b;

cin >> a >> b;

// 頂点番号を 0-indexed とする

a--;

b--;

}

// 頂点番号 0 からDFSを始める

dfs(0);

cout << ans << endl;

}

code:4.5.cpp

int W, H;

vector<vector<char>> s;

vector<vector<int>> cost;

int bfs(){

// 移動可能なマスをループで簡単に列挙

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// 座標をpair(y, x)でもってqueueに入れる

queue<pair<int, int>> que;

// スタートは(0, 0) (0-indexedに読み替える)

que.push(make_pair(0, 0));

while(!que.empty()) {

pair<int, int> p = que.front();

que.pop();

if(p == make_pair(H-1, W-1)){

// ゴールに到達

}

for(int i = 0; i < 4; i++) {

// 壁orマスの外

if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;

// 既に探索済み

que.push(make_pair(ny, nx));

}

}

return -1;

}

int main() {

cin >> H >> W;

s = vector<vector<char>>(H, vector<char>(W));

int white = 0;

for(int i=0; i<H; i++){

for(int j=0; j<W; j++){

}

}

cost = vector<vector<int>>(H, vector<int>(W, -1));

int min_cost = bfs();

if(min_cost == -1) cout << -1 << endl;

else cout << white - (min_cost+1) << endl;

}

code:4.6.cpp

// 隣接リストでは相手の頂点番号だけ持っておけばよかったので、

// vector<vector<int>> で大丈夫だった、今回は辺の重みも

// 保持する必要があるので、データ構造 edge を用意する

// pair でもできるが、わかりやすいのはこっち？

struct edge{

int to, cost;

};

const int INF = 999999999;

// startからの最短経路をすべての頂点に対して求める

vector<int> dijkstra(vector<vector<edge>> &G, int start){

vector<int> dist(G.size(), INF);

using pi = pair<int, int>;

// 自動的にソートしておいてくれるqueueであるpriority_queueを使う

// costが小さい順に並ぶようにする

// pair(その時点での最短経路, 頂点番号)

priority_queue<pi, vector<pi>, greater<pi>> que;

while(!que.empty()){

int cost = que.top().first;

int idx = que.top().second;

que.pop();

}

}

return dist;

}

// 頂点 s -> t へ 重み d で結ぶ辺の追加方法

// 頂点 start からの最短経路長を保持したvectorを O(NlogN) で構築する!

vector<int> ans = dijkstra(G, start);