第三回 アルゴリズム実技検定

PAST003H 座標 \(i\) にいるとき，次に取るべき行動は， 今までの行動とは無関係に選べる． つまり，時刻だけが重要で今までの選択は無関係なので， 状態をまとめることができ，これはDPで実現可能． 実装ジャンプ中にゴールするときだけ注意． 問題文にも書いてあるし， \(T_{j}\) たちが全て偶数という制約もある． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, l; cin >> n >> l; set<ll> x; rep(i,n) { ll a …

PAST003I 転置のクエリだけが時間がかかるので，そこを何とかする． 転置は2回繰り返すともとに戻るので，回数だけ記録しておく． また，行と列は独立に操作可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, q; cin >> n; cin >> q; auto f = [&](ll h, ll w) -> ll { return n*h + w; }; bool tr = false; vvll pe(2, vll(n)); rep(i,2) rep(j,…

PAST003J LISに近い問題． 実験してみると，子供 \(i \in N\) が食べた最大の寿司を \(v_{i}\) とおくと， \(v\) は常に降順． よって，誰が食べるのかは binary search で求まる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m; cin >> n >> m; vll a(m); rep(i,m) { cin >> a[i]; a[i] *= -1; } vll v(n,INFL); rep(i,m){ auto…

PAST003K データ構造の問題． 愚直に移動を実装していてはTLE. コンテナ毎について， 下に何があるか，上に何があるか を記録しておく． 切れ目とつなぎ目だけ更新すれば良いので \(O(Q)\) 実装今回の問題では，上に何があるかは記録しなくてもよい，また，机とコンテナを区別するために， 机 \(i\) を \(-i\)として記録して， コンテナ \(j\) を \(j\)として記録する． \(-i\) を使うため 0 が出てくると困るので， 1-indexed とする． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/…