[JOI精進録] 難易度7「水ようかん」(JOI2017/2018 予選D)
問題リンク
問題概要
水ようかんを指定された場所から何箇所か選んで切る。
最大の大きさと最小の大きさの差を最小化してください。
解説
AC解法 (100/100点)
最小値を全探索し、
個目の切れ目までを考えたときの最大の大きさの最小値
との差の最小値を求めればよいです。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,t; cin >> n; vector<int> acc(n+1); for (int i(0);i < n;++i) (cin>>t),acc[i+1]=acc[i]+t; auto f = [&n,&acc](const int x){ vector<int> dp(n+1,numeric_limits<signed>::max()); dp[0] = 0; for (int i(0);i < n;++i){ for (int k(i+1);k <= n;++k){ if (acc[k]-acc[i]<x) continue; if (i==0&&k==n) continue; dp[k] = min(dp[k],max(dp[i],acc[k]-acc[i])); } } return dp[n]; }; int r = f(0); for (int i(1);i < acc.back();++i) r = min(r,f(i)-i); cout << r << endl; }
提出結果
[JOI精進録] 難易度7「バームクーヘン」(第13回日本情報オリンピック 本選C)
問題リンク
問題概要
円状のものから3箇所切って3つに分けることを考える(切れる場所に制限がある)。
3つの内一番小さいものの大きさを最大化してください。
解説
AC解法 (100/100点)
最初に切る場所を全探索する。そして3つ全てが以上の大きさにできる最大の
を二分探索する。
判定関数は累積和を二分探索を使って前処理、計算
で求められる。
全体の計算量はである。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,t,ind(0); cin >> n; vector<int> dp(2*n+1),A(n); for (int& a:A) cin >> a; for (int i(0);i < 2*n;++i) dp[i+1]=dp[i]+A[i%n]; int x = 0; for (int i(0);i < n;++i){ t = x; x = max(x, (*lower_bound( views::iota(0ll,dp[n]).begin(), views::iota(0ll,dp[n]).end(), i, [&dp,&n](const int& x, const int& t){ if (dp[t]+x*3>dp[n+t]) return false; int y = *lower_bound(dp.begin(),dp.end(),x+dp[t]); if (y+x>dp[n+t]) return false; y = *lower_bound(dp.begin(),dp.end(),x+y); return (dp[n+t]-y<x?false:true); } ))-1); if (t!=x) ind = i; } cout << x << endl; }
提出結果
[JOI精進録] 難易度7「ゾンビ島」(第15回日本情報オリンピック 予選E)
問題リンク
問題概要
頂点
辺の無向グラフが与えられる。
そのうち個の頂点に訪れる事はできない。
また、それらの頂点から本以下の辺を通って移動できる頂点へ訪れるときは重み
がかかる。
それ以外の頂点へ訪れるときは重みがかかる。ただし頂点
に訪れるときに重みはかからない。
頂点1から出発し頂点を訪れるとき重みの総和の最小値を求めなさい。
解説
AC解法 (100/100点)
BFSを使って危険な街を列挙し、Dijkstra法を使って宿泊費の総和の最小値を求める。
またBFSをK頂点毎に行うのは重いため超頂点というテクニックを使って1回にまとめる。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,m,k,s; cin >> n >> m >> k >> s; int p,q,a,b; cin >> p >> q; vector<int> dist(n),res(n); queue<int> que; int t; for (int i(0);i < k;++i) (cin >> a),--a,dist[a]=1,que.emplace(a); vector<vector<int>> G(n); for (int i(0);i < m;++i) (cin>>a>>b),--a,--b,G[a].emplace_back(b),G[b].emplace_back(a); while(!que.empty()){ int t = que.front(); que.pop(); if (dist[t]==s+1) break; for (int a:G[t]){ if (dist[a]) continue; dist[a]=dist[t]+1,que.emplace(a); } } set<pair<int,int>> pque; pque.emplace(0,0),dist[n-1]=0; while(!pque.empty()){ auto [a,b] = *pque.begin(); pque.erase(pque.begin()); if (b==n-1) break; if (a!=res[b]) continue; for (int c:G[b]){ if (dist[c]==1) continue; int d = res[b]+(dist[c]?q:p); if (res[c]&&res[c]<=d) continue; res[c]=d,pque.emplace(d,c); } } cout << res[n-1]-p << endl; }
提出結果
[JOI精進録] 難易度7「JOI公園」(第14回日本情報オリンピック 本選C)
問題リンク
問題概要
個の広場がある。また、広場同士を結ぶ道路が
本ある。
広場1からの最短距離が以下の広場同士が結ばれている道路を削除する。コストを
残った道路の距離の総和として、
を適切に決めたときのコストの最小値を求めてください。
解説
AC解法 (100/100点)
DIjkstra法を使って広場1からの最短距離をすべて求める。広場1からの道の距離を結ばれている広場の最短距離の大きい方とする。
multisetを使って広場1からの道の距離と道路の距離を管理する。
このとき道路の距離の累積和を取ると、広場1からの道の距離を全探索することでで探索できる。
全体の計算量はとなります。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,m,c,r(numeric_limits<int>::max()); cin >> n >> m >> c; // Dijkstraで得たのをsortして逆から累積和すれば勝ち vector<tuple<int,int,int>> A(m); vector<vector<pair<int,int>>> G(n); for (auto& [a,b,c]:A) (cin >> a >> b >> c),--a,--b,G[a].emplace_back(b,c),G[b].emplace_back(a,c); vector<int> dist(n); set<pair<int,int>> que; que.emplace(1,0),dist[0]=1; while(!que.empty()){ auto [a,b] = *que.begin(); que.erase(que.begin()); if (a!=dist[b]) continue; for (auto [c,d]:G[b]){ if (dist[c]&&dist[c]<=dist[b]+d) continue; dist[c] = dist[b]+d,que.emplace(dist[c],c); } } multiset<pair<int,int>> ds; for (auto& [a,b,c]:A){ int d = max(dist[a]-1,dist[b]-1); ds.emplace(d,c); } vector<int> dp(m+2); auto rit = ds.rbegin(); for (int i(0);i < m;++i,++rit){ dp[m-i]=dp[m-i+1]+rit->second; } auto it = ds.begin(); for (int i(0);i < m;++i,++it) r=min(r,c*it->first+dp[i+2]); cout << min(r,dp[1]) << endl; }
提出結果
[JOI精進録] 難易度6「オレンジの出荷」(第15回日本情報オリンピック 本選A)
これ、だいぶ正しいんだけど、キャベツを厳密にAtCoderが管理しているわけではないから、「大半のキャベツは自分で勝手に畑から飛んで行って出荷されていく」ってのがAtCoderが儲けるのが難しい原因なのよねｗhttps://t.co/B7xM4FQQ5O
— chokudai(高橋 直大)@AtCoder社長 (@chokudai) December 1, 2020
キャベツだったら多分笑い転げてた。2016年の問題なのでキャベツとは全く関係ない。
問題リンク
問題概要
オレンジを全ていくつかの箱に詰め込む。箱に詰め込まれるオレンジは連続していなければならない。
costは箱の固定コスト、詰め込む個数
、詰め込むオレンジの最大値
と最小値
で
と表される。
costの総和の最小値を求めなさい。
解説
AC解法 (100/100点)
個前のオレンジまで詰め込んだときのcostの総和の最小値
としてRMQを使ってを更新していく。
高速に更新するためにmodとか使ってるので詳しい説明は後になってはもうできない。だがACしているのでﾖｼ｡
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,m,k; cin >> n >> m >> k; vector<int> A(n),dp(m+1,0); for (int& a:A) cin >> a; vector<int> rminq(m+1),rmaxq = rminq; fill(rminq.begin()+1,rminq.end(),A[0]),fill(rmaxq.begin()+1,rmaxq.end(),A[0]); // dp[i] = i個前まで詰めたときの最小値 dp[0] = k; for (int i(1);i < n;++i){ for (int j(m);j > 1;--j) rminq[j] = min(rminq[j-1],A[i]),rmaxq[j] = max(rmaxq[j-1],A[i]); rminq[1] = A[i],rmaxq[1] = A[i]; int b = -i; b%=m+1; while (b<0) b = m+1+b; dp[b] = dp[(b+1)%(m+1)]+k; for (int j(0);j <= min(m-1,i);++j){ int c = b+j+1; c%=m+1; dp[b]=min(dp[b],(j==i?0:dp[c])+k+(j+1)*(rmaxq[j+1]-rminq[j+1])); } if (i<m&&dp[i]==0) dp[i] = k; } int b = -(n-1); b%=m+1; while (b<0) b = m+1+b; cout << dp[b] << endl; }
提出結果
[JOI精進録] 難易度7「イルミネーション」(JOI2018/2019 予選E)
JOIにイルミネーションなんか2つある
問題リンク
問題概要
イルミネーションをいくつかつける。美しさの総和の最大値を求めなさい。
ただし指定されている個指定されている区間内には各1つまでしか飾り付けることができない。
解説
AC解法 (100/100点)
イルミネーションを
まで飾り付ける、つけないを決めたときの美しさの総和
として、更新していく。区間はmultisetで管理して、最小値から取得する場所を決定する。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ #define int long long int n,m; cin >> n >> m; vector<int> A(n),dp(n+1); for (int &a:A) cin >> a; vector<pair<int,int>> Add(m); multiset<pair<int,int>> Sub; multiset<int> Notwo; for (auto& [a,b]:Add) (cin >> a >> b),Sub.emplace(b,a); sort(Add.begin(), Add.end()); int k(0); for (int i(0);i < n;++i){ while(k<m&&Add[k].first<i+2) Notwo.emplace(Add[k].first),++k; dp[i+1] = max(dp[max((*Notwo.begin())-1,0ll)]+A[i],dp[i]+(Notwo.empty()?A[i]:0)); while(!Sub.empty()&&Sub.begin()->first<i+2) Notwo.erase(Notwo.find(Sub.begin()->second)),Sub.erase(Sub.begin()); } cout << dp[n] << endl; }
提出結果
[JOI精進録] 難易度7「パンケーキ」(JOI2020/2021 二次予選B)
悪名高いやつ
2105ms/2500msなので想定解法じゃないかも
問題リンク
問題概要
よいパンケーキ文字列を以下で定義する。
・A、B、Cからなる文字列で、ASCIIコードで昇順にsortしたものと一致する (例「ABC」「AAAB」「CCCC」)
沢山のクエリが与えられる。クエリは
・文字列が与えられる。先頭から文字分ひっくり返す操作を最小何回行うことで一致させられるか
である。
解説
AC解法 (100/100点)
がちっちゃい。そしてよいパンケーキ文字列は高々
パターンである。全列挙できそうだ。
ということでBFSを終点から行い、始点を入力すればクエリに高速に答えることができる。
unordered_mapじゃないと通らなかった。
ACコード
#include <bits/stdc++.h> using namespace std; int main(){ int n,q; cin >> n >> q; unordered_map<string,int> M; for (int i(0);i <= n;++i) for (int k(i);k <= n;++k) { string s; for (int l(0);l < i;++l) s+="A"; for (int l(i);l < k;++l) s+="B"; for (int l(k);l < n;++l) s+="C"; queue<string> que; que.emplace(s); while(!que.empty()){ auto& a = que.front(); int d = M[a]; for (int l(2);l <= n;++l){ reverse(a.begin(),a.begin()+l); if (M[a]==0) M[a] = d+1,que.emplace(a); reverse(a.begin(),a.begin()+l); } que.pop(); } } string s; while(q--){ cin >> s; if (M[s]<=2&&is_sorted(s.begin(),s.end())) cout << 0 << '\n'; else cout << M[s] << '\n'; } cout.flush(); }
sort済みかを判定するプログラムが余計についてる。距離を+1してクエリに-1して答えればよかったが忘れてた
とは書いたが試したらの+1はきついらしくTLEした。
