ABC311 反省会
全体的な反省
- 考えていた解法はサンプルできちんと試そう
A,B問題
- 今回は特になし。あっさり解けたと思う。
E問題
コンテスト中に頑張ったが解けなかった。
考えていたこと
各マスからどの程度伸ばせるかということが判別することができれば、解ける。
ただし、 伸ばせる数 程度の計算量になるので、前計算か高速に答える必要がある。
コンテスト中の方針としては、前計算として、各マスから最も近い穴の座標を、それぞれ独立に累積minで記録して、各マスごとにどこまで伸ばせるかを計算しようとした。が、うまくいかなった。提出
なぜだめだったのかを反省も込めて書いてみる。
コンテスト中の方針は、あるマスから、最も近い穴の座標を記録しておき、それをもとに計算するというものだった。
(モチベーションは,、正方形 を考えるときに、最初に当たりそうな穴の座標をでそれぞれ記録したいという感じ。)
ここで、マスのときに、座標とにそれぞれ穴があるものとする。この時、は右下隅とする正方形は答えの候補となりえるが、はとなってしまい答えを導出できない。
がそれぞれの軸についての上限となってくれることを期待したが、最小値同士だと情報が足りない。 例えば、とに穴があってもとなり、情報が消える。
それぞれの情報をマスの座標を保存すれば解ける気もするが、計算パートが大変そう。
いずれせよ、記録しておく値だけで情報が不足する/答えの導出に足りないという部分には気づくべきだった。
解法
結局累積和と二分探索で解いた。こっちのほうが解法が明確がわかりやすいかも...
コンテスト中にひらめきたい解法だった。
#include <bits/stdc++.h> using namespace std; using Int = long long; template<class F,class T> auto maximize(T imin,T imax,F &f){ while(imax - imin > 1){ T mid = imin + (imax - imin)/2; if(f(mid)) imin = mid; else imax = mid; } return imin; } template <class T> class Cumulative2DSum { // query[sx,gx),[sy,gy) public: vector<vector<T>>sum; T e; Cumulative2DSum(vector<vector<T>>&v,T e) { // W is x, H is y int W = v.front().size(); int H = v.size(); ++H , ++W; sum = vector<vector<T>>(H,vector<T>(W,e)); for(int i = 0; i < v.size(); ++i){ for(int j = 0; j < v[i].size(); ++j){ sum[i + 1][j + 1] += v[i][j]; } } for(int i = 1; i < sum.size(); ++i){ for(int j = 1; j < sum[i].size();++j){ sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]; } } } T query(int sx,int sy,int gx,int gy){ return sum[gy][gx] - sum[sy][gx] - sum[gy][sx] + sum[sy][sx]; } }; int main(){ std::ios_base::sync_with_stdio(false); cin.tie(nullptr); int H, W, N; cin >> H >> W >> N; map<pair<int,int>,int>pos; vector<vector<Int>>h(H, vector<Int>(W,0)); for(int i = 0; i < N; ++i){ int y,x; cin >> y >> x; --y; --x; h[y][x]++;; } auto csum = Cumulative2DSum<Int>(h, 0LL); int cx = 0, cy = 0; auto f = [&](int mid) { if(cx + mid >= W or cy + mid >= H) return false; return csum.query(cx,cy,cx + mid + 1,cy + mid + 1) == 0; }; Int ans = H * W - N; for(int y = 0; y < H; ++y){ for(int x = 0; x < W; ++x){ if(h[y][x]++) continue; cx = x; cy = y; Int remu = maximize(0, 3001,f); ans += remu; } } cout << ans << endl; }
E- NAND repeatedly
問題
を求めよ。
ただし、 である
考えてたこと
・二重和なので、一度全体の和を求めて、いい感じに調整して回計算するのだろうなという予測を立てる
・否定論理積の性質から、の値は0または1のどちらかである。
・ここで、 は、先程の式から一つ前の値と文字の値で決まる。つまり、文字目は直前の値の種類だけ状態数がある。
・一つ前の値がとしたときの、から番目までの累積和を計算して、この2つで累積和の値をメモ化しておく。
・あとは一つ目の和をループして終わり。
#include <bits/stdc++.h> using namespace std; using Int = long long; int N; string s; Int rec(int idx, int pbit,vector<vector<Int>>&memo, vector<vector<bool>>&used, vector<int>&A){ if(used[idx][pbit]){ return memo[idx][pbit]; } used[idx][pbit] = true; return memo[idx][pbit] = (idx + 1 < N ? rec(idx + 1,!(pbit && A[idx]),memo,used,A) : 0) + !(pbit && A[idx]); } int main(){ std::ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; cin >> s; vector<int>A; for(auto c : s) A.push_back(c - '0'); vector<vector<Int>>memo(N,vector<Int>(2,0LL)); vector<vector<bool>>used(N, vector<bool>(2,false)); Int ans = 0; for(int i = 0; i < N; ++i){ ans += A[i] + (i + 1 < N ? rec(i + 1,A[i],memo,used,A) : 0); } cout << ans << endl; }
感想
解放までは5分だったけど、累積和の書き方でこじらせた。
ABC310 反省会
はじめに
私生活があまりに忙しくなりましたが、なんとか生きてます。
最近またABCに出始めたのですが、ボコボコにされているのでクイック反省会をブログでやりたいと思います
全体的な反省
- 問題文をちゃんと読もう
- Cぐらいまで速解き失敗するとゴタゴタになるのやめたい
A, B問題
- B問題で一生誤読していて辛かった。上方互換というより、価格が安いが同じ機能があるものみたいな言い回しにしてほしかったな
- ちゃんと読めてない自分が悪いが...
C問題
- 重複している棒の数の問題を解いていて、一生あわなかった
D問題
- どうみても全探索しか思いつかなったので、計算量がかなり不安だが全探索の方針を考えた。
- 実装してみるが合わない。最初の実装はこんな感じ
void dfs(int p, int t){ // 空のチームがあったらNG if(p == N - 1){ bool ok = true; for(auto& v : team) if(v.empty()) ok = false; if(ok) ++ans; return; } for(int nt = 0; nt < T; ++nt){ // 追加予定のチームを舐めて、組み合わせが悪いペアがなければ追加する bool ok = true; for(auto u : team[nt]){ if(e.find(minmax(p + 1, u))!= e.end()) ok = false; } if(ok){ team[nt].push_back(p + 1); dfs(p + 1,nt); team[nt].pop_back(); } } return; }
どうやらチーム数の区別がうまくいってないらしい。
具体的には、とを重複して数え上げているらしい。
順序性を導入すると重複なしで数え上げることができそうだが、コンテスト中は思いつかず...
解説
一番大事な部分を引用するとこうなる
ここに番目の選手を追加するには、たかだか チームのいずれかに 番目の選手を入れるか、(チーム数がより少ないとき)新しく番目の選手しかいないチームを作るかのどちらかです。
自分がやりたいことを正しくやろうとすると上のような感じになるらしい。
具体的に考えてみよう。人に対しての操作を考える。全てのチームに対して追加可能かどうか判定するのは、重複して計算してしまうので無駄になる。
すでに人が存在するチームに追加するかどうかは、全て試す。を新しいチームに追加する場合は、できるだけ小さい数字のチームに追加するように変更してみる。(つまり、ただ一つに定まる)
ACしたコード
void dfs(int p, int t){ if(p == N - 1){ ans += (team.back().empty() ? 0 : 1); return; } for(int nt = 0; nt < T; ++nt){ bool ok = true; for(auto u : team[nt]){ if(e.find(minmax(p + 1, u))!= e.end()) ok = false; } if(ok && not team[nt].empty()){ team[nt].push_back(p + 1); dfs(p + 1,nt); team[nt].pop_back(); } } // 新しくチームに追加する for(int nt = 0; nt < team.size(); ++nt){ if(team[nt].empty()){ team[nt].push_back(p + 1); dfs(p + 1,nt); team[nt].pop_back(); // break immediately break; } } return; }
と修正したらACした。
たったこれだけでteamを区別無くカウントできるのはすごい。思いつけなかったので完全敗北です。
E問題
なんかDより解かれているイメージ有るので、後日解きます。
解きました。
E - Safety Journey
2023年苦手なジャンルを克服しよう数え上げ編です。
解法/ 考えてたこと
解説ACしたが思いつけそうな問題だった。反省。
- 総当りは当然不可能なので、番目のときに頂点にいるときの総数を管理する方針を考えた。ただし、これは更新がかかる。具体的には、 番目のに対して個の更新を考える必要があり、できない。
- ならば余事象で攻めるか?となるが、できない。使えない辺を使っているパスを重複なく列挙するのは難しい。これを実装するまで気づかなかったのが本当に良くない。
- 最初の方針で攻めるしかないかなとなりつつ、計算量を減らせない。おそらく更新をサボるんだろうなぁ(つまり、使わない辺だけを使って更新するんだろうなぁ)と考えていたが、思いつけなかった。
- ここから解法。3番目の方針で解ける。テーブルは以下の通り
番目のパスのときに頂点にいるときの総数 で解ける。
更新は、使わない辺だけを使うのではなく、すべての辺を使った結果から、使わない辺を使っている結果を引く で更新すれば良い。イメージ的には累積和みたいな感じ。
うーん確かに。式にしてみればあっさりしている。列挙となった時かなり頭が固くなっている気がするので、慣れていきたいところ。
提出したコード
特に理由は無いけどGoで書きました
package main import ( "bufio" "fmt" "os" "strconv" ) var sc = bufio.NewScanner(os.Stdin) func nextInt() int { sc.Scan() i, e := strconv.Atoi((sc.Text())) if e != nil { panic(e) } return int(i) } func main() { sc.Split(bufio.ScanWords) N, M, K := nextInt(), nextInt(), nextInt() edge := make([][]int, N) dp := make([][]int64, K+1) mod := int64(998244353) for i := range dp { dp[i] = make([]int64, N) } for i := 0; i < M; i += 1 { u, v := nextInt()-1, nextInt()-1 edge[u] = append(edge[u], v) edge[v] = append(edge[v], u) } dp[0][0] = 1 prev := int64(1) for i := range dp { if i == 0 { continue } for j := range dp[i] { tmp := prev tmp -= dp[i-1][j] tmp += mod tmp %= mod for k := range edge[j] { nxt := edge[j][k] tmp -= dp[i-1][nxt] tmp += mod tmp %= mod } dp[i][j] = tmp } tmp := int64(0) for j := range dp[i] { tmp += dp[i][j] tmp %= mod } prev = tmp } fmt.Println(dp[K][0]) }
E - Throwing the Die
2023年苦手ジャンルがんばって埋めようシリーズ期待値編です。
問題
考えてたこと
サンプル2を導出するのに時間がかかって困った。ゲームも組み合わさってる用に見えてかなり時間がかかってしまった。
まずは容易に導出することができる。次のの期待値の求め方がしっくりこなかった。
・最初は出目によって場合分けしてたので、二ターン目以降も出目によって場合わけする?
・各ターンで前のターンの出目より大きい場合だけ列挙する?
・ターン毎に独立ならなんターン目でも* 出目になる?
・最初の出た目に書かわず次の期待値だけどあってるのか?
などなど
最初は出目によって場合分けして、その後の期待値は全部同じじゃん、そんなことある?みたいな気持ちなってた。
解法
だいぶ迷走してしまったが、問題を解くために必要を知識を整理しよう
- ゲームを続行するか終了するかを選択できる
- ゲームを終了する場合は、最後の出目だけがスコアに関係する。途中までのスコアは関係ない
- これをふまえるとスコアの期待値が最大になるように行動するとは、次の試行で今の期待値を超えそうなら続ければ良い。
- スコアの期待値自体は試行回数をNとするとになる。
- スコアが変わらないのに期待値だけ下がり続けるのが直感に反していて答えにたどり着けなかった。論理的に攻めよう
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; double ans = 3.5; for(int i = 1; i < N; ++i) { double tmp{}; for(int j = 1; j <= 6; ++j) { tmp += max(static_cast<double>(j), ans); } tmp /= 6; ans = max(ans, tmp); } cout << setprecision(10) << fixed << ans << endl; }
E - Swap Places
解法
すんなりと解けた。一回の動作で2つの頂点が移動するという点が厄介かもしれないが、拡張グラフ上でのDijkstraの気持ちになれば見通しが良くなる。
Dijkstra法のキモは、ある状態の最短経路(文脈によっては当然最短経路ではない場合もあるけど)を順次確定させていくことで、効率よく全体の最短経路を求める点である。この問題での状態とは2つのコマの位置、すなわち、である。
#include <bits/stdc++.h> using namespace std; void solve() { int N,M; cin >> N >> M; vector<int>C(N); vector<vector<int>>edge(N); for(auto& c : C) cin >> c; for(int i = 0; i < M; ++i) { int u,v; cin >> u >> v; --u; --v; edge[u].push_back(v); edge[v].push_back(u); } constexpr int inf = 1e9; vector<vector<int>>d(N,vector<int>(N,inf)); d[0][N - 1] = 0; using p = pair<int, pair<int,int>>; priority_queue<p,vector<p>, greater<>>q; q.emplace(d[0][N-1],make_pair(0,N -1)); while(not q.empty()) { int cd = q.top().first; const auto [u,v] = q.top().second; q.pop(); if (cd > d[u][v]) continue; for(auto nv : edge[v]) { for(auto nu : edge[u]) { if(nu == nv or C[nv] == C[nu]) continue; int nxt = cd + 1; if(d[nu][nv] > nxt) d[nu][nv] = nxt, q.emplace(d[nu][nv], make_pair(nu,nv)); } } } cout << (d[N - 1][0] == inf ? -1 : d[N - 1][0]) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while(T --> 0) solve(); }
E - Colorful Blocks
2023年は数え上げとか期待値とか苦手分野をやっていきます。
解法
条件の部分を言い換えると、隣接している」かつ「同色」を満たすブロックの組は K 組以下であると言い換えると良いらしい。
日本語が読めないので競プロサークルに助けを求めたら言い換えてくれました。Gくんありがとう。
さて、条件の部分から考察を考える。一度に組以下という条件を扱うのは厄介そうなので、何組使うかを決め打ちして考えることにしよう。(制約的にも間に合う, )
重要な考察として、個のブロックの中で、「隣接するブロックの組」は 個存在する。したがって、同じ色で塗られている組組のとき、個の「隣接するブロックの組」から個を選べば良い。
色の塗り方は、隣接する色と違う色で塗らなければならない。これは、最初だけ色選べて、それ以降は色から選べるというふうに考えればよい。
提出コード
#include <bits/stdc++.h> using namespace std; using Int = long long; constexpr Int mod = 998244353; template <class T> T modpow(T a, T b) { if (b == 0) return T(1); if (b % 2 == 0) { long long d = modpow(a, b / T(2)); return (d * d) % mod; } else { return (a * modpow(a, b - 1) % mod ); } } template <class T> class ModComb { public: T maxn,mod; vector<T>fac,finv,inv; ModComb(T maxn_,T mod_) : maxn(maxn_),mod(mod_),fac(maxn_),finv(maxn_),inv(maxn_){ fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (T i = T(2); i < maxn; i++){ fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i] % mod; } }; T computeComb(T n,T k){ if (n < k) return T(0); if (n < 0 || k < 0) return T(0); return fac[n] * (finv[k] * finv[n - k] % mod) % mod; } }; int main() { Int N, M, K; cin >> N >> M >> K; Int ans = modpow(M - 1, N - 1); ans *= M; ans %= mod; auto Comb = ModComb<Int>(1000000LL,mod); for(Int k = 1; k <= K; ++k) { Int res = Comb.computeComb(N - 1,k); Int a = modpow(M - 1, N - 1 - k); a *= M; a %= mod; a *= res; a %= mod; ans += a; ans %= mod; } cout << ans << endl; }