ABC164反省会Dまで

類題探しに行ってABC158Eを見つけたのに、「うーん、これはなんか違う気がするw」になってよく読まなかったバカーーー誕生。

それはそうと問題間に難易度の差がすっごい。。。。

個人的には

A - diff 0

B - diff 400

C - diff 800

D - diff 1200

みたいな旧ABC+αみたいな感じにしてほしい気持ち・・・

A

日本語の誤読に気をつけよう!

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int S,W;
    cin >> S >> W;
    auto ans = (W >= S) ? "unsafe" : "safe";
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

B

実装ゲーだと思います。こういうのキレイに実装出来るようになりたい。

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
 
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"
 
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
 
void solve() {
    int t_hp,t_atk,a_hp,a_atk;
    cin >> t_hp >> t_atk >> a_hp >> a_atk;
    bool is_t_tern = true;
    while (true) {
        if ((t_hp) <= 0 || (a_hp)<= 0) {
            cout << ((a_hp <= 0 )? "Yes" : "No") << endl;
            return;
        }
        ((is_t_tern) ? a_hp : t_hp) -= ((is_t_tern) ? t_atk : a_atk);
        is_t_tern = !is_t_tern;
    }
}
 
int main() {
    solve();
    return 0;
}

C

Sを全てsetに打ち込んでやりましょう。後はsizeを見れば良いです。

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
 
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"
 
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
 
void solve() {
    int N;
    cin >> N;
    set<string> s;
    REP(i,N) {
        string S;
        cin >> S;
        s.insert(S);
    }
 
    cout << s.size() << endl;
}
 
int main() {
    solve();
    return 0;
}

D

ABC158Eの復習記事を書きましたよね?

【Eまで】ABC158を振り返る。 - 散文的ゴミ箱

2つの解法が考えられます。

DPで解く

最大計算量$4*10^8$で二次元DPをする解法です。

@50j1_さんに教えていただきました!ありがとうございます。

遷移式は

左からi文字目に対して余りがjになる場合の数dp[i][j]において、

$$ p[i+1][j*10+S[i]-‘0’ mod 2019] = dp[i][j] $$

が成立します。よく考えると、i,i+1だけ遷移式に絡むのでdp[S.size()][2019]でメモリ確保する必要は無いのです。 今と前の文字の情報だけメモリ確保するような実装にしましょう。

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
 
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"
 
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
 
void solve() {
    string S;
    cin >> S;
    int ans = 0;
   vector<int> ntm(2019,0);
   for(const auto c: S){
       vector<int> stm(2019,0);
       REP(j,2019) stm[(j*10 + (c-'0'))%2019]+=ntm[j];
       stm[c-'0']++;
       ans+=stm[0];
       ntm = stm;
   }
   cout << ans << endl;
}
 
int main() {
    solve();
    return 0;
}

イメージはこんな感じ

image

もう一個の解法

TODO

Share on: