yukicoder No.513 宝探し2
- 最初三分探索してた。二分探索で良いのにね。
- 最初にxを探して、見つかったらマンハッタン距離の残りの差分がyまでの距離だから、yは探索しなくて済むね。
#include<bits/stdc++.h> using namespace std; inline int check(int minx,int maxx){ cout<<minx<<" "<<0<<"\n"; int d1;cin>>d1; if(d1==0)return -1; cout<<maxx<<" "<<0<<"\n"; int d2;cin>>d2; if(d2==0)return -1; if(d1==d2)return 0; else if(d1>d2)return 2; else return 1; } int main(){ int minx=0,maxx=100000; int resx=0; bool flag=0; while(maxx-minx>1){ int temp=check(minx,maxx); if(temp==-1)return 0; else if(temp==0){ resx=(minx+maxx)/2; flag=1; break; }else if(temp==1){ maxx=(minx+maxx)/2; }else{ minx=(minx+maxx)/2; } } if(!flag){ int temp=check(minx,maxx); if(temp==1)resx=minx; else resx=maxx; } cout<<resx<<" "<<0<<endl; int dd;cin>>dd; cout<<resx<<" "<<dd<<endl; return 0; }
yukicoder No.561 東京と京都
- 全部探索したいよー(と思います)
- 2の100乗の計算なんて無理よ…
- じゃあ動的計画法(dp)じゃない？
- よし書こう
- 初期の位置は東京に注意しなきゃね。
#include<bits/stdc++.h> using namespace std; int n,d; int t[101],k[101]; long long dp[101][2]; int main(){ cin>>n>>d; for(int i=0;i<n;i++){ cin>>t[i]>>k[i]; } for(int i=0;i<n;i++){ for(int j=0;j<2;j++){ if(i==0 && j==1)continue;//初期に京都はありえないもんね。 if(j==0){ dp[i+1][j]=max(dp[i][j]+t[i],dp[i+1][j]); dp[i+1][1]=max(dp[i][j]+k[i]-d,dp[i+1][1]); }else{ dp[i+1][j]=max(dp[i][j]+k[i],dp[i+1][j]); dp[i+1][0]=max(dp[i][j]+t[i]-d,dp[i+1][0]); } } } cout<<max(dp[n][1],dp[n][0])<<"\n"; return 0; }
yukicoder No.593 4進FizzBuzz
- 数が大きくなる気がするので文字列で受け取ってループ回してやっていきましょう。
- 毎度毎度余りを管理しておけば良いだけなのでやってる事は簡単ですね。
- こんな様な考え方で桁dpとかもやりますよね。
- あと、解説にある豆知識は必見ですね。(全く知りませんでした)
#include<bits/stdc++.h> #define ll long long using namespace std; string s; int main(){ cin>>s; int n=(int)s.size(); int now3=0,now5=0; for(int i=0;i<n;++i){ now3*=4; now5*=4; now3+=(int)(s[i]-'0'); now5+=(int)(s[i]-'0'); now3%=3; now5%=5; } now3%=3;now5%=5; if(now3==0 && now5==0)cout<<"FizzBuzz"<<"\n"; else if(now3==0)cout<<"Fizz"<<"\n"; else if(now5==0)cout<<"Buzz"<<"\n"; else cout<<s<<"\n"; return 0; }
yukicoder No.582 キャンディー・ボックス3
- 僕の大っ嫌いなゲームの必勝法考える奴です。
- 本当に苦手なんで誰かゲームの必勝法がわかる必勝法とか教えてください。
- 今回は出てきませんでしたけどnimみたいなxorとか出てくるのできる気がしないんですよね。
- 深く考え過ぎて解説見たらただの場合分けとかあるし。
- そんな僕でも今回は寝ながら考え抜いた結果自力でAC出来ました！(嬉しい)
- この問題探索とかやっても数が大きい場合にはTLEしちゃうので簡単な必勝法があるはずですよね(制約を見てそう思いました)。
- あとは圧倒的なBの有利性。(ここで数が多い時はおおよそBが勝つんじゃないかと思いました)
- とすると、Bがいつ負けるのかを考えることに。。
- 元から箱の中のキャンディーの数が1個の時とかはいくらBでもキャンディーの数を有利にコントロールするのは無理そうですよね。
- ということは、全部1個のキャンディーしか無かったら箱の数に依存します。
- 他には無いかなー？なんて考えるとサンプル1がヒントですよ！
- Aが先手である事で唯一2個の箱があった場合はその2個の箱から1個取る事で勝てる時があります(その1個を取ってからは箱の個数で勝敗が別れます)
- こんな感じで考えると場合分けできるんじゃ無いですか？(もっと良い考え方はありそうだけど)
#include<bits/stdc++.h> using namespace std; int n; int a[151],b[151]; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } int cont=0; for(int i=0;i<n;i++){ if(a[i]!=0){ b[cont]=a[i]; cont++; } } n=cont; int gt2=0; int eq2=0; for(int i=0;i<n;i++){ if(b[i]==2){ eq2++; }else if(b[i]>2){ gt2++; } } if(gt2>0 || eq2>1){ cout<<"B"<<"\n"; }else if(eq2==1){ if(n&1){ cout<<"B"<<"\n"; }else cout<<"A"<<"\n"; }else{ if(n&1){ cout<<"A"<<"\n"; }else cout<<"B"<<"\n"; } return 0; }
yukicoder No.592 括弧の対応(2)
- 何かと括弧ってスタックって言うデータ構造と相性が良い気がするんですよ。
- なので、括弧の問題を考える時はまずゆっくりスタックの性質を考えながら解いていくと良い気がします。(僕も経験が浅いので大きい事は言えませんが)
- あと、類似した問題を2個程見たことがあるのでやったことが無い人は挑戦してみてね(そんなに複雑じゃないよ)
#include<bits/stdc++.h> using namespace std; int n; string s; int a[200001]; int ans[200001]; int main(){ cin>>n>>s; for(int i=0;i<n;i++)a[i]=i+1; stack<int> st; for(int i=0;i<n;i++){ if(s[i]==')'){ int temp=st.top(); ans[i]=temp; ans[temp-1]=i+1; st.pop(); }else{ st.push(i+1); } } for(int i=0;i<n;i++)cout<<ans[i]<<"\n"; return 0; }
yukicoder No.609 Noelちゃんと星々
- 中央値に集めるのが最適なんて知らないし、考えもしなかった人は三分探索を思いついたよね。
- 三分探索知らない人はGoogle先生に問い合わせてみよう。(わかりやすい記事があったはず)
- 俺スゲー賢いとか思った僕は解説読んで知識増やしていこうね
- 因みに以下のコードは三分探索の書き方を忘れた人間が苦し紛れに書いたものなので、もっと短くて読みやすいコードを提出一覧から見つける事をオススメします！
#include<bits/stdc++.h> #define ll long long using namespace std; int n; int a[100001]; inline bool check(ll m1,ll m2){ ll sum1=0,sum2=0; for(int i=0;i<n;i++){ sum1+=abs(m1-a[i]); sum2+=abs(m2-a[i]); } if(sum1>=sum2)return 1; else return 0; } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } int cont=0; ll l=-1000000000,r=1000000000; while(cont<80){ ll mid1=(r+2*l)/3; ll mid2=(l+2*r)/3; //cerr<<mid1<<" "<<mid2<<endl; if(check(mid1,mid2)){ l=mid1; }else{ r=mid2; } cont++; } ll ans=(ll)1e15; for(int i=l;i<=r;i++){ ll nowsum=0; for(int j=0;j<n;j++){ nowsum+=abs(i-a[j]); } ans=min(ans,nowsum); } cout<<ans<<endl; return 0; }
yukicoder No.604 誕生日のお小遣い
- 二分探索やるんですよ。
- 予め、何年か指定したらいくら貰えてるか計算しやすいし。(check関数のこと)
- 算数が苦手な人でもこっちならいけるんじゃない？(僕のことです)
- あとはlong long だとオーバフローします。(unsignedつけようね)僕はミスしました。
#include<bits/stdc++.h> #define ll unsigned long long int using namespace std; ll a,b,c; inline bool check(ll m){ ll sum=m/a*b+m-m/a; if(sum>=c)return 1; else return 0; } int main(){ cin>>a>>b>>c; ll ng=0,ok=c; while(ok-ng>1){ ll mid=(ok+ng)/2; cerr<<mid<<endl; if(check(mid)){ ok=mid; }else{ ng=mid; } } cout<<ok<<endl; return 0; }
