5完で水パフォでした。青パフォstreakが切れて悲しいですね。
jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績:864位
— naga@精進 (@longeqe) 2020年9月14日
パフォーマンス:1597相当
レーティング:1412→1432 (+20) :)
Highestを更新しました!#AtCoder #ABC178 https://t.co/JlM3ZncqvH
A - Not
解説
1とのxorを取ると逆転します。
実装
int main() { int x; cin >> x; cout << x^1 << endl; }
B - Product Max
解説
こういう問題最近よく見ます。大抵区間の端のみを見ればよいです。
実装
int main() { ll a, b; ll c, d; cin >> a >> b; cin >> c >> d; ll ans = -INFLL; chmax(ans, a * c); chmax(ans, a * d); chmax(ans, b * c); chmax(ans, b * d); if(a <= 0 && 0 <= b)chmax(ans, 0LL); if(c <= 0 && 0 <= d)chmax(ans, 0LL); cout << ans << endl; }
C - Ubiquity
解説
dp[どこまで見たか][0が出たか][9が出たか]
でdpします。
実装
mint dp[1000100][2][2]; int main() { int N; cin >> N; rep(i,N+1)rep(j,2)rep(k,2)dp[i][j][k] = 0; dp[0][0][0] = 1; rep(i,N){ rep(j,2)rep(k,2){ for(int nxt = 0; nxt <= 9; nxt++){ dp[i+1][j || nxt == 0][k || nxt == 9] += dp[i][j][k]; } } } cout << dp[N][1][1] << endl; }
D - Redistribution
解説
のdpしか見えなくて雑に枝刈りしたら通りました。許してください。
実装
mint dp[2500][2500]; int main() { ll S; cin >> S; rep(i,2222)rep(j,2222)dp[i][j] = 0; dp[0][0] = 1; rep(i,2221)rep(j,S){ if(dp[i][j].x == 0)continue; for(int add = 3; add + j <= S; add++){ dp[i+1][add + j] += dp[i][j]; } } mint ans = 0; rep(i,2222)ans += dp[i][S]; cout << ans << endl; }
E - Dist Max
解説
既出っぽいし典型っぽいので「マンハッタン距離 最大」とかでググると色々ヒットします。 マンハッタン距離なら45°回転は典型っぽいので、抑えておきたいところです。
実装
int main() { int N; cin >> N; vector<ll> v, w; rep(i,N){ int x, y; cin >> x >> y; v.emplace_back(x-y); w.emplace_back(x+y); } sort(all(v)); sort(all(w)); ll maxx = 0; chmax(maxx, v.back() - v[0]); chmax(maxx, w.back() - w[0]); cout << maxx << endl; }
F - Contrast
解説
ある数がとに渡って個以上あるとき、不可能で、それ以外は可能です。 構築は難しいですが、をreverseすると重なるのは一つだけなので、そこを雑に調整すると良さそうです。
実装
int main() { int N; cin >> N; vector<int> A(N), B(N); cin >> A >> B; map<int, int> mpa, mpb; rep(i,N){ mpa[A[i]]++; mpb[B[i]]++; } for(int i = 1; i <= N; i++){ ll cnta = mpa[i]; ll cntb = mpb[i]; if(cnta + cntb > N){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; reverse(all(B)); int idx = 0; rep(i,N){ if(A[i] == B[i]){ while(B[idx] == B[i] || A[idx] == B[i]){ idx++; idx %= N; } swap(B[i], B[idx]); } } rep(i,N){ cout << B[i] << " "; } cout << endl; }