結果
| 問題 |
No.2673 A present from B
|
| コンテスト | |
| ユーザー |
 Astral__
|
| 提出日時 | 2024-03-15 22:20:22 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 217 ms / 2,000 ms |
| コード長 | 10,527 bytes |
| コンパイル時間 | 2,716 ms |
| コンパイル使用メモリ | 254,444 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-09-30 01:42:47 |
| 合計ジャッジ時間 | 4,745 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//using uLL = unsigned __int128;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using pq = priority_queue<T>;
using pll = pair<long long, long long>;
using pii = pair<int, int>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvc = vector<vector<vector<char>>>;
using vvvd = vector<vector<vector<double>>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<pair<ll, ll>>>;
using vvb = vector<vector<bool>>;
using vvd = vector<vector<double>>;
using vp = vector<pair<ll, ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vu = vector<unsigned long long>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
#define vvvm vector<vector<vector<mint>>>
#define vvm vector<vector<mint>>
#define vm vector<mint>
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;
template <typename T1, typename T2>
using uset = unordered_set<T1, T2>;
#define rrr(l, r) mt()%(r-l+1)+l
#define rep(i, s, f) for(long long i = s; i <= f; i++)
#define rep1(i, s, f) for(long long i = s; i <= f; i++)
#define per(i, s, f) for(long long i = s; i >= f; i--)
#define per1(i, s, f) for(long long i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define ENDL '\n'
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//これが本当の組み込み関数ってね（笑）
template <typename T>
int LB(vector<T> &A, T x) {
return lower_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
int UB(vector<T> &A, T x) {
return upper_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
void UNIQUE(vector<T> &A, int indexed) {
sort(A.begin() + indexed, A.end());
A.erase(unique(A.begin() + indexed, A.end()), A.end());
}
int msb(long long a) {
if(a == 0) return -1;
return 64 - int(__builtin_clzll(a));
}
template<typename T = long long>
void chmin(T &a, T b) {
a = min(a, b);
}
template<typename T = long long>
void chmax(T &a, T b) {
a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//数学系
///////////////////////////////////////////////////////////////////////
ll extgcd (ll a, ll b, ll &x, ll &y) {
if(b == 0) { x = 1;y = 0;return a;}
ll d = extgcd(b, a%b, y, x);
y -= a/b * x;
return d;
}
template <typename T>
T ceil__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
else return a / b;
}
template <typename T>
T floor__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
else return a/b - 1;
}
ll modpow(ll x, ll y, ll mod) {
if(x > mod) x %= mod;
if(y == 0) return 1;
ll res = modpow(x, y >> 1, mod);
res = res * res % mod;
if(y & 1) res *= x, res %= mod;
return res;
}
ll sqrt__(ll a) {
ll l = 0;
ll r = 3037000499LL;
while(l < r) {
ll mid = (l + r + 1) / 2;
if(mid * mid <= a) l = mid;
else r = mid - 1;
}
return l;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//グローバル変数を置くところ
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize "trapv" //お祈り。変数同士の演算でのみ感知。代入や、 a *= 10000 では感知しない。
const ll big = 1001001001;
const ll BIG = 1001001001001001001LL;
const double pi = 3.141592653589793;
vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // 座標平面において、(番兵) → ↓ ← ↑ ※ 右から時計回り 注 : グリッド or 座標で上下は反転する。
vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};
//const ll mod = 1000000007;
//const ll mod = 998244353;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T>
struct SegTree {
int n;
vector<T> dat;
SegTree(int siz) {
n = 1;
while(n < siz) n <<= 1;
dat.resize(n * 2, T::ide());
}
private:
T query(int l, int r) {
T L = T::ide(), R = T::ide();
l += n - 1, r += n - 1;
while(l < r) {
if(l & 1) L = op(L, dat[l++]);
if(r & 1) R = op(dat[--r], R);
l >>= 1, r >>= 1;
}
return op(L, R);
}
public:
void set(int pos, T x) {
pos += n-1;
dat[pos] = x;
}
void init() {
for(int i = n-1; i >= 1; i--) dat[i] = op(dat[i<<1], dat[(i<<1) + 1]);
}
void change(int pos, T x) {
pos += n - 1;
dat[pos] = update(dat[pos], x);
while(pos >= 2) {
pos >>= 1;
dat[pos] = op(dat[pos<<1], dat[pos<<1|1]);
}
}
T get(int l, int r) {// [l, r]の演算結果。
return query(l, r+1);
}
T operator[](int pos) {
return dat[pos + n - 1];
}
};
struct Monoid {
int a;
Monoid(){}
Monoid(int _a) : a(_a) {
}
friend Monoid op(const Monoid& l, const Monoid& r) {
return min(l.a, r.a);
}
friend Monoid update(const Monoid& l, const Monoid& r) {
return r.a;
}
static Monoid ide() {
return big;
}
};
void solve() {
int N, M;
cin >> N >> M;
vi A(M+2);
rep(i,1,M) cin >> A[i];
A[M+1] = big;
/*
SegTree<Monoid> seg1(N);
SegTree<Monoid> seg2(N);
vi dp(N+1, big);
dp[1] = 0;
seg1.change(ti, -ti);// dp[i][j] - j
seg2.change(ti, ti);// dp[i][j] + j*/
vi dp(N+1, big);
dp[1] = 0;
per(i, M, 1) {
vi pre(N+1, big);
swap(pre, dp);
rep(j, 1, N) {
rep(pj, 1, N) {
int c = abs(pj - j);
if(j < pj && j <= A[i] && A[i] < pj)c--;
else if(pj < j && pj <= A[i] && A[i] < j)c--;
else if(pj == j && (A[i] == pj || A[i] == pj-1))c++;
chmin<int>(dp[pj], pre[j] + c);
}
}
}
rep(ti, 2, N) {
int res = big;
rep(j, 1, N) {
chmin<int>(res, dp[j] + abs(ti - j));
}
cout<< res << " ";
}
cout << ENDL;
return;
rep(ti, 2, N) {
SegTree<Monoid> seg1(N);
SegTree<Monoid> seg2(N);
vi dp(N+1, big);
dp[ti] = 0;
seg1.change(ti, -ti);// dp[i][j] - j
seg2.change(ti, ti);// dp[i][j] + j
rep(i, 1, M+1) {
vi pre(N+1, big);
swap(pre, dp);
rep(j, 1, N) {
int tar = j;
if(A[i] == j) tar = j+1;
else if(A[i] == j-1) tar = j-1;
{//pj = [1, tar]
chmin<int>(dp[j], seg1.get(1, tar).a + tar);
}
{//pj = [tar+1, N]
chmin<int>(dp[j], seg2.get(tar+1, N).a-tar);
}
}
rep(j, 1, N) if(dp[j] != big) {
seg1.set(j, dp[j] - j);
seg2.set(j, dp[j] + j);
}
seg1.init();
seg2.init();
}
cout << dp[1] << " ";
}
cout << ENDL;
}
/*
-違法な読み替えをしていないか・違法な操作をしていないか
・実装が重そうな時は確認する 一度飛ばしても良い
・waが出た時は嘘を吐いていないかの他に、違法な操作をしていないかもチェックする
特にふわっとした操作は危ない
・区間をちょっと伸ばす←伸ばす余地はあるか
・選択肢のうち、どれでも良いから消す←本当にどれでも良いか 場合分けを挟んでないか
-その情報はdpで纏めて良いものか
・dpで持つ：「この先の探索をするのに必要な情報」 なぜ必要なのか？
・途中までは辻褄が合っても、最後に分岐とかはある
-何もわからないという時
・解を列挙した上で特徴づけ
・制約に具体的な数値が登場している←適当に解をいじると何となく性質が見えることが多い
・何もわからない（自由度が高い) という時
-解の形を貪欲で絞る
-上階が達成できガチ 必要条件をつみかさねていく ”非自明な最悪ケース（例：点の数が多いのに答え=0)”を作る時、何を意識したか？
・要素と制約をグラフで表してみる
・制約を「全ての要素についてoo ⇔ (1<=i<=N)で、iについてoo」といったように、独立なものに言い換えた方がやりやすいこともある
・よくわからないものを言い換える。
-慣れ親しんだ制約も、問題設定によってより扱いやすい形に言い換えられるかもしれない（例：グラフが連結)
-一つの解法で駄目な時、周辺の解法も試すようにする。周辺で見えないなら全部試す。
・「貪欲で最適解」と「解の形を絞って全探索」
・「dp/最適化」と「解の形を絞って全探索」と 上界を見積もる」
・「dp」と「必要な情報を言い換える・何でのその情報が必要なのか考える事による高速化」
・「dp」と「探索の順番を変更する: でかい方から、深い方から、DAGで先端になっている・或いは葉になっている所から、全てを逆に言い換えて時系列的に後ろから」
・「dp」と「軸にするものを変える: マスを軸にするのではなく、燃料を軸にするなど」
*/
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
ll T = 1;
//cin >> T;
rep(i, 1, T) {
solve();
}
return 0;
}