自分用にAtcoderで間違えた問題を備忘録としてまとめます。
完全に自分用ですが、公開します笑
目次
格言のみ
- 本当に一部だけテストケースが通らない場合は、桁あふれの可能性。long longにすれば解決するかも
- 図を書いてみて問題文を言い換えよ！
- 制約が小さい問題は難しいこと考えずに全探索！
2023-04-09 D問題 難易度273
解答
格言：とりあえずテストケースを手計算で計算しパターンに気づけ！
//模範解答
#include<iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
long long ans = 0;
if (a < b) swap(a, b);
while (b > 0) {
ans += a / b;
a %= b;
swap(a, b);
}
cout << ans - 1 << endl;
}
2023-04-15 C問題 難易度
解答
格言：SET,MultiSetは便利だから積極的に使え！
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
map<int, set<int> > card_to_boxes;// セットは重複許さない,並べ替えもやってくれる
for (int k = 0; k < q; ++k) {
int query_type;
cin >> query_type;
if (query_type == 1) {
int i, j;
cin >> i >> j;
boxes[j].insert(i);
card_to_boxes[i].insert(j);
} else if (query_type == 2) {
int i;
cin >> i;
for (int card : boxes[i]) {
cout << card << " ";
}
cout << endl;
//boxes[i].clear();
} else {
int i;
cin >> i;
for (int box : card_to_boxes[i]) {
cout << box << " ";
}
cout << endl;
//card_to_boxes[i].clear();
}
}
return 0;
}
2023-04-15 D問題 難易度
なんか間違えてたけどいい感じの奴
解答
格言：でキューの使い方と％は何回でもできるの巻
#include <iostream>
#include <string>
#include <deque>
using namespace std;
long long MOD = 998244353;
//割るはいつでもできるの法則を使う
int main() {
int Q;
cin >> Q;
deque<int> S = {1};
long long num = 1;
long long base = 1;
for (int i = 1; i <= Q; i++) {
int query_type;
cin >> query_type;
if (query_type == 1) {
int x;
cin >> x;
S.push_back(x);
num = (num * 10 + x) % MOD;
base = base *10 % MOD;//10の何乗
} else if (query_type == 2) {
int removed_digit = S.front();
S.pop_front();
// Sの全ての順列を試す。next_permutationは次の順列を生成する
// すべての順列を試して、各連続する文字列が1文字だけ異なるものが見つかれば"Yes"を出力して終了
do {
if (check(S)) {
cout << "Yes" << endl;
return 0;
}
} while (next_permutation(S.begin(), S.end()));
// すべての順列を試したが条件を満たすものがなければ"No"を出力
cout << "No" << endl;
return 0;
}
＜next_permutationとは？＞std::next_permutationはC++のSTL（Standard Template Library）に含まれる関数で、与えられた範囲の要素を次の順列に並べ替えます。具体的には、辞書順で次に来るべき順列を生成します。順列は、要素の特定の並べ方を指します。たとえば、{1,2,3}の3つの数の全ての順列は{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}となります。std::next_permutationを使うと、これらを順に生成することができます。
2023年6月3日
atcoder.jp
深さ優先探索の基本的な問題
//深さ優先探索を使う問題
#include <iostream>
#include <cmath>
#include <cstring>
#define MAX_N 2005
int N, D;
int X[MAX_N], Y[MAX_N];
bool visited[MAX_N];
double dist(int x1, int y1, int x2, int y2) {
int dx = x1 - x2;
int dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
void dfs(int v) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u])
dfs(u);
}
}
int main() {
std::cin >> N >> D;
for (int i = 0; i < N; i++) {
std::cin >> X[i] >> Y[i];
}
// もしDより小さければ配列に突っ込む
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j && dist(X[i], Y[i], X[j], Y[j]) <= D) {
adj[i].push_back(j);
}
}
}
//探索開始
dfs(0);
for (int i = 0; i < N; i++) {
if (visited[i])
std::cout << "Yes\n";
else
std::cout << "No\n";
}
return 0;
}
*1:num - removed_digit*base) < 0) num +=MOD;
num = (num - removed_digit*base) % MOD; //マイナスになるときはMODを足す
base = base/10;
} else if (query_type == 3) {
cout << num % MOD << endl;
}
}
return 0;
}
