A - Hamming Distance
O(N)
forループの問題です。
異なる時にカウントをする。
S_i ≠ T_i
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
string S, T;
cin >> S >> T;
int ans = 0;
rep(i, N){
if(S[i] != T[i]) ans++;
}
cout << ans << endl;
return 0;
}
B - Ranking with Ties
O(N^2)
大きい要素の順に、順位をつけていきます。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| P_i | 3 | 12 | 9 | 9 |
| ans | 4 | 1 | 2 | 2 |
- 順位の決まっていない要素で最も大きい数字
xを探索 -
xの要素に現在の順位をつける - 全ての要素に順位をつけたなら終了
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
vector<int> P(N);
rep(i, N) cin >> P[i];
vector<int> ans(N, -1);
int r = 1;
while(1){
int x = -1;
rep(i, N){
if(ans[i] != -1) continue;
x = max(x, P[i]);
}
if(x == -1) break;
int k = 0;
rep(i, N){
if(x == P[i]){
ans[i] = r;
k++;
}
}
r += k;
}
rep(i, N){
cout << ans[i] << endl;
}
return 0;
}
すぬけさんのコードを見て勉強しました。
凄い参考になりました。
C - Make it Forest
O(N+Mα(M))
UnionFindの問題です。
閉路とは、グラフ理論において始点と終点が同じ経路の事を
いいます。
UnionFindへ２点を追加する時に、同じグループに属していないか確認しましょう。
UnionFindのデータ構造を知っているか知っていないかの問題です。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
class UnionFind {
private:
vector<int> par_;
public:
UnionFind(int N) : par_(N) {
rep(i, N) par_[i] = i;
}
int root(int x){
if(par_[x] == x) return x;
return par_[x] = root(par_[x]);
}
void unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry) return;
par_[rx] = ry;
}
bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};
int main() {
int N, M;
cin >> N >> M;
int ans = 0;
UnionFind uf(N);
rep(i, M){
int u, v;
cin >> u >> v;
u--; v--;
if(uf.same(u, v)){
ans++;
}else{
uf.unite(u, v);
}
}
cout << ans << endl;
return 0;
}
D - Switch Seats
O(N)
組み合わせの問題です。
下記のテストケースを元に考察します。
3
3
1 2 3 3 2 1
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5
テストケースの3行目、1 2と2 1の様な組み合わせの時にカウントします。
カウントしてはいけない組み合わせは、
テストケースの3行目の時、2 3、3 3、3 2の様な組み合わせです。
i-0からN*2-1までループして判定する組み合わせを探索しましょう。
a1とa2が等しい時は除外します。
a1とa2の順番が異なる時は揃えます。
C++
set<pair<int, int>> st;
rep(i, N*2-1){
int a1 = A[i];
int a2 = A[i+1];
if(a1 == a2) continue;
if(a1 > a2) swap(a1, a2);
st.emplace(a1, a2);
}
配列内の全ての組み合わせを探索しました。
ここから組み合わせの数字が隣り合っているか判定します。
各数字のインデックスを前処理で保持しておきます。
C++
vector<vector<int>> P(N);
rep(i, N*2) P[A[i]].push_back(i);
各数字のインデックスを見て、
- 同じ数字の要素が隣合っていた時は除外
- 組み合わせの数字のインデックスが隣り合っている
を判定して処理します。
C++
int ans = 0;
for(auto [x, y]:st){
int xl = P[x][0], xr = P[x][1];
int yl = P[y][0], yr = P[y][1];
if(xl+1 == xr) continue;
if(yl+1 == yr) continue;
if(abs(xl-yl) == 1 && abs(xr-yr) == 1) ans++;
}
考察が終わりました。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
void solve(int N, vector<int>& A){
vector<vector<int>> P(N);
rep(i, N*2) P[A[i]].push_back(i);
set<pair<int, int>> st;
rep(i, N*2-1){
int a1 = A[i];
int a2 = A[i+1];
if(a1 == a2) continue;
if(a1 > a2) swap(a1, a2);
st.emplace(a1, a2);
}
int ans = 0;
for(auto [x, y]:st){
int xl = P[x][0], xr = P[x][1];
int yl = P[y][0], yr = P[y][1];
if(xl+1 == xr) continue;
if(yl+1 == yr) continue;
if(abs(xl-yl) == 1 && abs(xr-yr) == 1) ans++;
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
rep(i, T){
int N;
cin >> N;
vector<int> A(N*2);
rep(i, N*2) cin >> A[i];
rep(i, N*2) A[i]--;
solve(N, A);
}
return 0;
}
すぬけさんのコードを見て勉強しました。
凄い参考になりました。