ABC165 2020.5.2
昨日のＡＢＣ１６５はＡ，Ｂ，Ｄの３完でパフォーマンス７２０。レーティングは最高を更新し５４１になりました。Ｃ問題にまったく手がでず、飛ばしてＤを解いた判断がよかったです。しかし、Ｃ問題は、解説を見て、いずれはクリアーしなければならない問題だと思いました。Ｃ問題の解説、まだ理解できませんがこの先の目標にするラインが見えてきたような気がします。再帰を使ったＤＦＳを自在に使いこなせるようになりたいです。Ｃ問題をACしているのは約2500人、今回参加者の上位２０％程度です。今回ちらっと見えた頂あたりに到達すれば水色の世界が見えてくるように思います。解説のポイントからA:制約を見るといずれの数も高々1000なので簡単なのは全ループをかけるのが楽。----#include <iostream>using namespace std;int main(){ int A,B,K; cin>>K>>A>>B; for(int i=A;i<=B;i++){ if(i%K==0){ cout<<"OK"<<endl; return 0; } } cout<<"NG"<<endl; return 0;}----A問題ではループかけなくても解ける問題を出している。B以下で最大のKの倍数を求め，これがＡ以上かで判定。----#include <iostream>using namespace std;int main(){ int A,B,K; cin>>K>>A>>B; if(B/K*K>=A ){ cout<<"OK"<<endl; return 0; } cout<<"NG"<<endl; return 0;}----Ｂ問題解説では１％ 1/100を加えていく処理をしていた。私の提出コード。これでも問題なくAC。-------------#include <bits/stdc++.h>using namespace std;int main(){ long long K; long long n=100; long long ans=0; cin>>K; while(n<K){ n*=1.01; ans++; } cout<<ans<<endl;}------------Ｃ問題制約にNとMが小さいのがポイント。これは気づいたが全列挙するようなアルゴリズムが書けなかった。〇と仕切り｜の並べ方の問題と考える。〇｜〇〇｜｜｜〇｜｜〇｜｜１０までの数での数列だと仕切りは９個19 choose 9= 92378通りグーグル検索で電卓代わりに使える。dfsで全探索をかけたいのでグローバルに変数宣言をおく（行儀がよくない？）vector を引数にdfs呼び出すとか超絶技巧。空配列にpush_back()ができない。再帰 １ステップで何をすれば次につなげられるか 終了条件は何かこの手のdfsは頻用するのですらっとかけるようになっているとよい。----void dfs(vector<int> A){ if(A.size()==n+1){ int now =0; rep(i,q){ if<条件にあうもののansを加算> } ans=max(ans,now); return; } A.push_ack(A.back()); while(A.back()<=m){ dfs(A); A.back()++; }}---- main関数からは dfs(vector<int>(1,1)); で呼び出し。 dfs(0)で呼んでいないのは空配列にpush_back()ができないから。
