4完でレート変動なし！ｗ
Dでアホなことするし、Fググって貼ったのにWA生やすしアだったね
A - Next Alphabet
char型を+1する
char型はc++みたいに出来るのでキャストしなくて楽になる
今回は使わないけどfor(char c='a';c<='z';c++)みたいにも出来るね
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); char c; cin >> c; c++; cout << c << endl; }
B - Achieve the Goal
必要な点数はでわかる
後はこれがK以下になるかどうかを見ればいい
必要な点数が負（すでに条件を満たしている）ときは0を出力する（サンプルが優しいね）
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N, K, M; cin >> N >> K >> M; vector<int > A(N); int sum = 0; REP(i,N-1){ cin >> A[i]; sum += A[i]; } int res = N * M - sum; if(res < 0) res = 0; if(res <= K) cout << res << endl; else cout << -1 << endl; }
C - Welcome to AtCoder
解いてるときはなんとも思ってなかったんだけど結構WAを生やした人が多かったっぽい
各問題のWAの数を順に加算していって、ACが出たらその時点WAの数を加算する
一度ACが出た問題はこれ以降見なくていいのでboolでフラグを持っておく
誤読というか問題文の条件を見落とした（勘違いした）人が多かったみたい
こどふぉやると耐性つくのでみんなこどふぉやろうな...！
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N, M; cin >> N >> M; vector<bool> ac(N); map<int, int> mp; ll ans = 0; ll cnt = 0; REP(i,M){ int p; string S; cin >> p >> S; p--; if(ac[p]) continue; if(S == "AC" && !ac[p]){ ac[p] = true; ans += mp[p]; cnt++; } else{ mp[p]++; } } cout << cnt << " " << ans << endl; }
D - Maze Master
最短距離の最大化か〜うーん、ダイクストラ！ｗ
頭が悪いので始点と終点を全探索して毎回ダイクストラをし1ケースTLE（ええ...）
よく考えると始点を決めれば終点は一意に決まるので始点全探索だけでいい
もっと考えるとわざわざダイクストラしなくてもBFSするだけでいい
無駄に時間とペナを増やしてしまったので反省…
提出コード
char fi[22][22]; int H, W; int ans = 0; int check(int sh, int sw){ int memo[22][22]; REP(i,22) REP(j,22) memo[i][j] = INF; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q; q.emplace(0, sh, sw); memo[sh][sw] = 0; while(!q.empty()){ ll c; int h, w; tie(c, h, w) = q.top(); q.pop(); REP(i,4){ int nh = h + dy[i]; int nw = w + dx[i]; if(!(0 <= nh && nh < H && 0 <= nw && nw < W)) continue; if(fi[nh][nw] == '#') continue; if(memo[nh][nw] > c + 1){ memo[nh][nw] = c + 1; q.emplace(c + 1, nh, nw); } } } int res = 0; REP(i,H) REP(j,W){ if(memo[i][j] != INF) chmax(res, memo[i][j]); } return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W; REP(i,H) REP(j,W) cin >> fi[i][j]; REP(i,H) REP(j,W){ if(fi[i][j] == '#') continue; int tmp = check(i,j); chmax(ans, tmp); } cout << ans << endl; }
E - Max-Min Sums
こういうのは取り敢えずソートして最小を決め打ちで考えてみる
最小を1個決めた時、これが最小となるのは残りK-1個がこれより上になればいい
全部の数列を見るのにかかるので、残りを効率的に探したい
本番中は最小を決めた後にを直接求めようとしてセグ木か〜？って言ってサンプル2が合わずにFを見たら貼るだけが出来そうな見た目をしていたので移行
実は最大と最小の総和は別々に求めても良い
最小で考えると、昇順に見ていき、を最小として使う場合、残りのK-1個がこれ以上である必要がある
以上のものは
個あり、その選び方は
通りあるので、
を最小の総和として加算していく
最大の総和も同様に求めることが出来るので後は最大の総和から最小の総和を引いたものが答え
あとはMODに気をつけばおっけー（けんちょんさんのmodintパクってます…いつもありがとうございます…）
提出コード
template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; // 二項係数ライブラリ template<class T> struct BiCoef { vector<T> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].getmod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; using mint = Fp<MOD>; BiCoef<mint> bc; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; vector<ll> A(N); REP(i,N) cin >> A[i]; sort(A.rbegin(), A.rend()); bc.init(510000); mint ans = 0; for(int i=0;i<N-K+1;i++){ mint tmp = mint(A[i]) * bc.com(N-i-1, K-1); ans += tmp; } reverse(A.begin(), A.end()); for(int i=0;i<N-K+1;i++){ mint tmp = mint(A[i]) * bc.com(N-i-1, K-1); ans -= tmp; } cout << ans << endl; }
F - Enclose All
パット見ほぼ凸包じゃんとなる
人のライブラリを漁る→点集合の円の中心を求めるライブラリがある
これを使って半径求めればいけるやろ！1ケースWA（お終い）
誤差で死んでるっぽい？
「最小包含円」でググると以下の記事がヒットするのでこれをちょっと書き換えるとAC（本番中ここに辿り着いた人多いっぽい）
本番中ここのページも見ていたはずなのにスルーしちゃったんだよなあ（悲しいね）
tubo28.me
おわりに
色々反省が多いけどDで無駄に時間かけちゃったのがアかな
Eも途中で投げてFの検索してたし、Fも結局AC出来ないしで酷かったね
Fの正攻法もちゃんとやっておこう
