1秒差で負けた [CADDi 2018 for beginners]
- 久しぶりに全完できました
- 結構早く解けました(500の実装がクソ軽かった)
- 1秒差で3位=>4位になったので賞金が1万円=>5000円になりました
- 1ペナで20:56で5分間(頼む誰も全完するな...)と思っていましたが4:59経った時全完されました(悲しい)
C問題
- かけてPになるN個の数がある時、それらすべてのgcdの最小値を求める問題です。
- Pを素因数分解したとき、同じ素因数をからまで均等に分けるのが良いので、図のようにします(一般化して書く能力がないのでsample 4で)
- 素因数分解のスニペットを持っていたので10分で実装できました
- 考察中はでやっていて、とが同じなために上ののところをとして1WAを出しました
int main(){ lint n,p;cin>>n>>p; lint plf=p,pp; map<lint,lint>ma; for(lint i=2;i*i<=p;++i){ if(!(plf%i)){ pp=1;plf/=i; while(plf%i==0){ ++pp;plf/=i; } //ここで、因数i^ppがわかる i is prime ma[i]=pp;//処理 } } if(plf!=1){ //ここで、因数plf^1がわかる plf is prime ma[plf]=1; } lint ans=1; for(auto i:ma){ if(i.second>=n)ans*=pow(i.first,i.second/n); }cout<<ans; }
D問題
一本のりんごの木があり、N色のりんごが実っています。これらのりんごの N種類の色には 1から Nまでの番号が振られており、i番の色のりんごは 個あります。 あなたとダックスフンドのルンルンは、以下の行動を交互に行います (あなたから始めます)。 木から1個以上のりんごを選んで食べる。ただし、一度に選ぶりんごは全て異なる色でなければならない。 木から最後のりんごを食べた者を勝者とします。あなたとルンルンがともに最善を尽くすとき、どちらが勝つでしょうか?
という問題です。 同じ色を列に並べて考えると、
- サンプルを見て考えると「相手のターンにわたるときにすべての列にあるりんごの個数が偶数になっていれば勝ち」だとわかります。
- なので始めのターンに「奇数の列からすべて取る」ができればfirstの勝ちです。
- それができないのはすべての列が最初から偶数になっているときなので、すべての列が偶数個になっているかわかればいいです。
- 証明はしていないw
int main(){ lint n;cin>>n; vector<lint> a(n); bool first=0; rep(i,n){ cin>>a[i]; if(a[i]&1)first=1; }cout<<(first?"first":"second"); }