類題探しに行ってABC158Eを見つけたのに、「うーん、これはなんか違う気がするw」になってよく読まなかったバカーーー誕生。
それはそうと問題間に難易度の差がすっごい。。。。
個人的には
A - diff 0
B - diff 400
C - diff 800
D - diff 1200
みたいな旧ABC+αみたいな感じにしてほしい気持ち・・・
A
日本語の誤読に気をつけよう！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#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
実装ゲーだと思います。こういうのキレイに実装出来るようになりたい。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#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を見れば良いです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#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]でメモリ確保する必要は無いのです。
今と前の文字の情報だけメモリ確保するような実装にしましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#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;
}
|
イメージはこんな感じ
もう一個の解法
TODO