B - Two Colors Card Game
コメント歓迎です。
今回はmapを使って解きました。
方針
今回の問題で初めてmapを使いました。
mapは2つの情報を関連付けて記録できます。
今回はカードに書かれた文字列とその登場回数を関連付けて記録しました。
同じ文字列が出てくるたびに関連付けている登場回数を+1します。
コード(AC)
#include <iostream> #include <unordered_map> #include <string> using namespace std; int main() { // 入力 int N; cin >> N; string tmp; unordered_map<string, int> s; for (int i = 0; i < N; i++) { cin >> tmp; // 入力をmap sに登録 // 登録されるたびmap値を+1 // 同じ文字列が登録された場合はmap値が増加 s[tmp]++; } // 上と同様の処理 int M; cin >> M; unordered_map<string, int> t; for (int i = 0; i < M; i++) { cin >> tmp; t[tmp]++; } // sに登録されている文字列をfor文で繰り返し処理 int ans = 0; for (auto& d : s) { // 青カードと赤カードに登録された回数から貰える金額を計算 ans = max(ans, d.second - t[d.first]); } // 出力 cout << ans << endl; return 0; }
B - Kagami Mochi
コメント歓迎です。
今回はsetを使って解きました。
方針
今回の問題で初めてsetを使いました。
setに追加した要素は自動でソートされ追加されます。
要素に重複があった場合は、追加されません。
この問題では入力をsetに追加していき、setに格納された要素数を数えることで解答できます。
コード(AC)
#include <iostream> #include <set> using namespace std; int main() { int N; int d[100]; // 入力を配列に追加 cin >> N; for (int i = 0; i < N; i++) { cin >> d[i]; } // setに配列の要素を追加 set<int> ans; for (int i = 0; i < N; i++) { ans.insert(d[i]); } // 出力 cout << ans.size() << endl; return 0; }
C - 器物損壊！高橋君
コメント歓迎です。
今回も幅優先探索の応用問題です。
0-1-BFSと呼ばれている手法のようです。
タイトルの勢いが結構好きです。
方針
今回の問題で初めてdequeというものを使いました。
dequeは普通のqueueとは違い、先頭にも最後尾にもpushできます。
今回の使い方としては優先度の高いものは先頭にpushし、
優先度が低いものは最後尾にpushします。
そうすることによって優先度が高いものからpopされ、処理が進むことになります。
迷路は通路('.', 's', 'g')か壁('#')の二種類しかなく、通路を優先して処理しています。
変数scoreの値は壁を一度壊さないと進めないマスは"1"、二度なら"2"、三度なら"3"といった具合になります。
下に例を示します。
迷路
| s | . | . | . | . | . | . | . | . | . |
| # | # | # | # | # | # | # | # | # | . |
| # | . | . | . | . | . | . | . | # | . |
| # | . | . | # | # | # | # | . | # | . |
| # | # | . | . | . | . | # | . | # | . |
| # | # | # | # | # | . | # | . | # | . |
| g | # | # | . | # | . | # | . | # | . |
| # | # | # | . | # | . | # | . | # | . |
| # | # | # | . | # | . | # | . | # | . |
| # | . | . | . | . | . | # | . | . | . |
処理後のscore
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 3 | 2 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 3 | 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
ゴールマスのscoreが2以下であれば壁を壊す回数が2回以下でたどり着けることになります。
コード(AC)
#include <iostream> #include <queue> #include <vector> using namespace std; // 宣言 char maze[500][500]; // 迷路データ int H; // 高さ int W; // 幅 int sh, sw; // スタート地点 int gh, gw; // ゴール地点 vector< vector<int> > score(500, vector<int> (500, 100)); // 手数 bool visited[500][500]; // 訪問履歴 const int dh[] = {1, -1, 0, 0}; const int dw[] = {0, 0, 1, -1}; // 幅優先探索 void bfs(int i, int j) { // キューを準備 deque<pair<int,int> > Q; // スタート地点のスコアを0にセット score[i][j] = 0; // スタート地点の座標をキューにプッシュ Q.push_back(make_pair(i, j)); // キューが空になるまで処理を実行 while(!Q.empty()) { // 探索の起点となる座標を記憶してからポップ pair<int,int> q = Q.front(); Q.pop_front(); int h = q.first; int w = q.second; // 起点を元に座標を移動 for (int k = 0; k < 4; k++) { int nh = h + dh[k]; int nw = w + dw[k]; // 移動先が迷路の範囲外なら処理をスキップ if (nh < 0 || nh >= H || nw < 0 || nw >= W) { continue; } // 移動先が壁ならdequeの最後尾にプッシュ if (score[nh][nw] > (score[h][w] + 1) && maze[nh][nw] == '#') { Q.push_back(make_pair(nh, nw)); // 移動先のスコアを起点のスコア+1にする score[nh][nw] = score[h][w] + 1; } // そうでなければdequeの先頭にプッシュ if (score [nh][nw] > score[h][w] && maze[nh][nw] != '#'){ Q.push_front(make_pair(nh, nw)); // 移動先のスコアを起点のスコアと同じにする score[nh][nw] = score[h][w]; } } } } int main() { // 入力 cin >> H >> W; // 迷路データ for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> maze[i][j]; // スタート地点を記録 if (maze[i][j] == 's') { sh = i; sw = j; } // ゴール地点を記録 if (maze[i][j] == 'g') { gh = i; gw = j; } } } // 幅優先探索 bfs(sh, sw); // 出力 cout << (score[gh][gw] <= 2 ? "YES" : "NO") << endl; return 0; }
D - Grid Repainting
コメント歓迎です。
以前に解いた幅優先探索の応用問題です。
以前の記事：C - 幅優先探索 - 思考する三角形▽
方針
この問題のポイントは2つあります。
①塗りつぶすマスをうまく計算する
②幅優先探索でゴールまでの最短手数を見つける
まず、黒く塗りつぶせるマスの最大数をどうやって計算するか考える必要があります。
すべてのマスの数は入力条件からで計算できます。
また、最初から黒いマス('#')の数も入力からわかります。
つまり、新たに黒く塗りつぶせるマスは「すべてのマス」ー「最初から黒いマス」ー「通り道の白いマス」となります。
黒く塗りつぶせるマスの数が最大となるのは、白のマスが最小の場合です。
ここで②の幅優先探索の話になります。
白のマスを最少にするためはスタートからゴールまで最短手数のルートを見つける必要があります。
最少ルートを探す方法が幅優先探索ということになります。
コード(AC)
#include <iostream> #include <queue> #include <vector> using namespace std; // 宣言 string maze[50]; // 迷路データ int H; // 高さ int W; // 幅 int scount = 0; // '#'の数 int ans = 0; vector< vector<int> > score(50, vector<int> (50, 0)); // 手数 bool visited[50][50]; // 訪問履歴 const int dh[] = {1, -1, 0, 0}; const int dw[] = {0, 0, 1, -1}; // 幅優先探索 void bfs(int i, int j) { // キューを準備 queue<pair<int,int> > Q; // スタート地点のスコアを0にセット score[i][j] = 0; // スタート地点の座標をキューにプッシュ Q.push(make_pair(i, j)); // キューが空になるまで処理を実行 while(!Q.empty()) { // 探索の起点となる座標を記憶してからポップ pair<int,int> q = Q.front(); Q.pop(); int h = q.first; int w = q.second; // 起点を元に座標を移動 for (int k = 0; k < 4; k++) { int nh = h + dh[k]; int nw = w + dw[k]; // 移動先が迷路の範囲外なら処理をスキップ if (nh < 0 || nh >= H || nw < 0 || nw >= W) { continue; } // 移動先が壁か訪問済みなら処理をスキップ if (maze[nh][nw] == '#' || visited[nh][nw]) { continue; } // 移動先のスコアを起点のスコア+1にする score[nh][nw] = score[h][w] + 1; // 移動先の座標を訪問済みにする visited[nh][nw] = true; // 訪問先の座標をキューにプッシュ(順番が来たら探索の起点になる) Q.push(make_pair(nh, nw)); } } } int main() { // 入力 cin >> H >> W; // 迷路データ for (int i = 0; i < H; i++ ) { cin >> maze[i]; } // 幅優先探索 bfs(0, 0); // '#'の数をカウント for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (maze[i][j] == '#') { scount++; } } } // ゴールにたどり着けなかった場合 if (score[H - 1][W - 1] == 0) { ans = -1; } // ゴールにたどり着けた場合 else { ans = H * W - scount -(score[H - 1][W - 1] + 1); } // 出力 cout << ans << endl; return 0; }
AtCoder Beginner Contest 114 [C - 755]
コメント歓迎です。
コンテストに参加したので1問ずつ記事を分けて解答を載せていきます。
今回はC問題です。
コンテスト時間内に解くことができませんでした。
コードは意外に短く、プログラミングの面白さを再認識しました。
方針
この問題のポイントは2つあります。
1つ目は、どうやって3, 5, 7の数字のみで構成された複数桁の数値を作るかです。
2つ目は、どうやって作った複数桁の数値に3, 5, 7がひとつ以上含まれていることを判定するかです。
まず、3, 5, 7の数字のみで構成された複数桁の数値を作る方法について考えます。
もし3種類の数字でなく2種類の数字であればビット全探索で列挙できますが、
今回は3種類のため別の方法が必要となります。
結論としては回帰関数(深さ優先探索)を使います。
考え方のイメージとしては「3」と「5」と「7」のマスがあり、マスの進み方を全探索していきます。
今記録している数値をとすると、1マス進むたびに
の処理をしていきます。
そうすると記録している数値は3575735553といった具合に3と5と7のみで構成された複数桁の数値を作ることができます。
問題の制約から、の値が入力Nの数値を超えた場合はそのdfsは終わるようにします。
dfsは再帰関数なので、1つdfsが終わってもそのdfsを呼び出したdfsの処理に戻ることに注意です。
次に作った数値に3, 5, 7がひとつ以上含まれているか判定することを考えます。
方法としてはdfsで「3」に進んだときはflag3をtrueにし、flag5, flag7は移動前の状態を引き継ぎます。
「5」や「7」についても同様にします。
そうすると、一度でも3に進めばflag3はtrueとなります。
flag5, flag7についてもどうようですので、flag3, flag5, flag7がすべてtrueであれば、
「3」, 「5」, 「7」がひとつ以上含まれていることが確認できます。
「3」, 「5」, 「7」がひとつ以上含まれている場合は条件を満たしますので、ansに+1してカウントします。
コード(AC)
#include <iostream> using namespace std; typedef long long ll; int N; int ans = 0; // 3, 5, 7を組み合わせて作れる数値を全探索 void dfs(ll x, bool flag3, bool flag5, bool flag7) { if (x > N) return; // 3, 5, 7をすべて含むならansに+1 if (flag3 && flag5 && flag7) ans++; dfs(10 * x + 3, true, flag5, flag7); dfs(10 * x + 5, flag3, true, flag7); dfs(10 * x + 7, flag3, flag5, true); } int main() { // 入力 cin >> N; // 深さ優先探索 dfs(0, 0, 0, 0); // 出力 cout << ans << endl; }
AtCoder Beginner Contest 114 [B - 754]
コメント歓迎です。
コンテストに参加したので1問ずつ記事を分けて解答を載せていきます。
今回はB問題です。
方針
この問題では、入力された数字列をどうやって3桁の数値に変換するかがポイントとなります。
まず、今回は入力の数字列を文字列として受け取りました。
string型で受け取ると先頭の数字を[0]とする配列として扱えるので便利です。
3桁の数字に変換するにあたって始点となる配列番号をfor文でループさせます。
そのたびにひと桁ずつ始点とその右隣、さらにその右隣の数字を3桁の数値に変換します。
具体的には桁上げをする必要がありますので、を繰り返す処理をします。
最後に753との差の絶対値をとり、最小となる数値を出力します。
コード(AC)
#include <iostream> #include <cmath> using namespace std; int main() { // 入力 string S; cin >> S; int digit = S.size(); // 入力の桁数 int ans = 1000; // 数字列を左から順に3桁の数値へ変換 for (int i = 0; i < digit - 2; i++) { int X = 0; X = S[i] - '0'; for (int j = 1; j < 3; j++) { X = X * 10 + S[i + j] - '0'; } ans = min(abs(753 - X), ans); } // 出力 cout << ans << endl; }
AtCoder Beginner Contest 114 [A - 753]
コメント歓迎です。
コンテストに参加したので1問ずつ記事を分けて解答を載せていきます。
A問題はシンプルです。
方針
この問題では、if文を使って出力する文字列に条件を与えます。
入力が数字の3, 5, 7の場合は出力は"YES"、そうでなければ"NO"を出力します。
言い換えるとXが3もしくは5もしくは7のとき、"YES"を出力すればよいことになります。
コード(AC)
#include <iostream> using namespace std; int main() { // 入力 int X; cin >> X; // Xが3, 5, 7のどれかなら"YES" if (X == 3 || X == 5 || X == 7) { cout << "YES" <<endl; } // そうでなければ""NO" else { cout << "NO" << endl; } }
