エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）参戦記
はじめに
2021年5月22日21:00-22:40に開催された表題のコンテストに参加しました。
結果は，64分42秒3完 5189位／8714位 パフォーマンス410でレーティングは前回902から-41の861となりました。
A問題
サイコロを３回振り，出た目の反対側の目の合計を出力する問題です。
1分05秒で提出。
C問題
問題文を理解するのにちょっと手間取りました。
愚直にやるとTLEしそうなので，どう計算量を落とすか悩みましたが，少し悩んで思いつかなかったので，先にD問題以降をやろうと思い飛ばしました。
D問題
A個の a と B個の b からなる長さ A+Bの文字列のうち、辞書順で K番目のものを求める問題です。
これもまともにやるとオーバーフローもしくはTLEしそうだったのでO（１）解法を探すべく小さめのABで少し実験しましたが法則性を思いつけず。飛ばしてＥ問題へ。
E問題
最近力を入れて勉強しているグラフ問題だったのでこの問題に賭けました（賭けに負けました）。
最短パスがDiである頂点の出力はDFSで容易にできましたが，根への最短パス上にUiが存在することをO（１）で求める部分に失敗しました。
最初に考えたのは，ある頂点までに通ってきた頂点を頂点毎に配列で保持する方法ですが，これだと根への最短パス上にUiが存在することを判別するのに各頂点毎にO（N）を要し，Nもクエリ―も１０＾５なのでTLE必至です。
次にある頂点までに通ってきた頂点をmapのベクターで保持する方法を考えましたが，これが意外に難しくうまく実装できませんでした。うまく実装できていればO（N）・O（logN）で間に合っていたつもりです。
だいぶ苦闘しましたが結局解ききれず。
途中で順位表見るとC問題がけっこう解かれているので，せめてC問題だけでも解いておこうと思い，C問題を解きました。見返してみると配列BCだけをつかった前計算をしておけばよいことに気づきました。飛ばさずに解いていたら１０～１５分くらいだったでしょうか。ぎりぎりパフォ８００ぐらいのラインで，いずれにしても冷えていました。
京セラプログラミングコンテスト2021（ABC200） 参戦記
はじめに
2021年5月8日21:00-22:40に開催された京セラプログラミングコンテスト2021（ABC200）に参戦しました。
結果は125分02秒（8ペナ含む）4完で1709位／8577人中、パフォーマンス1217でレーティングは前回909から+35の944になり、highestを更新しました。
A問題
XX年は何世紀ですか、という問題。
2000年までが20世紀で2001年は21世紀とかちょっとわかりにくく感じることもありました。
100で割って切り上げる、というのは１引いて100で割って1足す操作です。
境目を丁寧に試してAC.
2分6秒。
B問題
整数N（<10^5）が与えられ、（操作１）200で割れるときは200で割る、（操作２）割れないときは末尾に文字列として200を加えた数に置き換える、という操作を20回以内する問題です。文字列で3ケタづつ足す操作でどこまで数が大きくなるのか不安に感じましたが、そもそもB問題で文字列で整数を扱わなければならないこともないだろう、とも考えました。末尾に200を加えた数は必ず200で割り切れるので操作２の回数は多くても１０回。操作１により２桁小さくなるので、long long 型に収まりそうです。
素直に操作を実装してAC。
3分8秒、通算5分14秒。
C問題
数列Aの中に差が200で割り切れるペアがいくつあるかを問う問題です。
N<10^5なのでO（N^2）では間に合わないのは明らかです。
しばらく考えて、200で割った剰余が等しいものの数を数えればよいことに思い至りました。
しばらく前に苦労した問題にでてきた技です。
D - Multiple of 2019
mapで管理して剰余が等しいものの数がもとまればあとはコンビネーションを足していきます。
7分19秒 通算12分33秒と自分にしては快調に3完できてほっとしました。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int d[200]; signed main(){ int n; cin>>n; int a[n]; rep(i,n){ cin>>a[i]; d[a[i]%200]++; } int ans=0; rep(i,200){ if(d[i]>1){ ans+=(d[i]*(d[i]-1)/2); } } cout<<ans<<endl; return 0; }
D問題
難しかったです。
数列中から異なる組み合わせでつくった部分数列の200で割った剰余が一致するものの有無を判定し、あれば一例を出力する問題です。
なかなか方針が思いつかず、最初はサンプルケースのmod200を出力するプログラムを書いて結果を眺めるなどしました。そうこうしているうち、鳩ノ巣原理を思い出し、最初の８個だけ試せばかならず重複がでてくるはずであることに気づきました。bit全探索で試せそうです。
もっとも解答を出力するあたりの実装に手間取ったり、全探索を２回やって結果が合うところを探さなければならないことに気づくまで時間がかかったり、更に２回とも同じ組み合わせしてしまっていたりして時間を溶かしWAを重ねました。このあたりになるともうペナ出すのは怖くなくなります。
途中では疑心暗鬼になり，やっぱり８個試すだけだとだめなんだろうかと弱気になって16個試してみたり迷走を続けました。最後に気づいたのはbit==0の組み合わせを出力してしまっていたことでした。自分でサンプルケースをつくっていろいろ試す中で発見できました。
提出コードは無駄が多くて恥ずかしすぎるので貼りません。
ACできて 解けた！を味わうことができました。
72分29秒8ペナ 通算85分02秒＋8ペナ
E問題
Dまで解けてまだ15分程度残していたのでEを考察する時間ができました。
パスカルの三角形みたいなのを考えて何個目の島に入っているかを求め、更にその島の中での位置を求める、みたいなことを考えてみましたが解法まで辿り着けず。後日ゆっくり考えます。
おわりに
highestの更新は、これまでに到達できなかった高みまで登れたということなので、まだまだ自分には可能性があるという希望を与えてくれます。今回のコンテストはたまたま相性がよかったこともありますが，Ｃ問題は苦しんだ過去問の経験を活かせましたし、Ｄ問題は最近の精進ですらすら書けるようになってきたbit全探索に助けられました。
努力せずによい結果を出すのがかっこいいみたいな風潮を感じることもありますが，私は違う価値観を持っています。資質や環境、ハンディキャップなどでなかなか伸びないこともあるけれど、できなければ人の２倍、３倍努力して追いつけばいいし、愚直にこつこつと地道な努力を重ねることこそが貴いことだと思っています。引き続きがんばります。
ZONeエナジープログラミングコンテスト参戦記（5月1日）
はじめに
5月1日21:00-22:40に開催されたZONeエナジープログラミングコンテストに参戦しました。
結果はABDの３完97:26 2ペナでパフォ―マンス849、レーティングは前回916から-7の909になりました。
A問題
A問題にしては難し目に感じました。今回はＢ問題以下も難し目でしたが。
substrの位置をよく間違えるので４文字程度だしと思って配列で処理しました。
2分55秒。
提出コード
#include <bits/stdc++.h> using namespace std; signed main(void) { string s; cin>>s; int cnt=0; for(int i=0;i<9;i++){ if(s[i]=='Z'&& s[i+1]=='O'&&s[i+2]=='N' && s[i+3]=='e'){ cnt++; } } cout<<cnt<<endl; return 0; }
Ｂ問題
今回冷えた一番の原因。
最初は方針を間違ってスタートし、その後はうまく立式できず後回しにしました。
戻ってきて解いたのですがなかなか合わずに40分以上かかってしまいました。
落ち着いてゆっくり解くこと、変数名を間違えにくいものでしっかり設定すること、あたりが反省点です。
最初に間違えた方針は答えの高さを二分探索する、というもので書きあげたあとで整数でないことに気づきぎゃふんとなりました。
型のキャストとかの知識もあやふやで一度しっかり押さえておかなければと思いました。
40分＋αかかっていて完全に嵌りました。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) signed main(void) { int n,d,h; cin>>n>>d>>h; int dn[n]; int hn[n]; rep(i,n){ cin>>dn[i]>>hn[i]; } double maxans=0.0; double ans=0; rep(i,n){ maxans=max(maxans,((double)hn[i]-(((double)h-(double)hn[i])/((double)d-(double)dn[i]))*(double)dn[i])); } cout<<maxans<<endl; }
C問題
ちらっと見て難しそうで飛ばしました。
昨晩解説ACし、今日、午前中に書きなおしましたがbitを使ったスマートな方法やunique関数による圧縮など新しい技がいろいろあって勉強になりました。
D問題
文字列操作のいろいろなテクニックがてんこ盛りでした。
dequeを使った実装はすぐに思いつきましたが重複を削除するのにdequeのままでは処理が難しく血迷って試行錯誤して無駄なWAを出してしまいました。
最後は愚直にdeque処理のあとstringに落として処理しました。
追加する方向を間違えたまま最後に無理無理合わせてるのでだいぶへんてこなコードになりました。
提出コード
#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(void) { string s; cin>>s; deque<char>deq; int len=s.length(); int flag=1; rep(i,len){ if(s[i]=='R'){ flag*=-1; continue; } if(flag==1){ deq.push_front(s[i]); } else{ deq.push_back(s[i]); } } string ans=""; len=deq.size(); rep(i,len){ ans+=deq[i]; } if(flag==1){ reverse(ans.begin(),ans.end()); } ans+='0'; int cur=0; while(cur != ans.length()){ if(ans[cur]==ans[cur+1]){ ans.erase(cur,2); cur--; continue; } cur++; } if(ans=="0"){ return 0; } else{ ans.erase(ans.size()-1,1); } cout<<ans<<endl; }
E問題
コンテスト中は手が出ず。
午前中にがんばって書きました。
もっとシンプルな方法がありそうなので勉強します。
コード
#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 int a[550][550]; int b[550][550]; int used[550][550]; int r,c; signed main(){ const int INF=1001001001; vector<vector<int>> d(550,vector<int>(550,INF)); cin>>r>>c; rep(i,r+1) rep(j,c+1){ used[i][j]=0; } for(int i=1;i<=r;i++){ for(int j=1;j<=c-1;j++){ cin>>a[i][j]; } } for(int i=1;i<=r-1;i++){ for(int j=1;j<=c;j++){ cin>>b[i][j]; } } priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> p; p.push(make_tuple(0, 1, 1)); while(!p.empty()){ ll cs = get<0>(p.top()); ll x = get<1>(p.top()); ll y = get<2>(p.top()); p.pop(); if(x==r && y==c){ cout<<cs<<endl; return 0; } if(used[x][y]==1){ continue; } used[x][y]=1; if(y<c && used[x][y+1] != 1){ if(d[x][y+1]>cs + a[x][y]){ d[x][y+1]=cs + a[x][y]; p.push(make_tuple(cs + a[x][y], x, y + 1)); } } if(y>1 && used[x][y-1] != 1){ if(d[x][y-1]>cs+a[x][y-1]){ d[x][y-1]=cs+a[x][y-1]; p.push(make_tuple(cs + a[x][y-1], x, y - 1)); } } if(x<r && used[x+1][y] != 1){ if(d[x+1][y]>cs + b[x][y]){ d[x+1][y]=cs+b[x][y]; p.push(make_tuple(cs + b[x][y], x+1, y)); } } for(int i=1;i<x;i++){ if(used[x-i][y] != 1){ if(d[x-i][y]>cs+i+1){ d[x-i][y]=cs+i+1; p.push(make_tuple(cs + i + 1, x-i, y)); } } } } }
終わりに
今回はB問題で嵌って時間がかかり失敗しました。
もっとも緑パフォで失敗したと思えるのはだいぶ力がついたなと感じています。
C問題、E問題も次に類題がでれば解けるはずです。
更に精進していきたいと思います。
ABC199参戦記
はじめに
2021年4月24日21:00-22:40に開催されたABC199（Sponsered by Panasonic）に参戦しました。
結果は23:23 ３完ノーペナで1946位/8716人中のパフォ1142、レーティングは前回887から+29の916となりhighestを更新しました。
A問題
A^2+B^2とC^2の大小を判定する問題。
１分３０秒。
B問題
いずれも長さNの数列Ai,BiについてＡi以上Bi以下を充たす整数Xの数を求めます。
Aiの最大値とBiの最小値の間にあるXの数を出力します。
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i=0;i<n;i++) int main(){ int n; cin>>n; int a[n]; int b[n]; rep(i,n) cin>>a[i]; rep(i,n) cin>>b[i]; int minx=-1; int maxx=1001; for(int i=0;i<n;i++){ minx=max(minx,a[i]); maxx=min(maxx,b[i]); } cout<<max(0,maxx-minx+1)<<endl; return 0; }
4分56秒 通算６分26秒
C問題
長さ２Nの文字列Sに対し，①Ai番目とＢi番目を入れ替える，②前半と後半を入れ替える，の２種類のクエリを繰り返した結果のSを出力します。文字列長が最大４＊１０＾５ クエリが最大３＊１０＾５あるので，入れ替えクエリをまともに処理してるとTLEになることにはすぐ気づきました（進歩してる♪）。
入れ替えはやったふりをして，入れ替えている状態かどうかのフラグをたてる方針で解きました。
実装はちょっと手間取りましたが沼らずに書けてよかったです。
16分47秒 通算23分13秒
提出コード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i=0;i<n;i++) typedef long long ll; int main(){ int n; cin>>n; string s; cin>>s; int q; cin>>q; int flag=1; rep(i,q){ int t,a,b; char temp; cin>>t>>a>>b; a--; b--; if(t==1){ if(flag==1){ temp=s[b]; s[b]=s[a]; s[a]=temp; } else{ int na,nb; if(a<n){ na=n+a; } else{ na=a-n; } if(b<n){ nb=n+b; } else{ nb=b-n; } temp=s[nb]; s[nb]=s[na]; s[na]=temp; } } if(t==2){ flag*=-1; } } if(flag==1){ cout<<s<<endl; } else{ cout<<s.substr(n,n)<<s.substr(0,n)<<endl; } return 0; }
D問題
残り時間のうち１時間ほどを費やして考えましたが解けませんでした。
方針としてはUnionFindで連結成分にわけ，連結成分毎に方法の数を出して掛け合わせる方法に思い至りました。
各連結成分の組み合わせ数は最初の頂点の色の選び方は３通り，それにつながる頂点の色の選び方は２通り，ただしループする場合には１通り，２か所からループがつながると塗れなくなる，ということでDFSに乗せようとしましたがうまく書けず。まだまだ修行がたりません。
感想など
D以下がとにかく難しかったです。
Cまで比較的スムーズにとけたことでhighestを更新できましたが，水を目指すにはもう一歩先に進む必要があります。
最近はcodeforcesやyukicoderなどの低難易度問題を数こなして基礎体力をつけるとともに，典型90問などでもう一歩上の考察力，典型力をつけることを心掛けています。
レーティンググラフはいい感じに上向きました。
しばらくABCが毎週続くので着実に結果を出していきたいと思います。
応用情報技術者受験記 2021.4.18
はじめに
２０２１年４月１８日令和３年度春期の応用情報技術者試験を受けてきました。
応用情報技術者試験は技術のみならず管理・経営分野にまたがった試験で，「高度IT人材となるために必要な応用的知識・技能をもち、高度IT人材としての方向性を確立した者」を対象者像とする試験です。
択一式の午前試験に加え，問題選択ができる午後試験（セキュリティの１問は必須，４問は１０問中から選択）があり，合格基準は午前午後もいずれも６０％以上です。
一昨年，基本情報技術者試験を受けましたが若干傾向が異なり，応用情報技術者の方がマネジメント・経営寄りの知識で対応できる部分が多いように感じました。
午前試験
テクノロジ系５０問，マネジメント系１０問，ストラテジ系２０問の全８０問を１５０分で回答します。
問題リンク
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2021r03_1/2021r03h_ap_am_qs.pdf
準備は２月から２ヶ月程度，簡単なテキストで基礎知識を入れて，
過去問を練習できるサイト，応用情報技術者試験ドットコムで過去問をやりました。
過去問は2480問中358問，14.4%の進捗であまり準備できませんでした。
もっとも過去問はだいたい７割ぐらいできてたのでまあいけるかな，という感触でした。
既に解答例が公表されており、自己採点５６／８０で７０％のできでした。
＜解答例＞
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2021r03_1/2021r03h_ap_am_ans.pdf
午後試験
もう少し早くから準備しとけばよかったなと思いました。
必須のセキュリティのほかは１０分野から選択します。
問題リンク
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2021r03_1/2021r03h_ap_pm_qs.pdf
当日は経営戦略，プログラミング，サービスマネジメント，システム監査の４問を選択しました。
経営戦略，サービスマネジメント，システム監査はいずれも国語の問題みたいな感じでいずれも解きやすい問題だったと思います。プログラミングもわりと解きやすい問題でした。電卓持ち込みできないので手計算が大変でしたが。
必須の情報セキュリティがDNSに関する問題で知識が不十分でがたがただったのが失敗です。
まあ６割ぐらいはできたかな。
＜プログラミングの問題用紙＞
おわりに
資格試験は勉強するよいモチベーションになります。
今回は準備にあまり時間がとれませんでしたが，それでも新たな知識や考え方のヒントをたくさん得ることができたと思います。
6/24追記
無事合格していました。
ABC194E Mex Min
昨晩はABC194E Mex Minに取り組みました。
ある数字が数列の何番目にでてくるかを保持する配列を準備し，0から順に候補を試し，配列の要素間の距離がMを超える場合，もしくはその候補がない（配列のサイズが0）の場合，その候補を出力する，という方針でACしました。
配列の位置の数は配列の要素の数と同じなので，計算量はほぼＯ（Ｎ）。
最後にWAが取れずに少し苦労したのが終端の処理でした。
最後の要素と終端の距離がMあればansになるので要素数から現在位置を引いた値とMを比較して判定するようにしてクリアー。
if(n-temp>=m){ cout<<i<<endl; return 0; }
提出コード
#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,m; cin>>n>>m; vector<int>a(n+2); a[0]=0; a[n+1]=0; int maxa=0; rep(i,n){ cin>>a[i+1]; maxa=max(maxa,a[i+1]); } set<int>is[maxa+2]; rep(i,n+2){ is[a[i]].insert(i); } rep(i,maxa+2){ if(is[i].size() ==0){ cout<<i<<endl; return 0; } int temp=0; for(auto e=is[i].begin();e != is[i].end();e++){ if(*e-temp>m){ cout<<i<<endl; return 0; } else{ temp=*e; } } if(n-temp>=m){ cout<<i<<endl; return 0; } } return 0; }
本番で見たとき非常に難しく感じたのに緑difで驚いたのですが，一昨日あたりに取り組んだABC157E Simple String Queriesで文字列中に文字が現れる場所の集合を管理する方法を学んでいたので，今回は簡単に感じました。Simple String Queriesは水difでしたので，みんなしっかり精進しているんだなあと思いました。
ABC１９８参戦記
はじめに
2021年4月11日21:00-22:40に開催されたABC198に参戦しました。
結果は103分52秒4完3ペナで1759位／8172人中。
パフォーマンス1152でレーティングは前回817から39上がって856でした。
直近4連続で冷えていたので久しぶりに温まってよかったです。
Ａ問題
N個のお菓子を２人で両者とも最低１個以上になるような分け方を求める問題です。
簡単でしたが一応サンプルにも目を通してAC。
1分04秒
B問題
Nを十進数で表した文字列の先頭に０を０個以上つけて回文にできるかという問題。
末尾の０を取った残りの文字列が回文かどうかで判定しました。
7分35秒 通算8分39秒はまあまあ。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) int main(){ string s; cin>>s; int len=s.length(); while(1){ if(s[len-1]=='0'){ s=s.substr(0,len-1); len--; continue; } break; } rep(i,len){ if(s[i]==s[len-1-i]) continue; cout<<"No"<<endl; return 0; } cout<<"Yes"<<endl; return 0; }
C問題
点(X,Y)までユークリッド距離Rを何回でいけるかという問題です。
距離が１回分より小さい時に２回かかるのがコーナーでした。
誤差がちょっと怖かったですが単純にceilとってACできました。
少し手間取りましたが通算27分17秒。
#include <bits/stdc++.h> using namespace std; int main(){ double r,x,y; cin>>r>>x>>y; double ans=ceil(pow(x*x+y*y,0.5)/r); if(ans==1 && x*x+y*y != r*r){ cout<<2<<endl; return 0; } cout<<setprecision(18)<<ans<<endl; }
D問題
10桁までの数２つを足す覆面算です。
今の実力では厳しいかと思いましたが典型っぽい問題だったのでぐぐったところAOJ1161を見つけました。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161&lang=jp
AOJ1161は８ケタまでの数を２～７個足す問題で使う文字が大文字，出力が成立する組み合わせの数を出力する，という点が本問と異なります。
AOJの正解コードから理解しやすいやつを捜して加工しました。
next_permutationを使って全探索するのがオーソドックスそうです。
組み合わせの数を出力するのに変えて成立した場合にその場合の数字を出力するようにすること、組み合わせの数が０だった場合に”UNSOLVABLE”を出力すること、足し合わせる数を２つにすること、覆面につかう英文字を小文字にすること、といったアレンジをしていい感じになりました。
文字の組み合わせが１０種類となった場合に”UNSOLVABLE”にする点に気づきWAケースは１つのみになりました。
最後に気づいたのは10桁同士の足し算なのでint型に収まらないケースがあることで＃define int long longを使ってAC.
Submission #21686740 - AtCoder Beginner Contest 198
時間はかかりましたがACできてよかったです。
61分35秒 通算88分52秒。
おわりに
E問題に入ったところで残り10分ほどでした。
解法が見えずに時間切れでした。
まだまだ足りないところばかりですが手応えのある結果でした。技を磨いてスピードをつけること、高難易度の問題に恐れず挑める力をつけることを念頭に、引き続きがんばります。
４月になって新入学の大学生など参加者が増えてくるとレートを伸ばしやすくなるのではないかとちょっと期待しています。
