ARC級の企業コン
配点出て2完早解き勝負になると言われてたけどそのとおりになったね
Aで誤読して無事敗北しました(ア
失敗に優しいAtCoder
— ボンド@競プロ (@bond_cmprog) 2020年3月8日
Bondo416さんの日立製作所 社会システム事業部 プログラミングコンテスト2020での成績:1369位
パフォーマンス:1196相当
レーティング:1322→1310 (-12) :(#AtCoder https://t.co/6W4hks1gBs
A - Hitachi String
hiが連続してできている文字列ならおっけー
判定方法は色々ありそうだけど愚直に見ていった
最初hiが含まれてたらいいと思って1WA(これでパフォ400近く変わるからひえ〜)
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; string ans = "Yes"; for(int i=0;i<(int)S.size()-1;i+=2){ if(!(S[i] == 'h' && S[i+1] == 'i')) ans = "No"; } if((int)S.size() % 2 != 0) ans = "No"; cout << ans << endl; }
B - Nice Shopping
読解がちょっとしんどいけど言われたとおりにやる
冷蔵庫と電子レンジの最小の和を持っておいて、クーポンを使ったものが安くなればそれに更新する
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int A, B, M; cin >> A >> B >> M; vector<int> a(A), b(B); vector<int> x(M), y(M), c(M); int mi_a = INF, mi_b = INF; REP(i,A){ cin >> a[i]; chmin(mi_a, a[i]); } REP(i,B){ cin >> b[i]; chmin(mi_b, b[i]); } REP(i,M){ cin >> x[i] >> y[i] >> c[i]; --x[i], --y[i]; } int ans = mi_a + mi_b; REP(i,M){ int tmp = a[x[i]] + b[y[i]] - c[i]; chmin(ans, tmp); } cout << ans << endl; }
C - ThREE
これ解けなかったけど好き
こういうのは絶対作れるパターンだなーって思ってたけど詰めきれず…
根を固定して、各頂点までの距離 mod 3で分けてできないかなーってやってパスの時作れないなーってなって終わった
実は二部グラフで考えると異なる色同士でしか距離が3のものは作れない
後は解説通りなので割愛しますが、条件を満たすように使っていない数字を割り振っていくとAC
提出コード
int color[202020]; vector<vector<int>> G; int even = 0, odd = 0; void dfs(int v, int par, int d){ if(color[v] == -1){ color[v] = d; if(d & 1) odd++; else even++; } for(auto nv : G[v]){ if(nv == par) continue; dfs(nv, v, d^1); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; G.resize(N); REP(i,N-1){ int a, b; cin >> a >> b; --a, --b; G[a].push_back(b); G[b].push_back(a); } memset(color, -1, sizeof(color)); color[0] = 0; even++; dfs(0, -1, 0); vector<int> num[3]; for(int i=1;i<=N;i++){ num[i%3].push_back(i); } vector<int> ans(N); if(N/3 < odd && N/3 < even){ REP(i,N){ if(!num[color[i]+1].empty()){ ans[i] = num[color[i]+1].back(); num[color[i]+1].pop_back(); } else{ ans[i] = num[0].back(); num[0].pop_back(); } } } else if(N / 3 >= odd){ REP(i,N){ if(color[i]){ ans[i] = num[0].back(); num[0].pop_back(); } else{ if(!num[2].empty()){ ans[i] = num[2].back(); num[2].pop_back(); } else if(!num[1].empty()){ ans[i] = num[1].back(); num[1].pop_back(); } else{ ans[i] = num[0].back(); num[0].pop_back(); } } } } else{ REP(i,N){ if(!color[i]){ ans[i] = num[0].back(); num[0].pop_back(); } else{ if(!num[2].empty()){ ans[i] = num[2].back(); num[2].pop_back(); } else if(!num[1].empty()){ ans[i] = num[1].back(); num[1].pop_back(); } else{ ans[i] = num[0].back(); num[0].pop_back(); } } } } REP(i,N) cout << ans[i] << " "; cout << endl; }
おわりに
AtCoderの早解きコンテスト失敗しがち
失敗して-12なので気にせずABCでレート上げていこうね
二部グラフ忘れがちなのでちゃんと考えよう