A – Changing a Character
問題
問題へのリンク解法
K文字目を小文字に変換して出力するだけ。実装
#include<iostream> #include<vector> #include<map> #include<algorithm> #include<cmath> #include<string> #include<cstdlib> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define MOD 1000000007 using namespace std; typedef long long int ll; const ll INF=(ll)1e18; int main(){ int N,K; cin >> N >> K; string S; cin >> S; S[K-1] = tolower(S[K-1]); cout << S << endl; }
B – YYMM or MMYY
問題
問題へのリンク解法
YYには制約は無いが、MMについては01〜12という制約がある。よって、1〜2文字目と3〜4文字目について、01〜12かどうかをチェックすればよい。・1〜2文字目と3〜4文字目が両方01〜12の場合:AMBIGUOUS
・1〜2文字目のみ01〜12の場合:MMYY
・3〜4文字目のみ01〜12の場合:YYMM
・1〜2文字目と3〜4文字目が両方01〜12以外の場合:NA
実装
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define PRINT(a) cout << (a) << endl #define pb push_back #define eb emplace_back #define mp make_pair #define Fi first #define Se second #define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'; using ll = long long int; using P = pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using pii = pair<int, int>; template <typename T> using PQ = priority_queue<T>; template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const int INF = 1001001001; const ll LINF = 1001001001001001001ll; const int MOD = 1e9 + 7; int main(){ string S; cin >> S; // 1〜2文字目を数値に変換 int x = (S[0]-'0')*10+(S[1]-'0'); // 3〜4文字目を数値に変換 int y = (S[2]-'0')*10+(S[3]-'0'); if(1<=x && x<=12 && 1<=y && y<=12){ cout << "AMBIGUOUS" << endl; }else if(1<=x && x<=12){ cout << "MMYY" << endl; }else if(1<=y && y<=12){ cout << "YYMM" << endl; }else{ cout << "NA" << endl; } }
C – Dice and Coin
問題
問題へのリンク解法
1回目に出たサイコロの数をxとする。xがK以上ならそのまますぬけ君の勝ちになる。xがK未満の場合、xを倍々にしていってK以上になる回数をtとすると、連続してコインの表が出続ける確率は、(1/2)tとなる。最初にサイコロの数xがでる確率は等しく1/nなので、各xごとに上記の確率を求めて1/nすればよい。
実装
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define PRINT(a) cout << (a) << endl #define pb push_back #define eb emplace_back #define mp make_pair #define Fi first #define Se second #define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'; using ll = long long int; using P = pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using pii = pair<int, int>; template <typename T> using PQ = priority_queue<T>; template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const int INF = 1001001001; const ll LINF = 1001001001001001001ll; const int MOD = 1e9 + 7; int main(){ int N,K; cin >> N >> K; double ans = 0; FOR(i,1,N+1){ int t = i; double s = 1.0/N; while(t < K){ s *= 0.5; t = t << 1; } ans += s; } cout << setprecision(12) << ans << endl; }
D – Even Relation
問題
問題へのリンク解法
とある頂点(例えば頂点1)の色を決めて(例えば白)、そこから隣接する頂点への距離が偶数の場合は同じ色(白)、奇数の場合は違う色(黒)に塗っていけば良い。実装方法は深さ優先探索や幅優先探索を使えばよい。(今回の実装例は幅優先探索とした)
実装
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define PRINT(a) cout << (a) << endl #define pb push_back #define eb emplace_back #define mp make_pair #define Fi first #define Se second #define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'; using ll = long long int; using P = pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using pii = pair<int, int>; template <typename T> using PQ = priority_queue<T>; template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const int INF = 1001001001; const ll LINF = 1001001001001001001ll; const int MOD = 1e9 + 7; int main(){ int N; cin >> N; vector<vector<P>> edge(N); vi col(N,-1); REP(i,N-1){ int u,v,w; cin >> u >> v >> w; u--; v--; edge[u].emplace_back(v,w); edge[v].emplace_back(u,w); } queue<int> q; col[0]=0; q.push(0); while(!q.empty()){ int x = q.front(); q.pop(); for(auto e: edge[x]){ int y = e.first; int w = e.second; if(col[y]!=-1)continue; if(w%2==0){ col[y] = col[x]; }else{ col[y] = col[x] ^ 1; } q.push(y); } } REP(i,N){ cout << col[i] << endl; } }
E – 1 or 2
問題
問題へのリンク解法
各X、Y、Zについて、総和が偶数ということは、Zが偶数の場合はXとYは同じ(両方とも1 or 両方とも2)、Zが奇数の場合はXとYは異なる(1と2の組み合わせ)となる。ここで入力例2を例にカードをノード、Zを辺の重みとしてグラフ化してみる。すると、グラフの連結成分のうち、1つのノードの数字が決まれば、残りのノードの数字も決まることがわかる。(下図では数字を色で表している)

なお、連結成分の数はUnion Findを使えば求められる。
実装
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define PRINT(a) cout << (a) << endl #define pb push_back #define eb emplace_back #define mp make_pair #define Fi first #define Se second #define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'; using ll = long long int; using P = pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using pii = pair<int, int>; template <typename T> using PQ = priority_queue<T>; template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const int INF = 1001001001; const ll LINF = 1001001001001001001ll; const int MOD = 1e9 + 7; class UnionFindTree{ public: vector<int> rank,p,count; UnionFindTree() {} UnionFindTree(int size){ rank.assign(size, 0); p.assign(size, 0); count.assign(size,1); REP(i,size)makeSet(i); } void makeSet(int x){ p[x] = x; rank[x] = 0; } bool same(int x, int y){ return findSet(x) == findSet(y); } void unite(int x, int y){ if(findSet(x) == findSet(y))return; x = findSet(x); y = findSet(y); if(rank[x] > rank[y]){ p[y] = x; }else{ p[x] = y; if(rank[x] == rank[y]){ rank[y]++; } } int tmp = count[x] + count[y]; count[x] = tmp; count[y] = tmp; } int findSet(int x){ if(x != p[x]){ p[x] = findSet(p[x]); } return p[x]; } int getCount(int x){ return count[findSet(x)]; } void print(){ REP(i,p.size()){ cout << p[i] << " "; } cout << endl; REP(i,p.size()){ cout << rank[i] << " "; } cout << endl; } }; int main(){ int n,m; cin >> n >> m; UnionFindTree tree(n); REP(i,m){ int x,y,z; cin >> x >> y >> z; x--;y--; tree.unite(x,y); } set<int> st; REP(i,n){ st.insert(tree.findSet(i)); } cout << st.size() << endl; }
コメント