ABC029を解いてみた
A問題
文字列の最後にsを連結しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { string s; cin >> s; cout << s + 's' << endl; return 0; }
B問題
全ての文字列についてrが含まれているか全探索しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { string s[12]; for(int i=0; i<12; i++) cin >> s[i]; int ans = 0; for(int i=0; i<12; i++) { for(int j=0; j<s[i].size(); j++) { if(s[i][j] == 'r') {ans++; break;} } } cout << ans << endl; return 0; }
C問題
8重のforループを書く気はしなかったので深さ優先探索で全列挙しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int n; char s[3] = {'a', 'b', 'c'}, ans[10]; int dfs(int i) { if(i == n) {cout << ans << endl; return 0;} for(int j=0; j<3; j++) { ans[i] = s[j]; dfs(i+1); } return 0; } int main(void) { cin >> n; dfs(0); return 0; }
D問題
9まで、99まで、999まで…に1が出てくる数を求め、この数と各桁の数に応じて場合分けして全パターンを求めました。
昔算数でこんな問題解いた気がします。解説の解法がシンプルでわかりやすかった。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 //10のべき乗を求める ll mypow(int i) { ll ret = 1; for(int j=0; j<i; j++) ret *= 10; return ret; } int main(void) { ll memo[15], n, ans = 0; cin >> n; //桁数を求める int digit = 0; ll _n = n; while(_n > 0) { _n /= 10; digit++; } // 9まで、99まで、999まで…に含まれる1の数を求める memo[0] = 1; for(int i=1; i < digit; i++) { memo[i] = mypow(i) + (memo[i-1]*10); } int temp; for(int i=digit-1; i > 0; i--) { // i桁目の数 temp = n / mypow(i); if(temp >= 2) { ans += mypow(i) + temp*memo[i-1]; } else if(temp == 1) { // a = n % 10^i ll a = n - temp*mypow(i); ans += a + memo[i-1] + 1; } // temp * 10^i までに含まれるiの数が求められている n -= temp * mypow(i); } // 1の位が1以上なら1の数はプラス1 if(n >= 1) {ans++;} cout << ans << endl; return 0; }
ABC028を解いてみた
A問題
条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int n; cin >> n; if(n <= 59) cout << "Bad" << endl; else if(n <= 89) cout << "Good" << endl; else if(n <= 99) cout << "Great" << endl; else cout << "Perfect" << endl; return 0; }
B問題
文字コードでint(s[i])-int('A')が0,1,2,3,4,5になるのを使いました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { string s; cin >> s; int a[6]={0}; for(int i=0; i<s.size(); i++) { a[int(s[i])-int('A')]++; } cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << " " << a[5] << endl; return 0; }
C問題
5C3なら全探索でも余裕そうなので、1番大きい、2番目に大きい、3番目に大きい数字を記録しつつ全ての組み合わせについて全探索しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int a[5]; cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4]; int ret = 0, max1 = -INF, max2 = -INF, max3 = -INF; for(int i=0; i<5; i++) { for(int j=i+1; j<5; j++) { for(int k=j+1; k<5; k++) { ret = a[i] + a[j] + a[k]; if(ret > max1) { max3 = max2; max2 = max1; max1 = ret; } else if(ret > max2) { max3 = max2; max2 = ret; } else if(ret > max3) { max3 = ret; } } } } cout << max3 << endl; return 0; }
D問題
全ての数字が異なる場合、kが一つとkより小さい数が一つ、kより大きい数が一つになります。3P3=6より(k-1)*(n-k)*6通りのパターンが存在します。同じ数が2つの場合、kが二つとk以外の数が一つになります。3P1=3より(n-1)*3通りのパターンが存在します。同じ数が3つの場合、kが3つになります。これは1通りしかありません。答えは {(k-1)*(n-k)*6+(n-1)*3+1}/(n*n*n) になります。
数学っぽく解くだけだったのでそんなに手こずらなかったです。doubleとintで何回かWA出したので気をつけたい。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { double n, k; cin >> n >> k; double ans = (k-1)*(n-k)*6 + (n-1)*3 + 1; cout << fixed << setprecision(15) << ans/(n*n*n) << endl; return 0; }
ABC027を解いてみた
A問題
長方形は向かい合っている辺の長さが等しいです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int a, b, c; cin >> a >> b >> c; if(a == b) cout << c << endl; else if(b == c) cout << a << endl; else if(c == a) cout << b << endl; return 0; }
B問題
一つの島にいるべき人数はわかるので橋より左の島、右の島にいるべき合計人数は求められます。各橋について調べていくO(N)で求められます。accumulateは積極的に使っていきたいです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 #define MAX_N 100 // lからrまで足す int sum(vector<int> v, int l, int r) { int ret = 0; for(int i=l; i<=r; i++) ret += v[i]; return ret; } int main(void) { int temp, n; cin >> n; vector<int> a; for(int i=0; i<n; i++) { cin >> temp; a.push_back(temp); } if(accumulate(a.begin(), a.end(), 0) % n != 0) {cout << -1 << endl; return 0;} int num = accumulate(a.begin(), a.end(), 0)/n; int ans = 0; for(int i=1; i<n; i++) { if(sum(a, 0, i-1) != i*num || sum(a, i, n-1) != (n-i)*num) { ans++; } //cout << "i:" << i << " left:" << sum(a, 0, i-1) << " right:" << sum(a, i, n-1) << endl; } cout << ans << endl; return 0; }
C問題
nimとかgrundy数とかで考えたがわからなかったので解説見て実装しました。木の深さが奇数なら先手は2x+1、後手は2xを選びます。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { ll n; cin >> n; int depth = 0; for(ll i = n; i > 0; i /= 2) depth++; // true だったら 先手の番 int turn = true; ll i = 1; //cout << "i:" << i << " turn:" << turn << endl; while(i <= n) { if(depth % 2 == 0) { if(turn) i *= 2; else i = 2*i+1; } else { if(turn) i = 2*i+1; else i *= 2; } turn = !turn; //cout << "i:" << i << " turn:" << turn << endl; } if(turn) cout << "Takahashi" << endl; else cout << "Aoki" << endl; return 0; }
D問題
解説見て実装しました。考察力つけたい。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 // lからrまで足す int sum(vector<int> v, int l, int r) { int ret = 0; for(int i=l; i<=r; i++) ret += v[i]; return ret; } int main(void) { string s; cin >> s; vector<int> v; int plusnum=0, minusnum=0; for(int i=s.size()-1; i>=0; i--) { if(s[i] == '+') plusnum++; else if(s[i] == '-') minusnum++; else v.push_back(plusnum-minusnum); //cout << "plus:" << plusnum << " minus:" << minusnum << endl; } sort(v.begin(), v.end()); cout << sum(v, v.size()/2, v.size()-1) - sum(v, 0, v.size()/2-1) << endl; return 0; }
ABC025を解いてみた
A問題
入力をソートして(n-1)/5文字目、(n-1)%5文字目が答えの文字列になります。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { vector<char> str; string ans = "", temp; int n; cin >> temp; cin >> n; for(int i=0; i<5; i++) str.push_back(temp[i]); sort(str.begin(), str.end()); ans += str[(n-1)/5]; ans += str[(n-1)%5]; cout << ans << endl; return 0; }
B問題
d[i]がAからBの範囲内かを判定して条件にそってシミュレーションしていきました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 100 int main(void) { int n, a, b, d[MAX_N], now = 0; string temp; cin >> n >> a >> b; for(int i=0; i<n; i++) { cin >> temp >> d[i]; if(d[i] < a) d[i] = a; else if(d[i] > b) d[i] = b; if(temp == "West") d[i] *= -1; now += d[i]; } if(now < 0) cout << "West " << abs(now) << endl; else if(now > 0) cout << "East " << now << endl; else cout << now << endl; return 0; }
C問題
解説を読んでminimax法をつかって実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1e9 int a[3][3], b[2][3], c[3][2]; // minimax法 int minimax(int cnt) { // 最終盤面の得点を求める if(cnt == 9) { int result = 0; for(int i=0; i<2; i++) { for(int j=0; j<3; j++) { if(a[i][j] == a[i+1][j]) result += b[i][j]; } } for(int i=0; i<3; i++) { for(int j=0; j<2; j++) { if(a[i][j] == a[i][j+1]) result += c[i][j]; } } return result; } int turn = cnt%2; int ret = (turn == 0 ? -INF : INF); for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { //cout << a[i][j] << endl; if(a[i][j] == -1) { a[i][j] = turn; // どちらのターンかによってmaxかminを変える if(turn == 0) { ret = max(ret, minimax(cnt+1)); } else { ret = min(ret, minimax(cnt+1)); } a[i][j] = -1; } } } return ret; } int main(void) { // 入力 int sum = 0; for(int i=0; i<2; i++) { for(int j=0; j<3; j++) { cin >> b[i][j]; sum += b[i][j]; } } for(int i=0; i<3; i++) { for(int j=0; j<2; j++) { cin >> c[i][j]; sum += c[i][j]; } } memset(a, -1, sizeof(a)); //minimax法を実行 int ans = minimax(0); cout << ans << endl; cout << sum - ans << endl; return 0; }
D問題
ビットDPの実装で詰まったのでできたら追記します…
ABC026を解いてみた
A問題
x=1からx=a-1まで全探索で実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, ret = 0, maxret = -1; cin >> a; for(int x=1; x<a; x++) { ret = x*(a-x); maxret = max(maxret, ret); } cout << maxret << endl; return 0; }
B問題
外から奇数番目の円を足して、偶数番目の円を引く包除原理っぽい感じで解きました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 1000 #define PI 3.1415926535 int main(void) { int n, ans = 0; vector<int> r; //入力 cin >> n; for(int i=0; i<n; i++) { int temp; cin >> temp; r.push_back(temp); } //包除原理(?) sort(r.begin(), r.end(), greater<int>()); for(int i=0; i<n; i++) { int sign = (i%2 ? -1: 1); ans += sign * r[i] * r[i]; } cout << setprecision(11) << ans * PI << endl; return 0; }
C問題
深さ優先探索で全探索しました。N<=20なので実行時間は余裕ありそうな設定になってそう。配列の境界の扱いを間違えて一回WA出したのは気をつけたいです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 20 #define INF 1e9 int n, lis[MAX_N][MAX_N], dp[MAX_N]; //社員numberの給料を返す int dfs(int number){ vector<int> subordinate; //直属の部下の番号 for(int i=0; i<n; i++) if(lis[number][i] == 1) subordinate.push_back(i); //直属の部下がいなければ給料は1 if(subordinate.empty()) return dp[number] = 1; int maxret = -INF, minret = INF; for(int i=0; i<subordinate.size(); i++) { maxret = max(maxret, dfs(subordinate[i])); minret = min(minret, dfs(subordinate[i])); } return dp[number] = maxret + minret + 1; } int main(void) { cin >> n; if(n == 1) { cout << "1" << endl; return 0; } memset(lis, 0, sizeof(lis)); //入力 隣接行列にする for(int i=1; i<n; i++) { int temp; cin >> temp; lis[temp-1][i] = 1; } int ans = dfs(0); //for(int i=0; i<n; i++) cout << "i:" << i << " dp:" << dp[i] << endl; cout << ans << endl; return 0; }
D問題
直線とsin波を足し合わせたグラフになるので、上下に振れながら大きくなっていくグラフになります。答えが小数になる関数の探索なので2分探索かなと目処を立てて実装しました。最小のtを求めるコードを書きましたが最小に限定されてなかったに解き終わった後で気づきました…
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define PI 3.14159265359 double a, b, c; // f(x) double f(double t) { return a*t + b*sin(c*t*PI); } int main(void) { cin >> a >> b >> c; //一周期ごとに区切って double left = 1/(2*c), right = 5/(2*c); for(right=5/(2*c); right<110; right += (2/c)) { if(f(right) >= 100) break; left = right; } //二分探索 while(abs(f(left)-100) > 0.000001) { double mid = (left+right)/2; double fmid = f(mid); if( fmid > 100) { right = mid; } else if( fmid < 100) { left = mid; } } cout << fixed << setprecision(15) << left << endl; return 0; }
ABC024を解いてみた
A問題
条件に沿って実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, b, c, k, s, t, ans = 0; cin >> a >> b >> c >> k; cin >> s >> t; if(s+t >= k) ans = s*(a-c)+t*(b-c); else ans = s*a+t*b; cout << ans << endl; return 0; }
B問題
a[i+1]-a[i]がt未満かどうかで場合分けしました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 100000 int main(void) { int n, t, a[MAX_N], ans=0; //入力 cin >> n >> t; for(int i=0; i<n; i++) cin >> a[i]; for(int i=0; i<n-1; i++) { if(a[i+1]-a[i] < t) ans += a[i+1]-a[i]; else ans += t; } ans += t; //出力 cout << ans << endl; return 0; }
C問題
蟻本で見たことがあるような気がしてセグメントツリーを使うのかと考えてもO(NDK)の解法しか思いつかず、解説を見てできるだけ始点から終点に近づく方向に進める貪欲でO(DK)で実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_D 10000 #define MAX_K 100 int main(void) { int n, d, k, l[MAX_D], r[MAX_D], s[MAX_K], t[MAX_K]; cin >> n >> d >> k; for(int i=0; i<d; i++) cin >> l[i] >> r[i]; for(int i=0; i<k; i++) cin >> s[i] >> t[i]; for(int i=0; i<k; i++) { //今たどり着けるもっとも進んだ頂点 int now = s[i]; for(int j=0; j<d; j++) { // sからtへ増える方向なら if(s[i] <= t[i]) { if(l[j] <= now && now <= r[j]) now = r[j]; if(now >= t[i]) { cout << j+1 << endl; break; } // sからtへ減る方向なら } else { if(l[j] <= now && now <= r[j]) now = l[j]; if(now <= t[i]) { cout << j+1 << endl; break; } } } } return 0; }
D問題
解説を見て実装しました。組み合わせの考え方からr, cをA, B, Cで表す。MOD内での計算方法を使ってr, cを計算する。MODで除算はフェルマーの小定理と二分累乗法を使えば高速に計算可能。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 ll binpow(ll x, ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } return a % MOD; } int main(void) { ll a, b, c; cin >> a >> b >> c; ll ab = a*b%MOD, bc = b*c%MOD, ca = c*a%MOD; ll c_deno = (ca-bc+ab+MOD)%MOD, r_deno = (ab-bc+ca+MOD)%MOD; ll c_deno_inv = binpow(c_deno, MOD-2), r_deno_inv = binpow(r_deno, MOD-2); ll _c = ((bc-ab+MOD)*c_deno_inv)%MOD, r = ((bc-ca+MOD)*r_deno_inv+MOD)%MOD; cout << r << " " << _c << endl; return 0; }
ABC049を解いてみた
A問題
入力がa, i, u, e, oならvowel、そうでなければconsonantを出力しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { string str; cin >> str; if(str == "a" || str == "i" || str == "u" || str == "e" || str == "o") cout << "vowel" << endl; else cout << "consonant" << endl; return 0; }
B問題
入力を配列として全部受け取ってから、問題文の数式のように((i+2)/2)-1と行を求めること(配列は0スタートなのでその分ずれる)で実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int h, w; char str[100][100]; string temp = ""; cin >> h >> w; for(int i=0; i<h; i++) { for(int j=0; j<w; j++) { cin >> str[i][j]; } } for(int i=0; i<2*h; i++) { for(int j=0; j<w; j++) { temp += str[((i+2)/2)-1][j]; } cout << temp << endl; temp = ""; } return 0; }
C問題
C++の文字列関係をまだ勉強してなかったので文字列操作について知ってるPythonで実装しました。dreamのあとにer, erase, eraserが来る場合で分けて処理しました。
s = input() flag = 1 i = 0 while i < len(s): if s[i:i+5] == 'dream': if s[i+5:i+10] != "erase" and s[i+5:i+7] == "er": i += 7 elif s[i+5:i+11] == "eraser": i += 11 elif s[i+5:i+10] == "erase": i += 10 else: i += 5 elif s[i:i+6] == "eraser": i += 6 elif s[i:i+5] == "erase": i += 5 else: flag = 0 break if(flag == 1): print("YES") else: print("NO")
D問題
解いた過去問でUnion-Find木の問題があったのに勉強を後回しにしていたらUnion-Findの問題が出てしまってちょっとショック。実装でつまってるので解けたら追記。