5完11ペナ(!?)でパフォ1483でした
新ABCになってから初5完ですが反省も多かった…
A - Tenki
各文字が一致しているかどうか見ればいいですね
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; string T; cin >> S >> T; cout << (S[0] == T[0]) + (S[1] == T[1]) + (S[2] == T[2]) << endl; }
B - Power Socket
A〜Dまでで一番難しくないですか(問題文ちゃんと読もうね)
愚直にシミュレートでも数式立てても解けますがB=1のときに注意
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int A, B; cin >> A >> B; if(B == 1){ cout << 0 << endl; return 0; } int cnt = 1; int tap = A; if(tap >= B){ cout << 1 << endl; return 0; } while(tap < B){ tap += A-1; cnt++; } cout << cnt << endl; }
C - Lower
前から見て愚直にやるとになりそう
逆に後ろから見ると一意に決まりそうなので後ろから見ました
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<int> a(n); REP(i,n) cin >> a[i]; reverse(a.begin(),a.end()); a.push_back(0); int cnt = 0, ans = 0; REP(i,n){ if(a[i] <= a[i+1]) cnt++; else chmax(ans,cnt), cnt = 0; } cout << ans << endl; }
D - ModSum
競プロに慣れてる人はサンプルからエスパーできそう
エスパーすると1~N-1までの総和になりそう
一応ちゃんと証明すると
N,1,2,…のように数列を並べていくとそのmodを取った数列は
0,1,2,...,N-1になりそれが最大になるのでこれが答え
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; cout << N * (N-1) / 2 << endl; }
E - League
ごめんなさいテストケースエスパーしました
愚直にシミュレートするとになる
キューなどを上手く使うとになるみたいです
もしくは各試合を頂点とみなしDAGとして扱うとで解けるみたいですね(閉路があった時-1)
ぼくの場合愚直にシミュレートすると1ケースだけTLE
→最大ケースは1日に1試合しか行われない(N*(N-1)/2)
→でTLEしているので最大ケースしかなさそう?
→時間計算をしてTLEしそうなら最大ケース出力するとAC(ごめんなさい)
N=1000のとき最大ケース以外でTLEするケースあるんですかね?
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<vector<int>> player(N,vector<int>(N)); REP(i,N) REP(j,N-1){ cin >> player[i][j]; player[i][j]--; } int ans = 0; vector<int> cnt(N); int sum = 0; int step = 0; while(sum < N*(N-1)){ ans++; int tmp = sum; vector<bool> done(N); REP(i,N){ step++; if(cnt[i] > ans) continue; if(cnt[i] >= N-1) continue; int outside = player[i][cnt[i]]; if(cnt[outside] < ans){ if(i == player[outside][cnt[outside]] && !done[i] && !done[outside]){ cnt[i]++; cnt[outside]++; done[i] = true; done[outside] = true; sum += 2; } } else continue; } if(sum == tmp){ cout << -1 << endl; return 0; } if(sum >= N*(N-1)) break; if(step >= 1e8){ cout << N*(N-1)/2 << endl; return 0; } } cout << ans << endl; }
おわりに
今回はBでペナ出したり,Eで計算量削減出来ずにエスパーしたりと反省が多い回でした
とりあえずEは想定解でACし直したいですね
ところで今回はAのAC数が5,800超えてて大分参加者が増えたなあという印象です
DのAC数も4,000近く居て人類競プロ強くないかというお気持ち
今回のDは証明まで含めたら400でも良さそうだけどこんなに解ける?というお気持ちです
水になるにはやっぱりEの打率上げるのが一番の近道かな?