ABC212参戦記
はじめに
7月31日21:00-22:40ABC212に参戦しました。
結果は81:59 ABCD4完2425位/7893人中でパフォーマンス934レーティングは前回875から+6の881となりました。
ABC8問制の初回で難易度傾斜が弱くなるとの触れ込みでしたがE以降はとても難しく難問が増えただけのような印象でした。
もっともDまででも楽しいセットだったと思います。
A問題
金と銀の量が示され混ぜ合わせたものが純金か純銀か合金かを判別する問題です。
B問題
数字4桁のパスワードの強度を判別する問題。
４つとも同じ数字か順番に１づつ大きくなる（9の次は0）場合に弱いパスワードになります。
stringで入力して処理。
提出コード
#include <bits/stdc++.h> using namespace std; signed main(){ string s; cin>>s; if(s[0]==s[1] && s[1]==s[2] && s[2]==s[3]){ cout<<"Weak"<<endl; return 0; } if((s[1]==s[0]+1 ||(s[1]=='0' && s[0]=='9'))&& (s[2]==s[1]+1 ||(s[2]=='0' && s[1]=='9'))&& (s[3]==s[2]+1 ||(s[3]=='0' && s[2]=='9'))){ cout<<"Weak"<<endl; return 0; } cout<<"Strong"<<endl; return 0; }
Ｃ問題
C - Min Difference
数列Aと数列Bから要素を１こづつ選んだときの差の最小値を求める問題です。
片方ソートしておいて二分探索が頭をよぎりましたが尺取りみたいなやり方の方がまぎれが少なそうです。
両方ソートしておいて，インデックスを動かしながら差の最小値を求めました。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) signed main(){ int n,m; cin>>n>>m; vector<int> a(n,0); vector<int> b(m,0); rep(i,n) cin>>a[i]; rep(i,m) cin>>b[i]; sort(a.begin(),a.end()); sort(b.begin(),b.end()); int aind=0; int bind=0; int mindif=1000000000; while(aind<n && bind<m){ int dif=abs(a[aind]-b[bind]); mindif=min(mindif,dif); if(aind==n-1) bind++; else if(bind==m-1) aind++; else if(abs(a[aind+1]-b[bind])>=abs(a[aind]-b[bind+1])){ bind++; } else{ aind++; } } cout<<mindif<<endl; return 0; }
Ｄ問題
D - Querying Multiset
①要素の追加、②集合全部に加算、③最小の値を出力して削除、という３つのクエリ―を処理する問題です。
ヒープ（priority_queue)を使った実装をすぐ思いつき、②について要素とは別に累積の加算量を準備し③の出力の際に足す工夫をしました。ところがサンプルは通りましたが提出するとWAです。
途中で追加された要素について、②の値がずれてくるのが問題だと気づきましたが、なかなか解決策を思いつきませんでした。血迷って愚直解を書いてみましたが当然ながらＴＬＥ。自作のサンプルを書き出していろいろいじっているうちに、要素を追加する際にそこまでの累積の加算量を引いてやればよい、と気づいて「解けた！」となりました。提出コードはめちゃめちゃシンプルです。
提出コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define int long long signed main(){ int q; cin>>q; priority_queue<int, vector<int>, greater<int> > que; int base=0; while(q--){ int t,x; cin>>t; if(t != 3) cin>>x; if(t==1) que.push(x-base); if(t==2) base+=x; if(t==3){ cout<<que.top()+base<<endl; que.pop(); } } return 0; }
ABC209参戦記
はじめに
2021年7月10日21:00-22:40に開催されたABC209に参戦しました。
結果は44:09 ABCD4完ノーペナでパフォーマンス1106 レーティングは前回835から+30の865になりました。
前回まで5回連続で冷えていたので久しぶりのレートアップです。
A問題
A - Counting
A以上B以下の整数を出力する問題です。
BがＡより小さい場合に注意して解きました。
1分15秒
Ｂ問題
B - Can you buy them all?
N個の商品をK円で全部買えますかという問題です。
偶数個が１円引きということで添え字と偶奇がずれることに注意します。
Ａ問題もＢ問題も簡単な問題でした。時間もまあまあ。
2分38秒、通算3分53秒
C問題
C - Not Equal
難しかったです。
最初５分ほど考えて解法を思いつかず、先にDを解いて戻ってきました。
落ち着いて考えるとソートしても結果は同じことに気づき昇順でソートして積を取ればよいことに気づきました。
0になるパターンに注意して実装しました。
トータルで12分ぐらいかかった感じ。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) static const ll mod=1000000007; int main() { int n; cin>>n; vector<int>a(n); rep(i,n){ cin>>a[i]; } sort(a.begin(),a.end()); ll ans=1; rep(i,n){ if(a[i]<i+1){ cout<<0<<endl; return 0; } ans*=(a[i]-i); ans%=mod; } cout<<ans<<endl; return 0; }
D問題
D - Collision
グラフ問題です。
二部グラフになっているのでBFSで頂点の塗り分けをして同じ色の頂点か異なる色の頂点かで判別する方針で解きました。
BFSもだいぶ慣れてきて塗分けなどの作業もうまくできました。３から引いて１か２にするのがいい感じ。
デクリメントする場所を間違えていたのに気づかずバグとりに手間取り25分ぐらいかかりましたが解けてよかったです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) int main() { int n,q; cin>>n>>q; vector<int>to[n]; rep(i,n-1){ int a,b; cin>>a>>b; a--;b--; to[a].push_back(b); to[b].push_back(a); } vector<int>dist(n,-1); queue<int>que; dist[0]=1; que.push(0); while(!que.empty()){ int v=que.front(); que.pop(); for(auto nv:to[v]){ if(dist[nv] != -1) continue; dist[nv]=3-dist[v]; que.push(nv); } } //rep(i,n) cout<<dist[i]<<endl; rep(i,q){ int c,d; cin>>c>>d; c--; d--; if(dist[c]==dist[d]) cout<<"Town"<<endl; else cout<<"Road"<<endl; } return 0; }
E問題
一見して手に負えそうにない感じでしたが，時間一杯取り組みました。
グラフに落とすところまでやった。
あとは解説見て勉強します。
int main(){
int n;
cin>>n;
string s[n];
rep(i,n) cin>>s[i];
vector<int>to[n];
rep(i,n) rep(j,n){
int ilen=s[i].length();
if(s[i].substr(ilen-3,3)==s[j].substr(0,3)){
to[i].push_back(j);
}
}
終わりに
単調減少は脱出しましたが長期停滞が続いています。
まあ自己評価的にはプログラミングに慣れてきて細かいところが充実してきてるので，同じ緑低位でも安定感はでてきてはいるのですが，そろそろ上を目指したいところです。
水色を目指して４つのことを進めていきます。
・ 基礎知識の涵養 数学・アルゴリズムなどの知識を継続して学び続けます。
・ ABC復習 過去に出たコンテストをバチャで解きなおして知ってる技術を使える技術に昇華します。
・ 環境整備 ライブラリの整備も含めて勝つための環境を整えます。
近況
- ABCはなかなか結果がでず、単調減少を続けてMAXから100ぐらい下がってますが何とか緑を維持。
- オイラー路による部分木判定をする問題を検討しました。
- atcoderライブラリ、じっくり腰を据えて使えるようになるといいなと思う機会がありました。キューに入れておきます。
- 使いこなせる技術を増やしたい。知っているところから使いこなせるところまでの距離がなかなか埋まりません。
いちいち参照して学びなおす時間を省けると当然ですがぐっとスピードアップできそうです。
- 復習重視の大切さを感じています。ABC過去回のバチャも進めていきたい。
先日ABC151にトライしてみました。
初めてratedになったABCで当時の成績は11:14 AB2完でパフォーマンスは315。
先日トライしたバチャではABCD4完78:05 2ペナで推定パフォは1051。
Dも相当苦労しEは解ききれずFには手が出ませんでした。
ABC203参戦記
はじめに
2021年5月30日21:00-22:40に開催されたABC203に参戦しました。
結果は12:43 ３完ノーペナで1595位／8432人中 パフォーマンス1213でレーティングは前回861から+41の902になりました。
A問題
ちんちろりんとはなんとも昔懐かしいサイコロ賭博です。
３つのサイコロをふって２つが同じ目のとき残りの１つのサイコロの目が得点になるのが基本です。
「目」といいます。
バラバラだとクズといって０点ですね。
実際のルールはもう少し複雑で３つとも目が揃うとアラシ､１，２，３がでるとヒフミといって無条件の負け，４，５，６はシゴロといって無条件の勝ちで掛け金の２倍がもらえたりします。
素直に実装して丁寧にサンプルを試して2:13。まあまあ。
提出コード
#include <bits/stdc++.h> using namespace std; signed main(){ int a,b,c; cin>>a>>b>>c; if(a == b){ cout<<c<<endl; return 0; } if(c == b){ cout<<a<<endl; return 0; } if(a == c){ cout<<b<<endl; return 0; } cout<<0<<endl; return 0; }
B問題
部屋番号を３桁の整数と見なして足し合わせる問題。
i,jが9までなので，素直に実装してよさそうです。
サンプル確認して提出。
2分14秒 通算4分27秒は快調。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) signed main(){ int n,k; cin>>n>>k; int ans=0; rep(i,n) rep(j,k){ ans+=(i+1)*100+j+1; } cout<<ans<<endl; return 0; }
C問題
貪欲に手持ちのお金で次の村までたどり着けるか，たどり着けたらBiを手持ちのお金に足す，という方針でよさそうです。
最初に書いたコードは，村のソートを忘れており，入力例３が合わなくて気づきました。
親切なサンプルがあってよかった。
ソートを書き加えてAC。
8分16秒 通算12分43秒はまずまずです。
ノーペナで比較的スムーズに３完できたのが幸いで，エスティメーター見ると水パフォが出てました。
もっとも，このあたりまで好調でも後半にずるずる落ちてくのが常なので，気を引き締めて先に進みました。
提出コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define int long long signed main(){ ll n,k; cin>>n>>k; vector<pair<ll,ll>> ab; ll a[n]; ll b[n]; rep(i,n){ cin>>a[i]>>b[i]; ab.push_back(make_pair(a[i],b[i])); } sort(ab.begin(),ab.end()); ll ans=0; ans+=k; rep(i,n){ if(ab.at(i).first<=ans){ ans+=ab.at(i).second; } else break; } cout<<ans<<endl; return 0; }
D問題
N×Nの区画中にとれるK×Kの区画のマスの中央値の最小値を求める問題です。
難しかったです。
愚直解は思いつきますが，Ｏ（N^4）でN==800だと到底間に合いません。
計算量落とす工夫も思いつかず15分ほど悩んで先に進みました。
E問題
チェスのポーンの動きをシミュレートして最下段の到達し得るマスの数を出力する問題です。
非常に幅の広いフィールドですが黒ポーンは高々２＊１０^５しかないので，黒ポーンのあるところだけ操作をすればよさそうです。
解法は思いついたのですが，実現するデーター構造を思いつかず，pairをつかったりvector
記念提出
雰囲気はでてますがダメダメです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define int long long signed main(){ ll n,m; cin>>n>>m; vector<vector<int>> G(2*n+1); rep(i,m){ ll x,y; cin>>x>>y; G[x].emplace_back(y); } sort(G.begin(),G.end()); vector<ll>vec; vec.push_back(n); int s=G.size(); rep(i,s){ //cout<<"#"<<vec.size()<<endl; vector<ll>nvec; for(auto e:G){ for(auto u:vec){ if(count(e.begin(),e.end(),u)==0){ nvec.push_back(u); } for(auto v:e){ if(v==u-1){ nvec.push_back(u-1); } if(v==u+1){ nvec.push_back(u+1); } } } } vec=nvec; } cout<<vec.size()<<endl; return 0; }
解説AC
昨晩解説を見て今朝解いてみました。
実装が軽くて冴える技が入っていていい問題です。
setの使い方やmapのsecondでvectorを扱う方法など応用のきく技を理解しました。
sをいじるタイミングで壊してしまわないようaddという配列を用意して更新するところもポイントですね。
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n,m; cin>>n>>m; map<int,vector<int>>mp; rep(i,m){ int x,y; cin>>x>>y; mp[x].push_back(y); } set<int>s; s.insert(n); for(auto p:mp){ vector<int>add; for(auto y:p.second){ if(s.count(y-1)||s.count(y+1)){ add.push_back(y); } } for(auto y:p.second) s.erase(y); for(auto y:add){ s.insert(y); } } cout<<s.size()<<endl; return 0; }
終わりに
今回はD問題以下が崖になっていたため，Cまで比較的スムーズに解けたのが奏功してレートを少し戻すことができました。
D問題は解説をチラ見しましたがまだ理解できていません。
E問題はしっかり復習して理解できました。
水～青難度の問題にじっくり取組んで応用のきく技を身につける努力を続けていきます。
今回のコンテストはCまでは低難易度問題の精進量が効くセットだったと思います。
地道に積み重ねた精進はどこかで必ず役にたつことを実感しました。
引き続き上を目指してがんばります。
set を使う
練習
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define int long long signed main(){ set<int>s; int temp; int n; cin>>n; rep(i,n){ cin>>temp; s.insert(temp); } int m; cin>>m; rep(i,m){ cin>>temp; s.erase(temp); } for(auto e:s){ cout<<e<<endl; } return 0; }
入力例
5 2 4 8 10 101 3 1 2 4
出力例
8 10 101
ABC141E
検討
文字列Sを１文字ずつずらして重ね合わせ，連続して同じ数字になるところの最大連続数を数えます。＜重ならずに＞というところを確保するため，ずらした長さを上限としてmaxを出力します。O（N^2）で十分間に合いそうです。
E問題としては極めて簡単で，E問題におかれていたのであまり解かれなかったのかもしれません。水difの表示ですが最近のABCだとC問題レベルに感じました。
けんちょんさんの解説記事を見ましたが難しくてあまりよく理解できてません。
前処理とかいらないのではと思いました。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int len; cin>>len; string s; cin>>s; int maxcnt=0; for(int i=1;i<len;i++){ int cnt=0; for(int j=0;j<len-i;j++){ if(s[j]==s[i+j]){ cnt++; if(cnt<=i){ maxcnt=max(maxcnt,cnt); } } else{ cnt=0; } } } cout<<maxcnt<<endl; return 0; }
今日の学習
一昨日のABCで蟻本いよいよちゃんとやるぞの思いを強くしました。
やります。
進捗と感想
蟻本P55まで。
DPの復習。
ときおり見直さないといろいろ忘れている。
EDPC D問題の典型ナップサックをいろいろな解き方で解きました。
D - Knapsack 1
再帰か配るDPがわかりやすそう。
メモ化再帰
今日のWAから
× return res=dp[i][j];
○ return dp[i][j]=res;
resの値をdpテーブルにメモしてリターンする場合の書き方です。
分けて書くなら
dp[i][j]=res;
return res;
となるので下が正しいのですがresを返す気持ちが先走り上のような書き方でWAになりました。
上の書き方だとからっぽのdp[i][j]の内容がresに入ってリターンされるのでdpの初期値が返されてしまいます。
memset
直接メモリに書き込んで初期化するようで1byte単位なので0埋めか-1埋めには適しているけれど1埋めなどには向かない。-1埋めで使えるのは全桁が1なので。
memset(dp,-1,sizeof(dp));
メモ化再帰につかうdpテーブルの初期化は-1で初期化するのが本来かもしれないけど0で初期化し0より大きいときにメモ化値を使うようにしても速度などは変らないのでmemsetで初期化しなくてもdpの宣言をグローバルにおいてやれば十分そう。
